On the generative power of regular pattern grammars

DOI10.1007/BF00264281zbMath0541.68048OpenAlexW2062841770MaRDI QIDQ794441

H. C. M. Kleijn, Grzegorz Rozenberg

Publication date: 1983

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

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

zbMATH Keywords

recursively enumerable languagecontext-sensitive languagesgenerative powerEOL languagesregular pattern grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Prefix pushdown automata and their simplification ⋮ Middle quotients of linear languages ⋮ Applications of scheduling theory to formal language theory ⋮ Unnamed Item ⋮ A combinatorial property of EOL languages ⋮ Syntactic complexity of scattered context grammars ⋮ A pumping result for 2-context-free languages ⋮ Table systems with unconditional transfer ⋮ One-sided forbidding grammars and selective substitution grammars ⋮ Canonical scattered context generators of sentences with their parses ⋮ Six-Nonterminal multi-sequential grammars characterize the family of recursively enumerable languages ⋮ Hierarchy of k-context-free languages part 1 ⋮ Hierarchy ofk-context-free languages ⋮ Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete ⋮ Manipulating derivation forests by scheduling techniques ⋮ Simultaneously One-Turn Two-Pushdown Automata ⋮ Unnamed Item ⋮ Generative power of three-nonterminal scattered context grammars ⋮ Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages