Insertion languages
From MaRDI portal
Publication:796994
DOI10.1016/0020-0255(83)90023-3zbMath0544.68049OpenAlexW2914627413MaRDI QIDQ796994
Publication date: 1983
Published in: Information Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0255(83)90023-3
equivalencedeterminismregular expressionsambiguitycontext-free languagesword problemsChurch-Rosser systemsgeneralized Dyck languagesinsertion languages
Formal languages and automata (68Q45) Word problems, etc. in computability and recursion theory (03D40)
Related Items
On the computational completeness of graph-controlled insertion-deletion systems with binary sizes ⋮ Insertion-deletion systems with substitutions I ⋮ Modelling DNA and RNA secondary structures using matrix insertion-deletion systems ⋮ ON THE AMBIGUITY OF INSERTION SYSTEMS ⋮ A characterization of (regular) circular languages generated by monotone complete splicing systems ⋮ Outfix-guided insertion ⋮ On the generative capacity of matrix insertion-deletion systems of small sum-norm ⋮ Single semi-contextual insertion-deletion systems ⋮ Unnamed Item ⋮ On Succinct Description of Certain Context-Free Languages by Ins-Del and Matrix Ins-Del Systems ⋮ Unnamed Item ⋮ On path-controlled insertion-deletion systems ⋮ On Basic Properties of Jumping Finite Automata ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Universal insertion grammars of size two ⋮ Matrix insertion-deletion systems ⋮ Unavoidable sets and circular splicing languages ⋮ Outfix-Guided Insertion ⋮ On bonded sequential and parallel insertion systems ⋮ On regularity of context-free languages ⋮ Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems ⋮ Two Results on Discontinuous Input Processing ⋮ Generating and accepting P systems with minimal left and right insertion and deletion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On regularity of context-free languages
- On the enlargement of the class of regular languages by the shuffle closure
- The power of synchronizing operations on strings
- Infinite regular Thue systems
- Some definitional suggestions for automata theory
- Une généralisation des ensembles de Dyck
- A characterization of context-free languages
- On theories with a combinatorial definition of 'equivalence'
- Confluent and Other Types of Thue Systems
- Software Descriptions with Flow Expressions
- A note on undecidable properties of formal languages
- Full AFLs and nested iterated substitution
- A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free
- A variant of a recursively unsolvable problem
