A hierarchy between context-free and context-sensitive languages
From MaRDI portal
Publication:2544411
DOI10.1016/S0022-0000(70)80045-9zbMath0212.02705MaRDI QIDQ2544411
Publication date: 1970
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q45: Formal languages and automata
Related Items
Covering-languages of grammars, Pumping lemmas for the control language hierarchy, ON ALTERNATING PHRASE-STRUCTURE GRAMMARS, Fuzzy state grammar and fuzzy deep pushdown automaton, GENERATION OF LANGUAGES BY REWRITING SYSTEMS THAT RESEMBLE AUTOMATA, State grammars with stores, Locally finite languages, On state-alternating context-free grammars, Computing by observing: simple systems and simple observers, Left-forbidding cooperating distributed grammar systems, An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations, On the power of deep pushdown stacks, A note on Parikh maps, abstract languages, and decision problems, Shuffle on trajectories: Syntactic constraints, 2DST mappings of languages and related problems, Upper bounds on recognition of a hierarchy of non-context-free languages, A unified approach to the generation and the acception of formal languages, Fast recognition of context-sensitive structures, Multipass precedence analysis, Nonterminal complexity of programmed grammars., Error tolerance for the recognition of faulty strings in a regulated grammar using fuzzy sets, Normal forms for context-sensitive grammars, Theory of formal grammars, Deep pushdown automata, AFL with the semilinear property, A note on leftmost restricted random context grammars, Some concepts for languages more powerful than context-free, One-Sided Random Context Grammars with Leftmost Derivations, Program Schemes with Deep Pushdown Storage, On Alternating Phrase-Structure Grammars, Iterated linear control and iterated one-turn pushdowns, On the generating power of regularly controlled bidirectional grammars, On coupled languages and translations, Size, index, and context-sensitivity of controlled partition grammars, The complexity of the membership problem for some extensions of context-free languagest†, An algebraic technique for context-sensitive parsing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Scattered context grammars
- A note on asymmetry in phrase structure grammars
- Mappings which preserve context sensitive languages
- On Context-Free Languages
- Control sets on grammars
- Grammars with partial ordering of the rules
- Programmed Grammars and Classes of Formal Languages
- An analog of a theorem about context-free languages
- Classes of languages and linear-bounded automata
- Some remarks on state grammars and matrix grammars
