Six nonterminals are enough for generating each r.e. language by a matrix grammar

DOI10.1080/00207168408803399zbMath0558.68065OpenAlexW112931193MaRDI QIDQ3347322

Gheorghe Păun

Publication date: 1984

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168408803399

zbMATH Keywords

regular languagesrecursively enumerable languagelinear languageappearance checkingcontext-free matrix grammarprogrammed grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Parsimonious computational completeness, From regulated rewriting to computing with membranes: collapsing hierarchies, Investigations on the power of matrix insertion-deletion systems with small sizes, Nonterminal complexity of programmed grammars., Language classes generated by tree controlled grammars with bounded nonterminal complexity, Six-Nonterminal multi-sequential grammars characterize the family of recursively enumerable languages, Nonterminal complexity of tree controlled grammars, Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity, Unnamed Item, Unnamed Item, Generalized forbidding matrix grammars and their membrane computing perspective, A guide to membrane computing.

Cites Work

• On the effect of the finite index restriction on several families of grammars
• Programmed Grammars and Classes of Formal Languages
• Unnamed Item