Highly Undecidable Problems For Infinite Computations
From MaRDI portal
Publication:3625697
Abstract: We show that many classical decision problems about 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are -complete, hence located at the second level of the analytical hierarchy, and "highly undecidable". In particular, the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are all -complete for context-free omega-languages or for infinitary rational relations. Topological and arithmetical properties of 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are also highly undecidable. These very surprising results provide the first examples of highly undecidable problems about the behaviour of very simple finite machines like 1-counter automata or 2-tape automata.
Recommendations
- Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
- The Complexity of Infinite Computations In Models of Set Theory
- Decision problems for Turing machines
- Decision problems for recognizable languages of infinite pictures
- Some problems in automata theory which depend on the models of set theory
Cites work
- scientific article; zbMATH DE number 4019040 (Why is no real title available?)
- scientific article; zbMATH DE number 4039337 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3501028 (Why is no real title available?)
- scientific article; zbMATH DE number 3578343 (Why is no real title available?)
- scientific article; zbMATH DE number 3602692 (Why is no real title available?)
- scientific article; zbMATH DE number 722611 (Why is no real title available?)
- scientific article; zbMATH DE number 1142314 (Why is no real title available?)
- scientific article; zbMATH DE number 1948507 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- scientific article; zbMATH DE number 871238 (Why is no real title available?)
- scientific article; zbMATH DE number 2206109 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- A theory of timed automata
- Ambiguity in omega context free languages
- Borel hierarchy and omega context free languages.
- Borel ranks and Wadge degrees of context free $\omega$-languages
- Classical and effective descriptive complexities of \(\omega \)-powers
- Classical recursion theory. The theory of functions and sets of natural numbers
- Classical recursion theory. Vol. II
- Decision problems forω-automata
- Nondeterministic Ω-Computations and the Analytical Hierarchy
- ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES
- On the Accepting Power of 2-Tape Büchi Automata
- On the Topological Complexity of Infinitary Rational Relations
- On verifying that a concurrent program satisfies a nondeterministic specification
- Proof systems for infinite behaviours
- Relations rationnelles infinitaires
- Synchronized rational relations of finite and infinite words
- The equivalence problem of multitape finite automata
- Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
- Topological properties of omega context-free languages
- Topology and ambiguity in \(\omega\)-context free languages
- Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
- Undecidable Problems About Timed Automata
- \(L(A)=L(B)\)? decidability results from complete formal systems
- \(X\)-automata on \(\omega\)-words
- \(\omega\)-computations on Turing machines
- \(\omega\)-computations on deterministic pushdown machines
Cited in
(20)- scientific article; zbMATH DE number 3845565 (Why is no real title available?)
- Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
- Logical aspects of the lexicographic order on 1-counter languages
- Highly Undecidable Problems about Recognizability by Tiling Systems
- Undecidability and finite automata
- Undecidability of infinite post correspondence problem for instances of Size 9
- The Wadge hierarchy of Petri nets \(\omega\)-languages
- On Büchi one-counter automata
- Locally finite \(\omega\)-languages and effective analytic sets have the same topological complexity
- On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
- On the high complexity of Petri nets \(\omega \)-languages
- Nondeterministic Ω-Computations and the Analytical Hierarchy
- Infinity problems and countability problems for \(\omega \)-automata
- Undecidability of infinite Post correspondence problem for instances of size 8
- Infinite games specified by 2-tape automata
- Two Effective Properties of ω-Rational Functions
- Some problems in automata theory which depend on the models of set theory
- Decision problems for recognizable languages of infinite pictures
- Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
- Reasoning about infinite computations
This page was built for publication: Highly Undecidable Problems For Infinite Computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3625697)
