A helpful result for proving inherent ambiguity
From MaRDI portal
Publication:5565120
DOI10.1007/BF01694004zbMath0175.27802OpenAlexW1964431911WikidataQ29013399 ScholiaQ29013399MaRDI QIDQ5565120
No author found.
Publication date: 1968
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01694004
Related Items
The chop of languages, A pumping lemma for real-time deterministic context-free languages, Sur la structure des langages algébriques, Ogden Property for Linear Displacement Context-Free Grammars, On languages satisfying “interchange Lemma”, The Generative Power of Probabilistic and Weighted Context-Free Grammars, Accepting splicing systems with permitting and forbidding words, Algebraic languages and polyominoes enumeration, Remarks on Privileged Words, The interchange or pump (di)lemmas for context-free languages, An ambiguity hierarchy of weighted context-free grammars, Unnamed Item, Unnamed Item, On grammatical complexity of a class of attractors, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Comparisons of Parikh's condition to other conditions for context-free languages, Automatic winning shifts, Ogden's lemma for nonterminal bounded languages, Iteration theorems for families of strict deterministic languages, Langages sur des alphabets infinis, Two iteration theorems for the LL(k) languages, Inverse star, borders, and palstars, Unnamed Item, Independance forte de certaines opérations, Coordinated pair systems ; part II : sparse structure of Dyck words and Ogden's lemma, Re-examining regular expressions with backreferences, Permutations are not context-free: An application of the interchange lemma, A pushdown automaton or a context-free grammar - which is more economical?, Queues, stacks, and transcendentality at the transition to chaos, A note on the sufficiency of Sokolowski's criterion for context-free languages, Unnamed Item, A complexity analysis of the elementary cellular automaton of rule 122, On satisfying the LL-iteration theorem, Prefix-suffix duplication, Quantum Pushdown Automata with Garbage Tape, Unambiguous Boolean grammars, Slender Siromoney matrix languages, Additive number theory via automata theory, On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids, Le cylindre des langages linéaires, The Strong, Weak, and Very Weak Finite Context and Kernel Properties, On the size complexity of hybrid networks of evolutionary processors, On languages with a certain prefix property, Two iteration theorems for some families of languages, The Turing degree of the inherent ambiguity problem for context-free languages, An ambiguity hierarchy of weighted context-free grammars, Uniformly erasable AFL, Monoides syntactiques des langages algébriques, Tree adjunct grammars, The inclusion of the substitution closure of linear and one-counter languages in the largest sub-AFL of the family of algebraic languages is proper, A strong pumping lemma for context-free languages, Ogden's lemma, multiple context-free grammars, and the control language hierarchy, A simplified proof of Parikh's theorem, Complexity metatheorems for context-free grammar problems, Langages algébriques, paires iterantes et transductions rationnelles, Générateurs algébriques et systèmes de paires iterantes, ON SOME PROPERTIES OF THE LANGUAGE OF 2-COLLAPSING WORDS, A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES, Comparisons between some pumping conditions for context-free languages, Sur une propriété d'itération des langages algébriques déterministes, Growth and ergodicity of context-free languages II: The linear case, Left-derivation bounded languages, Theory of formal grammars, On context-free and Szilard languages, Sublogarithmic ambiguity, A note onxy languages, Coverability, Termination, and Finiteness in Recursive Petri Nets, Sums of Palindromes: an Approach via Automata, On the growth of linear languages
Cites Work
