Insertion languages
DOI10.1016/0020-0255(83)90023-3zbMATH Open0544.68049OpenAlexW2914627413MaRDI QIDQ796994FDOQ796994
Authors: 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
Recommendations
equivalenceambiguitycontext-free languagesdeterminismregular expressionsword problemsChurch-Rosser systemsgeneralized Dyck languagesinsertion languages
Formal languages and automata (68Q45) Word problems, etc. in computability and recursion theory (03D40)
Cites Work
- Title not available (Why is that?)
- A variant of a recursively unsolvable problem
- On theories with a combinatorial definition of 'equivalence'
- Title not available (Why is that?)
- Title not available (Why is that?)
- Software Descriptions with Flow Expressions
- The power of synchronizing operations on strings
- Full AFLs and nested iterated substitution
- A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free
- On regularity of context-free languages
- Some definitional suggestions for automata theory
- A note on undecidable properties of formal languages
- Une généralisation des ensembles de Dyck
- Confluent and Other Types of Thue Systems
- Title not available (Why is that?)
- Infinite regular Thue systems
- On the enlargement of the class of regular languages by the shuffle closure
- A characterization of context-free languages
Cited In (33)
- Generating and accepting P systems with minimal left and right insertion and deletion
- On path-controlled insertion-deletion systems
- On basic properties of jumping finite automata
- Single semi-contextual insertion-deletion systems
- Insertion-deletion systems with substitutions. I
- Matrix insertion-deletion systems
- On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
- On the ambiguity of insertion systems
- Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
- Two results on discontinuous input processing
- Decidability questions for insertion systems and related models
- Insertion-deletion with substitutions. II: About the role of one-sided context
- Universal insertion grammars of size two
- Outfix-guided insertion (extended abstract)
- On succinct description of certain context-free languages by ins-del and matrix ins-del systems
- On the generative capacity of matrix insertion-deletion systems of small sum-norm
- Title not available (Why is that?)
- On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
- On regularity of context-free languages
- Aspects of Molecular Computing
- Context insertions
- Site-directed insertion: language equations and decision problems
- Site-directed insertion: decision problems, maximality and minimality
- Outfix-guided insertion
- 1-normal DRA for insertion languages
- A characterization of (regular) circular languages generated by monotone complete splicing systems
- On decision problems concerning contextual insertions and deletions
- Word-paired insertions of languages
- Title not available (Why is that?)
- Unavoidable sets and circular splicing languages
- Title not available (Why is that?)
- Descriptional complexity of graph-controlled insertion-deletion systems
- On bonded sequential and parallel insertion systems
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)