Nonterminal complexity of one-sided random context grammars

DOI10.1007/S00236-012-0150-6MaRDI QIDQ2428495zbMATH OpenOpenAlexFDO

Authors Alexander Meduna, Petr Zemek

Publication date 26 April 2012

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-012-0150-6

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• One-sided random context grammars
• One-sided random context grammars: a survey
• One-sided random context grammars with leftmost derivations
• One-sided random context grammars with a limited number of right random context rules
• scientific article; zbMATH DE number 637483
• Nonterminal complexity of tree controlled grammars
• scientific article; zbMATH DE number 1738663
• On the nonterminal complexity of tree controlled grammars
• Nonuniform complexity and the randomness of certain complete languages

Cites work

• A note on the descriptional complexity of semi-conditional grammars
• A simultaneous reduction of several measures of descriptional complexity in scattered context grammars
• Descriptional complexity of multi-parallel grammars
• scientific article; zbMATH DE number 5506908 (Why is no real title available?)
• scientific article; zbMATH DE number 1330031 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2201367 (Why is no real title available?)
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• Nonterminal complexity of programmed grammars.
• Normal forms for phrase-structure grammars
• On the descriptional complexity of scattered context grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• On the descriptional complexity of Watson-Crick automata
• One-sided random context grammars
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Scattered context grammars generate any recursively enumerable language with two nonterminals

Cited in

(8)

• One-sided random context grammars: a survey
• One-sided random context grammars with leftmost derivations
• One-sided random context grammars with a limited number of right random context rules
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• Linear grammars with one-sided contexts and their automaton representation
• Linear grammars with one-sided contexts and their automaton representation
• Improved descriptional complexity results on generalized forbidding grammars
• One-sided random context grammars

This page was built for publication: Nonterminal complexity of one-sided random context grammars

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