On decidability of problems involving insertion operations
Date
2025-06-14
Authors
Ibarra, Oscar H.
McQuillan, Ian
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
ORCID
Type
Article
Degree Level
Abstract
In the past, there have been many different string insertion operations—often inspired by biological or physical systems—that have been defined and studied using formal language theory. For each such insertion operation, it is common to state various decision problems using important computational models, and to study whether these problems are decidable or not. Here, we generalize this approach by studying any possible insertion operation that can be defined as long as they produce every string in some lower bound language and no strings outside some upper bound language. We create two different such classes of insertion operations called general contextual insertion operations and general concatenative insertion operations. Several problems (so-called language equations) are shown to be undecidable no matter how an insertion operation is defined, so long as it belongs to one of these classes of operations. Several problems are also shown to be decidable, as long as the insertion operation satisfies some simple conditions. This general approach covers many different insertion operations that have been defined and studied in the literature, from classical operations such as concatenation and shuffle, to bio-inspired insertion operations, and we are able to demonstrate many stronger decidability results than what was previously known.
Description
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s11047-025-10032-x
Keywords
Insertion Operations, Finite Automata, Counter Machines, Decidability, Closure Properties, Algorithms, Computability and Recursion Theory, Computational Complexity, Data Structures, Formal Languages and Automata Theory, Lisp
Citation
Ibarra, O.H., McQuillan, I. On decidability of problems involving insertion operations. Nat Comput (2025). https://doi.org/10.1007/s11047-025-10032-x
Degree
Department
Program
Advisor
Committee
Part Of
item.page.relation.ispartofseries
DOI
https://doi.org/10.1007/s11047-025-10032-x