Insertion languages
The operations of insertion (\(\leftarrow)\) and iterated insertion (\(\leftarrow *)\) are variants of Kleene's operations \(\cdot\) and *. For languages S and T, \(S\leftarrow T=\{xzy:xy\in S\quad and\quad z\in T\}\) and \(S\leftarrow *=\{\lambda \}\cup S\cup S\leftarrow S\cup...\) (where \(\lambda\) is the empty word). The class of languages of the form \(S\leftarrow *\) for finite S forms a class of generalized Dyck languages. The problems of equivalence, ambiguity and determinism are investigated for this class and all are shown to be decidable. On the other hand, it is shown that the problem \(S\leftarrow *T\leftarrow *=\{\lambda \}?\) is undecidable for finite unambiguous S and T. By extending the regular expressions to include the operations \(\leftarrow\) and \(\leftarrow *\), the class of insertion languages is obtained, which includes both the regular languages and the Dyck languages, but is properly contained in the class of context-free languages. It is shown that the problem \(L=\Sigma *?\) is undecidable for the class of insertion languages. From this it follows that the equivalence problem and the problem Is L regular? are also undecidable for this class.
- A characterization of context-free languages
- A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free
- A note on undecidable properties of formal languages
- A variant of a recursively unsolvable problem
- Confluent and Other Types of Thue Systems
- Full AFLs and nested iterated substitution
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3550181 (Why is no real title available?)
- scientific article; zbMATH DE number 3634526 (Why is no real title available?)
- scientific article; zbMATH DE number 3238653 (Why is no real title available?)
- Infinite regular Thue systems
- On regularity of context-free languages
- On the enlargement of the class of regular languages by the shuffle closure
- On theories with a combinatorial definition of 'equivalence'
- Software Descriptions with Flow Expressions
- Some definitional suggestions for automata theory
- The power of synchronizing operations on strings
- Une généralisation des ensembles de Dyck
- Outfix-guided insertion
- 1-normal DRA for insertion languages
- On path-controlled insertion-deletion systems
- On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
- Universal insertion grammars of size two
- Site-directed insertion: language equations and decision problems
- On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
- Generating and accepting P systems with minimal left and right insertion and deletion
- Outfix-guided insertion (extended abstract)
- Descriptional complexity of graph-controlled insertion-deletion systems
- Two results on discontinuous input processing
- Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
- On the ambiguity of insertion systems
- On succinct description of certain context-free languages by ins-del and matrix ins-del systems
- Context insertions
- scientific article; zbMATH DE number 446842 (Why is no real title available?)
- Word-paired insertions of languages
- On basic properties of jumping finite automata
- scientific article; zbMATH DE number 1836431 (Why is no real title available?)
- Insertion-deletion systems with substitutions. I
- Decidability questions for insertion systems and related models
- On bonded sequential and parallel insertion systems
- Regulated insertion-deletion systems
- Aspects of Molecular Computing
- A characterization of (regular) circular languages generated by monotone complete splicing systems
- Insertion-deletion with substitutions. II: About the role of one-sided context
- On the generative capacity of matrix insertion-deletion systems of small sum-norm
- Single semi-contextual insertion-deletion systems
- On decision problems concerning contextual insertions and deletions
- Space separating special Geffert normal form for succinct representation of star-controlled insertion-deletion systems
- Subregularly controlled insertion systems
- Matrix insertion-deletion systems
- Unavoidable sets and circular splicing languages
- On regularity of context-free languages
- Site-directed insertion: decision problems, maximality and minimality
This page was built for publication: Insertion languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q796994)
