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

DOI10.1080/00207168408803399MaRDI QIDQ3347322zbMATH OpenOpenAlexFDO

Authors 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

recursively enumerable languageregular languageslinear languageappearance checkingcontext-free matrix grammarprogrammed grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1738664
• scientific article; zbMATH DE number 1738663
• Nonterminal complexity of programmed grammars.
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Scattered context grammars generate any recursively enumerable language with two nonterminals

Cites work

• scientific article; zbMATH DE number 3548460 (Why is no real title available?)
• On the effect of the finite index restriction on several families of grammars
• Programmed Grammars and Classes of Formal Languages

Cited in

(16)

• scientific article; zbMATH DE number 1738664 (Why is no real title available?)
• scientific article; zbMATH DE number 3854449 (Why is no real title available?)
• Parsimonious computational completeness
• Six-Nonterminal multi-sequential grammars characterize the family of recursively enumerable languages
• A guide to membrane computing.
• scientific article; zbMATH DE number 1738663 (Why is no real title available?)
• Investigations on the power of matrix insertion-deletion systems with small sizes
• scientific article; zbMATH DE number 3974325 (Why is no real title available?)
• Generalized forbidding matrix grammars and their membrane computing perspective
• From regulated rewriting to computing with membranes: collapsing hierarchies
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Nonterminal complexity of tree controlled grammars
• Nonterminal complexity of programmed grammars.
• On the computational completeness of generalized forbidding matrix grammars
• scientific article; zbMATH DE number 617134 (Why is no real title available?)

This page was built for publication: Six nonterminals are enough for generating each r.e. language by a matrix grammar

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3347322)