Parsimonious computational completeness
From MaRDI portal
Publication:832917
DOI10.1007/978-3-030-81508-0_2OpenAlexW3192794283MaRDI QIDQ832917
Publication date: 25 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-81508-0_2
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Mathematical Theory of Communication
- Computational power of insertion-deletion (P) systems with rules of size two
- Recent developments on insertion-deletion systems
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- A variant of random context grammars: Semi-conditional grammars
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- Comment on the paper 'Error detection in formal languages'
- Small deterministic Turing machines
- DNA computing: Arrival of biological mathematics
- Unconditional transfer in regulated rewriting
- Nonterminal complexity of programmed grammars.
- On the computational power of insertion-deletion systems
- New nonterminal complexity results for semi-conditional grammars
- On path-controlled insertion-deletion systems
- Context-free insertion-deletion systems
- Computational completeness of simple semi-conditional insertion-deletion systems
- Universal insertion grammars of size two
- On the power of generalized forbidding insertion-deletion systems
- Insertion-deletion with substitutions. II
- Generalized forbidding matrix grammars and their membrane computing perspective
- Insertion-deletion systems with substitutions. I
- A general framework for sequential grammars with control mechanisms
- Descriptional complexity of matrix simple semi-conditional grammars
- On matrix ins-del systems of small sum-norm
- On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
- Universal matrix insertion grammars with small size
- Graph-controlled insertion-deletion systems generating language classes beyond linearity
- On the Complexity Landscape of the Domination Chain
- The Complexity of Small Universal Turing Machines: A Survey
- Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
- Parikh Images of Matrix Ins-Del Systems
- Automata Studies. (AM-34)
- On certain formal properties of grammars
- Six nonterminals are enough for generating each r.e. language by a matrix grammar
- Insertion-Deletion Systems with One-Sided Contexts
- Normal forms for phrase-structure grammars
- How to Make Arbitrary Grammars Look Like Context-Free Grammars
- On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
- On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
- Universality of Tag Systems with P = 2
- Three models for the description of language
- Classes of languages and linear-bounded automata
- Formal Reductions of the General Combinatorial Decision Problem
- A variant of a recursively unsolvable problem
- Improved descriptional complexity results on generalized forbidding grammars
- Investigations on the power of matrix insertion-deletion systems with small sizes
This page was built for publication: Parsimonious computational completeness
