Parsimonious computational completeness
type: Item
instance of: scholarly article
title: Parsimonious computational completeness
DOI: 10.1007/978-3-030-81508-0_2
author: Henning Fernau
publication date: 2022-03-25T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7498712
zbMATH Keywords: normal forms
zbMATH Keywords: computational completeness
zbMATH Keywords: descriptional complexity
MaRDI profile type: Publication
full work available at URL: 978-3-030-81508-0 2
OpenAlex ID: W3192794283
cites work: On the Complexity Landscape of the Domination Chain
cites work: Three models for the description of language
cites work: On certain formal properties of grammars
cites work: Universality of Tag Systems with P = 2
cites work: Q3336722
cites work: Q3811726
cites work: The (generalized) Post correspondence problem with lists consisting of two words is decidable
cites work: Q4858934
cites work: Q3125170
cites work: Unconditional transfer in regulated rewriting
cites work: Q4530000
cites work: Nonterminal complexity of programmed grammars.
cites work: Q3178873
cites work: Q3517098
cites work: Parikh Images of Matrix Ins-Del Systems
cites work: New nonterminal complexity results for semi-conditional grammars
cites work: Improved descriptional complexity results on generalized forbidding grammars
cites work: Graph-controlled insertion-deletion systems generating language classes beyond linearity
cites work: On the computational completeness of graph-controlled insertion-deletion systems with binary sizes
cites work: On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes
cites work: Computational completeness of simple semi-conditional insertion-deletion systems
cites work: Investigations on the power of matrix insertion-deletion systems with small sizes
cites work: On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems
cites work: Q4623037
cites work: Descriptional complexity of matrix simple semi-conditional grammars
cites work: On matrix ins-del systems of small sum-norm
cites work: On path-controlled insertion-deletion systems
cites work: On the power of generalized forbidding insertion-deletion systems
cites work: Generalized forbidding matrix grammars and their membrane computing perspective
cites work: Universal matrix insertion grammars with small size
cites work: Q4939577
cites work: A general framework for sequential grammars with control mechanisms
cites work: Q4964013
cites work: Q4530001
cites work: Q3980380
cites work: Normal forms for phrase-structure grammars
cites work: Q3783607
cites work: DNA computing: Arrival of biological mathematics
cites work: Q4263694
cites work: Computational power of insertion-deletion (P) systems with rules of size two
cites work: Small deterministic Turing machines
cites work: Classes of languages and linear-bounded automata
cites work: Context-free insertion-deletion systems
cites work: Insertion-Deletion Systems with One-Sided Contexts
cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines
cites work: Q5590814
cites work: Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
cites work: The Complexity of Small Universal Turing Machines: A Survey
cites work: Six nonterminals are enough for generating each r.e. language by a matrix grammar
cites work: A variant of random context grammars: Semi-conditional grammars
cites work: Q4223673
cites work: Formal Reductions of the General Combinatorial Decision Problem
cites work: A variant of a recursively unsolvable problem
cites work: Comment on the paper 'Error detection in formal languages'
cites work: Q3953199
cites work: Q3051396
cites work: How to Make Arbitrary Grammars Look Like Context-Free Grammars
cites work: A Mathematical Theory of Communication
cites work: Automata Studies. (AM-34)
cites work: On the computational power of insertion-deletion systems
cites work: Recent developments on insertion-deletion systems
cites work: Universal insertion grammars of size two
cites work: Insertion-deletion systems with substitutions. I
cites work: Insertion-deletion with substitutions. II
cites work: Q3811725