An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations

DOI10.1016/J.TCS.2008.12.013zbMath1168.68027OpenAlexW2045903524MaRDI QIDQ1019169

Alexander Meduna, Jiří Techet

Publication date: 28 May 2009

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

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

zbMATH Keywords

scattered context grammarsgenerative powerinfinite hierarchy of language familiesleft derivation restrictionunordered scattered context grammars

Mathematics Subject Classification ID

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

Cites Work

• Petri net algorithms in the theory of matrix grammars
• Scattered context grammars
• A hierarchy between context-free and context-sensitive languages
• A note on scattered context grammars
• Maximal and Minimal Scattered Context Rewriting
• Some restrictive devices for context-free grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations