Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
A 15-Year Retrospective on Insertion-Deletion Systems: Progress, Evolution, and Future Directions
Authors: Alhazov Artiom, Sergiu Ivanov, Sergey Verlan
Keywords: insertion-deletion systems, computational completeness, decidability, regulated rewriting.
– 0.20 Mb
Keywords: insertion-deletion systems, computational completeness, decidability, regulated rewriting.
Abstract
This paper offers a comprehensive retrospective on the development and results in the field of insertion-deletion systems over the past 15 years, building upon an earlier foundational overview from 2010. We review key theoretical developments, new extensions, and variations that have emerged, examining their impact on the computational power of insertion-deletion systems. This retrospective aims to update the field's understanding of the model, providing insights into the latest progress and identifying promising directions for future research.Artiom Alhazov
ORCID: https://orcid.org/0000-0002-6184-3971
State University of Moldova,
Vladimir Andrunachievici Institute of Mathematics and Computer Science
Academiei 5, Chișinău, MD-2028, Moldova
E-mail:
Sergiu Ivanov
ORCID: https://orcid.org/0000-0002-1537-6508
Université Paris-Saclay, Université Évry,
IBISC, 91020, Évry-Courcouronnes, France
E-mail:
Sergey Verlan
ORCID: https://orcid.org/0000-0001-7800-1618
University of Paris Est Creteil
Univ Paris Est Creteil, LACL, F-94010, Creteil, France
E-mail:
ORCID: https://orcid.org/0000-0002-6184-3971
State University of Moldova,
Vladimir Andrunachievici Institute of Mathematics and Computer Science
Academiei 5, Chișinău, MD-2028, Moldova
E-mail:
Sergiu Ivanov
ORCID: https://orcid.org/0000-0002-1537-6508
Université Paris-Saclay, Université Évry,
IBISC, 91020, Évry-Courcouronnes, France
E-mail:
Sergey Verlan
ORCID: https://orcid.org/0000-0001-7800-1618
University of Paris Est Creteil
Univ Paris Est Creteil, LACL, F-94010, Creteil, France
E-mail:
DOI
https://doi.org/10.56415/csjm.v32.18Fulltext
– 0.20 Mb
Contents
- Preface
- Generalized Distributed Reaction Systems
- A 15-Year Retrospective on Insertion-Deletion Systems: Progress, Evolution, and Future Directions
- Insertion Systems Controlled by Ideals and Codes
- Restrictions on Multicounter and Partially-Blind Multicounter Languages
- Meadows in the Heptgrid and Possible Generalizations
- A Universal Reversible Turing Machine that Directly Simulates Reversible Counter Machines
