Scattered context grammars that erase nonterminals in a generalized k-limited way

DOI10.1007/S00236-008-0081-4MaRDI QIDQ1006344zbMATH OpenOpenAlexFDO

Authors Alexander Meduna, Jiří Techet

Publication date 20 March 2009

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-008-0081-4

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations
• Two power-decreasing derivation restrictions in generalized scattered context grammars
• Terminating left-hand sides of scattered context productions M. Nivat
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement
• On the descriptional complexity of scattered context grammars

Cites work

• scientific article; zbMATH DE number 3470036 (Why is no real title available?)
• scientific article; zbMATH DE number 1330031 (Why is no real title available?)
• scientific article; zbMATH DE number 2013189 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• A note on scattered context grammars
• Canonical scattered context generators of sentences with their parses
• Leftmost derivations of propagating scattered context grammars: a new proof
• Maximal and Minimal Scattered Context Rewriting
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Scattered context grammars
• Scattered versus context-sensitive rewriting

Cited in

(4)

• An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations
• Two power-decreasing derivation restrictions in generalized scattered context grammars
• Terminating left-hand sides of scattered context productions M. Nivat
• Workspace theorems for regular-controlled grammars

This page was built for publication: Scattered context grammars that erase nonterminals in a generalized \(k\)-limited way

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