Scattered context grammars
From MaRDI portal
Publication:2532394
DOI10.1016/S0022-0000(69)80015-2zbMath0174.02801MaRDI QIDQ2532394
Sheila A. Greibach, John E. Hopcrofts
Publication date: 1969
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (54)
Syntactic complexity of scattered context grammars ⋮ Quasi-realtime languages ⋮ On parsing coupled-context-free languages ⋮ LR(k)-coupled-context-free grammars ⋮ The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index ⋮ One-Sided Random Context Grammars: A Survey ⋮ Multi-stack-counter languages ⋮ Scattered context grammars generate any recursively enumerable language with two nonterminals ⋮ CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages ⋮ On the degree of scattered context-sensitivity. ⋮ On elimination of erasing rules from E0S grammars ⋮ Unnamed Item ⋮ Context-free like restrictions on selective rewriting ⋮ Lexicalized non-local MCTAG with dominance links is NP-complete ⋮ Unnamed Item ⋮ Simple restriction in context-free rewriting ⋮ Independent parallelism in finite copying parallel rewriting systems ⋮ Parsing and generation with static discontinuity grammars ⋮ Fast uniform analysis of Coupled-Context-Free languages ⋮ Unnamed Item ⋮ Canonical scattered context generators of sentences with their parses ⋮ Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete ⋮ On the complexity of finite, pushdown, and stack automata ⋮ On the descriptional complexity of some rewriting mechanisms regulated by context conditions ⋮ On coupled languages and translations ⋮ Size, index, and context-sensitivity of controlled partition grammars ⋮ Membership for growing context-sensitive grammars is polynomial ⋮ Degree-languages: A new concept of acceptance ⋮ Control sets on context-free grammar forms ⋮ On the descriptional complexity of scattered context grammars ⋮ Scattered context grammars that erase nonterminals in a generalized \(k\)-limited way ⋮ A simultaneous reduction of several measures of descriptional complexity in scattered context grammars ⋮ An observation on scattered grammars ⋮ An algebraic technique for context-sensitive parsing ⋮ An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations ⋮ Priorities on context conditions in rewriting systems ⋮ Rewriting systems with a clocking mechanism ⋮ On regularity of context-free languages ⋮ A hierarchy between context-free and context-sensitive languages ⋮ Manipulating derivation forests by scheduling techniques ⋮ A note on scattered context grammars ⋮ Terminating left-hand sides of scattered context productions M. Nivat ⋮ One-sided random context grammars ⋮ Outils et résultats pour les transducteurs boustrophédons ⋮ Direction controlled programmed grammars ⋮ Absolutely parallel grammars and two-way finite-state transducers ⋮ Algorithms for producing grammars from sample derivations: a common problem of formal language theory and developmental biology ⋮ A note on leftmost restricted random context grammars ⋮ Some concepts for languages more powerful than context-free ⋮ Normal forms for context-sensitive grammars ⋮ Theory of formal grammars ⋮ Expressiveness and complexity of regular pure two-dimensional context-free languages ⋮ Modelling economic processes by means of formal grammars: A survey of results at the middle of 1981 ⋮ Chart parsing of scattered context grammars
Cites Work
This page was built for publication: Scattered context grammars
