Nonterminal complexity of programmed grammars.

DOI10.1016/S0304-3975(02)00656-4zbMath1044.68076MaRDI QIDQ1401269

Henning Fernau

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Descriptional complexityProgrammed grammarsMatrix grammarsNonterminal complexityRegulated rewriting

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (15)

Parsimonious computational completeness ⋮ One-Sided Random Context Grammars with Leftmost Derivations ⋮ The power of programmed grammars with graphs from various classes ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ Nonterminal complexity of one-sided random context grammars ⋮ Workspace theorems for regular-controlled grammars ⋮ Language classes generated by tree controlled grammars with bounded nonterminal complexity ⋮ Nonterminal complexity of tree controlled grammars ⋮ On the computational completeness of generalized forbidding matrix grammars ⋮ Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity ⋮ Improved descriptional complexity results on generalized forbidding grammars ⋮ Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion ⋮ Generalized forbidding matrix grammars and their membrane computing perspective ⋮ On the computational completeness of matrix simple semi-conditional grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Remarks on blind and partially blind one-way multicounter machines
• Petri net algorithms in the theory of matrix grammars
• Unconditional transfer in regulated rewriting
• Generative power of three-nonterminal scattered context grammars
• Regulated grammars under leftmost derivation
• Syntactic complexity of scattered context grammars
• A hierarchy between context-free and context-sensitive languages
• Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages
• Six nonterminals are enough for generating each r.e. language by a matrix grammar
• Accepting grammars with regulation
• ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS
• Programmed Grammars and Classes of Formal Languages
• Machines, computations, and universality. 3rd international conference, MCU 2001, Chişinǎu, Moldova, May 23--27, 2001. Proceedings

This page was built for publication: Nonterminal complexity of programmed grammars.