On the Topological Complexity of Infinitary Rational Relations

DOI10.1051/ITA:2003016MaRDI QIDQ4825475zbMATH OpenOpenAlexFDO

Authors Olivier Finkel

Publication date 28 October 2004

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

Full work available at URL https://arxiv.org/abs/0803.1841, http://www.numdam.org/item?id=ITA_2003__37_2_105_0, https://eudml.org/doc/92716

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Hierarchies of computability and definability (03D55) Descriptive set theory (03E15)

Abstract: We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [Automates et Th'eorie Descriptive, Ph. D. Thesis, Universit'e Paris 7, March 1992].

Recommendations

• scientific article; zbMATH DE number 2040947
• Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
• Relations rationnelles infinitaires
• An example of \(\boldsymbol{\Pi}_3^0\)-complete infinitary rational relation
• scientific article; zbMATH DE number 2187727

Cites work

• scientific article; zbMATH DE number 1670852 (Why is no real title available?)
• scientific article; zbMATH DE number 4019040 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3780583 (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 219444 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1408334 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3255437 (Why is no real title available?)
• Computer science and the fine structure of Borel sets
• Decision problems forω-automata
• Descriptive set theory
• Logic, semigroups and automata on words
• Relations rationnelles infinitaires
• Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
• \(X\)-automata on \(\omega\)-words

Cited in

(9)

• ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES
• Highly Undecidable Problems For Infinite Computations
• An example of \(\boldsymbol{\Pi}_3^0\)-complete infinitary rational relation
• scientific article; zbMATH DE number 2187727 (Why is no real title available?)
• On the continuity set of an Omega rational function
• Automata, Borel functions and real numbers in Pisot base
• Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations
• scientific article; zbMATH DE number 2040947 (Why is no real title available?)
• scientific article; zbMATH DE number 762245 (Why is no real title available?)

This page was built for publication: On the Topological Complexity of Infinitary Rational Relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4825475)