Highly Undecidable Problems For Infinite Computations

DOI10.1051/ITA/2009001zbMATH Open1171.03024arXiv0901.0373OpenAlexW2962866237MaRDI QIDQ3625697FDOQ3625697

Authors: Olivier Finkel 

Publication date: 6 May 2009

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Abstract: We show that many classical decision problems about 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are $P{i}_2^1$-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 $P{i}_2^1$-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.

Full work available at URL: https://arxiv.org/abs/0901.0373

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

zbMATH Keywords

complete setsinfinite computationsarithmetical hierarchydecision problemsanalytical hierarchyhighly undecidable problems1-counter-automata2-tape automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Undecidability and degrees of sets of sentences (03D35)

Cites Work

• A theory of timed automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Classical recursion theory. The theory of functions and sets of natural numbers
• \(\omega\)-computations on Turing machines
• Classical recursion theory. Vol. II
• Borel ranks and Wadge degrees of context free $\omega$-languages
• Nondeterministic Ω-Computations and the Analytical Hierarchy
• On the Accepting Power of 2-Tape Büchi Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Undecidable Problems About Timed Automata
• Decision problems forω-automata
• Synchronized rational relations of finite and infinite words
• \(X\)-automata on \(\omega\)-words
• \(\omega\)-computations on deterministic pushdown machines
• The equivalence problem of multitape finite automata
• Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
• Title not available (Why is that?)
• Proof systems for infinite behaviours
• Title not available (Why is that?)
• Topological properties of omega context-free languages
• Relations rationnelles infinitaires
• On verifying that a concurrent program satisfies a nondeterministic specification
• Title not available (Why is that?)
• Ambiguity in omega context free languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Borel hierarchy and omega context free languages.
• Topology and ambiguity in \(\omega\)-context free languages
• Classical and effective descriptive complexities of \(\omega \)-powers
• Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
• On the Topological Complexity of Infinitary Rational Relations
• ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES

Cited In (20)

• Infinity problems and countability problems for \(\omega \)-automata
• Nondeterministic Ω-Computations and the Analytical Hierarchy
• On Büchi one-counter automata
• Two Effective Properties of ω-Rational Functions
• Highly Undecidable Problems about Recognizability by Tiling Systems
• Locally finite \(\omega\)-languages and effective analytic sets have the same topological complexity
• Infinite games specified by 2-tape automata
• Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
• Undecidability of infinite Post correspondence problem for instances of size 8
• Reasoning about infinite computations
• Undecidability of infinite post correspondence problem for instances of Size 9
• Title not available (Why is that?)
• Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
• Decision problems for recognizable languages of infinite pictures
• Undecidability and finite automata
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• On the high complexity of Petri nets \(\omega \)-languages
• Some problems in automata theory which depend on the models of set theory
• Logical aspects of the lexicographic order on 1-counter languages
• The Wadge hierarchy of Petri nets \(\omega\)-languages

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)