Parsimonious computational completeness
From MaRDI portal
Cites work
- A general framework for sequential grammars with control mechanisms
- A Mathematical Theory of Communication
- A variant of a recursively unsolvable problem
- A variant of random context grammars: Semi-conditional grammars
- An essay on general grammars
- Automata Studies. (AM-34)
- Classes of languages and linear-bounded automata
- Comment on the paper 'Error detection in formal languages'
- Computational completeness of simple semi-conditional insertion-deletion systems
- Computational power of insertion-deletion (P) systems with rules of size two
- Context-free insertion-deletion systems
- Descriptional complexity of matrix simple semi-conditional grammars
- DNA computing: Arrival of biological mathematics
- Formal Reductions of the General Combinatorial Decision Problem
- Generalized forbidding matrix grammars and their membrane computing perspective
- Graph-controlled insertion-deletion systems
- Graph-controlled insertion-deletion systems generating language classes beyond linearity
- How to Make Arbitrary Grammars Look Like Context-Free Grammars
- scientific article; zbMATH DE number 3646304 (Why is no real title available?)
- scientific article; zbMATH DE number 992006 (Why is no real title available?)
- scientific article; zbMATH DE number 3870627 (Why is no real title available?)
- scientific article; zbMATH DE number 4047162 (Why is no real title available?)
- scientific article; zbMATH DE number 4080938 (Why is no real title available?)
- scientific article; zbMATH DE number 4080939 (Why is no real title available?)
- scientific article; zbMATH DE number 3772981 (Why is no real title available?)
- scientific article; zbMATH DE number 21368 (Why is no real title available?)
- scientific article; zbMATH DE number 1236223 (Why is no real title available?)
- scientific article; zbMATH DE number 1342113 (Why is no real title available?)
- scientific article; zbMATH DE number 1738663 (Why is no real title available?)
- scientific article; zbMATH DE number 1738664 (Why is no real title available?)
- scientific article; zbMATH DE number 827969 (Why is no real title available?)
- scientific article; zbMATH DE number 1400024 (Why is no real title available?)
- scientific article; zbMATH DE number 3310089 (Why is no real title available?)
- Improved descriptional complexity results on generalized forbidding grammars
- Insertion-Deletion Systems with One-Sided Contexts
- Insertion-deletion systems with substitutions. I
- Insertion-deletion with substitutions. II
- Investigations on the power of matrix insertion-deletion systems with small sizes
- New nonterminal complexity results for semi-conditional grammars
- Nonterminal complexity of programmed grammars.
- Normal forms for phrase-structure grammars
- On certain formal properties of grammars
- On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
- On matrix ins-del systems of small sum-norm
- On path-controlled insertion-deletion systems
- On the complexity landscape of the domination chain
- On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
- On the computational power of insertion-deletion systems
- On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
- On the power of generalized forbidding insertion-deletion systems
- Parikh images of matrix ins-del systems
- Properties of language classes between linear and context-free
- Recent developments on insertion-deletion systems
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
- Six nonterminals are enough for generating each r.e. language by a matrix grammar
- Small deterministic Turing machines
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- The Complexity of Small Universal Turing Machines: A Survey
- Three models for the description of language
- Unconditional transfer in regulated rewriting
- Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
- Universal insertion grammars of size two
- Universal matrix insertion grammars with small size
- Universality of Tag Systems with P = 2
Cited in
(4)
This page was built for publication: Parsimonious computational completeness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832917)
