Insertion languages

DOI10.1016/0020-0255(83)90023-3zbMath0544.68049OpenAlexW2914627413MaRDI QIDQ796994

David Haussler

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

zbMATH Keywords

equivalencedeterminismregular expressionsambiguitycontext-free languagesword problemsChurch-Rosser systemsgeneralized Dyck languagesinsertion languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, etc. in computability and recursion theory (03D40)

Related Items (23)

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

This page was built for publication: Insertion languages