On the descriptional complexity of scattered context grammars

DOI10.1016/J.TCS.2008.10.017zbMath1161.68022OpenAlexW1978202723MaRDI QIDQ1001907

Tomáš Masopust

Publication date: 19 February 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.017

zbMATH Keywords

descriptional complexityscattered context grammar

Mathematics Subject Classification ID

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

Related Items (3)

Scattered context grammars generate any recursively enumerable language with two nonterminals ⋮ Nonterminal complexity of one-sided random context grammars ⋮ Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

Cites Work

• Terminating left-hand sides of scattered context productions M. Nivat
• Generative power of three-nonterminal scattered context grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Scattered context grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the descriptional complexity of scattered context grammars