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

DOI10.1080/00207168408803399zbMATH Open0558.68065OpenAlexW112931193MaRDI QIDQ3347322FDOQ3347322

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

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

zbMATH Keywords

recursively enumerable languageregular languageslinear languageappearance checkingcontext-free matrix grammarprogrammed grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Programmed Grammars and Classes of Formal Languages
• Title not available (Why is that?)
• On the effect of the finite index restriction on several families of grammars

Cited In (16)

• Title not available (Why is that?)
• Parsimonious computational completeness
• Six-Nonterminal multi-sequential grammars characterize the family of recursively enumerable languages
• Title not available (Why is that?)
• A guide to membrane computing.
• Investigations on the power of matrix insertion-deletion systems with small sizes
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

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)