On the generative power of regular pattern grammars
From MaRDI portal
Publication:794441
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
recursively enumerable languagecontext-sensitive languagesgenerative powerEOL languagesregular pattern grammars
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
