CD grammar systems with two propagating scattered context components characterize the family of context sensitive languages

MaRDI QIDQ5016368zbMATH OpenFDO

Authors Alexander Meduna, Jakub Martiško

Publication date 13 December 2021

Full work available at URL https://arxiv.org/abs/1708.06467, http://eptcs.web.cse.unsw.edu.au/paper.cgi?AFL2017.17

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 878951
• On growing context-sensitive languages
• On the descriptional complexity of scattered context grammars
• An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations
• Scattered context grammars with one non-context-free production are computationally complete

Cites work

• Classes of languages and linear-bounded automata
• scientific article; zbMATH DE number 4135414 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 745858 (Why is no real title available?)
• Regulated grammars and automata
• Scattered context grammars

Cited in

(1)

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

This page was built for publication: CD grammar systems with two propagating scattered context components characterize the family of context sensitive languages

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