A note on undecidable properties of formal languages
From MaRDI portal
Publication:5538917
DOI10.1007/BF01691341zbMath0157.01902OpenAlexW2101036675MaRDI QIDQ5538917
Publication date: 1968
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01691341
Related Items
On languages satisfying “interchange Lemma” ⋮ On the equivalence and containment problems for context-free languages ⋮ Carathéodory extensions of subclasses of regular languages ⋮ On the equivalence and containment problems for context-free languages ⋮ Parallel complexity of logical query programs ⋮ Dynamical recognizers: real-time language recognition by analog computers ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Context-Freeness of Parsing Expression Languages is Undecidable ⋮ On some transducer equivalence problems for families of languages ⋮ Linear automata with translucent letters and linear context-free trace languages ⋮ On series-parallel pomset languages: rationality, context-freeness and automata ⋮ Unnamed Item ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Reversal-bounded multipushdown machines ⋮ On the equivalence, containment, and covering problems for the regular and context-free languages ⋮ On the pre-AFL of \([lg\;n\) space and related families of languages] ⋮ Complexity metatheorems for context-free grammar problems ⋮ Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract) ⋮ Derivation-bounded languages ⋮ What makes some language theory problems undecidable ⋮ Time-bounded grammars and their languages ⋮ A logic for document spanners ⋮ On families of full trios containing counter machine languages ⋮ Theory of formal grammars ⋮ Insertion languages ⋮ Characterization and complexity results on jumping finite automata
Uses Software
Cites Work
