What makes some language theory problems undecidable

DOI10.1016/S0022-0000(70)80018-6zbMath0198.03001MaRDI QIDQ2540268

Juris Hartmanis, John E. Hopcrofts

Publication date: 1970

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

languages, automata, networks

Related Items

On Boolean closed full trios and rational Kripke frames ⋮ On some decision questions concerning pushdown machines ⋮ The emptiness problem for valence automata over graph monoids ⋮ Prefix and equality languages of rational functions are co-context-free ⋮ Recursivite et cônes rationnels fermés par intersection ⋮ On counting functions and slenderness of languages ⋮ Existential Definability over the Subword Ordering ⋮ Generalizing input-driven languages: theoretical and practical benefits ⋮ Unnamed Item ⋮ Decidability of Skolem matrix emptiness problem entails constructability of exact regular expression ⋮ On the finite-valuedness problem for sequential machines ⋮ Counter machines, Petri nets, and consensual computation ⋮ VERIFICATION IN QUEUE-CONNECTED MULTICOUNTER MACHINES ⋮ Bounded AFLs ⋮ On the pre-AFL of \([lg\;n\) space and related families of languages] ⋮ Remarks on blind and partially blind one-way multicounter machines ⋮ Input-driven multi-counter automata ⋮ On simple generators of recursively enumerable languages ⋮ Substitution and bounded languages ⋮ Theory of formal grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• An Approach to a Unified Theory of Automata
• A note on undecidable properties of formal languages
• One-way stack automata
• Studies in abstract families of languages