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)
Related Items (36)
Error tolerance for the recognition of faulty strings in a regulated grammar using fuzzy sets ⋮ One-Sided Random Context Grammars with Leftmost Derivations ⋮ On the generating power of regularly controlled bidirectional grammars ⋮ Pumping lemmas for the control language hierarchy ⋮ Shuffle on trajectories: Syntactic constraints ⋮ Computing by observing: simple systems and simple observers ⋮ Multipass precedence analysis ⋮ Program Schemes with Deep Pushdown Storage ⋮ Nonterminal complexity of programmed grammars. ⋮ Iterated linear control and iterated one-turn pushdowns ⋮ 2DST mappings of languages and related problems ⋮ On Alternating Phrase-Structure Grammars ⋮ Upper bounds on recognition of a hierarchy of non-context-free languages ⋮ State grammars with stores ⋮ On coupled languages and translations ⋮ Deep pushdown automata ⋮ Locally finite languages ⋮ Left-forbidding cooperating distributed grammar systems ⋮ On state-alternating context-free grammars ⋮ Size, index, and context-sensitivity of controlled partition grammars ⋮ ON ALTERNATING PHRASE-STRUCTURE GRAMMARS ⋮ A unified approach to the generation and the acception of formal languages ⋮ Fast recognition of context-sensitive structures ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ An algebraic technique for context-sensitive parsing ⋮ An infinite hierarchy of language families generated by scattered context grammars with \(n\)-limited derivations ⋮ AFL with the semilinear property ⋮ On the power of deep pushdown stacks ⋮ GENERATION OF LANGUAGES BY REWRITING SYSTEMS THAT RESEMBLE AUTOMATA ⋮ 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 ⋮ A note on Parikh maps, abstract languages, and decision problems ⋮ Covering-languages of grammars ⋮ Fuzzy state grammar and fuzzy deep pushdown automaton
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
This page was built for publication: A hierarchy between context-free and context-sensitive languages
