The Unsolvability of the Recognition of Linear Context-Free Languages
From MaRDI portal
Publication:5526126
DOI10.1145/321356.321365zbMath0148.00901OpenAlexW2063554457MaRDI QIDQ5526126
Publication date: 1966
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321356.321365
Related Items
On the closure properties of linear conjunctive languages. ⋮ The theory of languages ⋮ The theory of languages ⋮ The interchange or pump (di)lemmas for context-free languages ⋮ Syntax checking either way ⋮ Unnamed Item ⋮ Cônes rationnels commutatifs ⋮ Unnamed Item ⋮ Ogden's lemma for nonterminal bounded languages ⋮ Formal grammars for turn-bounded deterministic context-free languages ⋮ Extended regular expressions of star degree at most two ⋮ On a language without star ⋮ Kernels of Sub-classes of Context-Free Languages ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ ON THE DESCRIPTIONAL COMPLEXITY OF METALINEAR CD GRAMMAR SYSTEMS ⋮ Sequential syntactical decoding ⋮ Extended regular expressions of arbitrary star degrees ⋮ Unnamed Item ⋮ Syntax checking either way ⋮ Comparing language operations ⋮ Control sets on context-free grammar forms ⋮ Produit dans le cône rationnel engendre par D ⋮ UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES ⋮ Syntactic operators on full semiAFLs ⋮ Finite-turn checking automata ⋮ Ambiguity and decision problems for local adjunct languages ⋮ Partial commutations and faithful rational transductions ⋮ Extended automata-like regular expressions of star degree at most (2,1) ⋮ A note on undecidable properties of formal languages
