Scattered versus context-sensitive rewriting

DOI10.1007/BF00263503zbMath0664.68078OpenAlexW2011022861MaRDI QIDQ1115634

Jakob Gonczarowski, Manfred K. Warmuth

Publication date: 1989

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00263503

zbMATH Keywords

context-sensitive languagescontext-sensitive rewritingscattered context languagesscattered grammarsscattered rewriting

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Petri net algorithms in the theory of matrix grammars ⋮ CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages ⋮ Canonical scattered context generators of sentences with their parses ⋮ On the descriptional complexity of some rewriting mechanisms regulated by context conditions ⋮ Membership for growing context-sensitive grammars is polynomial ⋮ Scattered context grammars that erase nonterminals in a generalized \(k\)-limited way ⋮ On representing recursively enumerable languages by internal contextual languages

This page was built for publication: Scattered versus context-sensitive rewriting