CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages

DOI10.1142/s0129054122410088OpenAlexW4293107880MaRDI QIDQ6114872

Alexander Meduna, Jakub Martiško, Zbyněk Křivka

Publication date: 15 August 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054122410088

zbMATH Keywords

scattered context grammarscontext sensitive languagesformal language theoryerasing rulesCD grammar systemspropagating rules

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scattered versus context-sensitive rewriting
• Scattered context grammars
• Classes of languages and linear-bounded automata

This page was built for publication: CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages