On the continuity set of an Omega rational function
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 183-196.

In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function $f$ has at least one point of continuity and that its continuity set $C\left(f\right)$ cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed. Furthermore we prove that any rational ${\Pi }_{2}^{0}$-subset of ${\Sigma }^{\omega }$ for some alphabet $\Sigma$ is the continuity set $C\left(f\right)$ of an $\omega$-rational synchronous function $f$ defined on ${\Sigma }^{\omega }$.

DOI : https://doi.org/10.1051/ita:2007050
Classification : 68Q05,  68Q45,  03D05
Mots clés : infinitary rational relations, omega rational functions, topology, points of continuity, decision problems, omega rational languages, omega context-free languages
@article{ITA_2008__42_1_183_0,
author = {Carton, Olivier and Finkel, Olivier and Simonnet, Pierre},
title = {On the continuity set of an {Omega} rational function},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {183--196},
publisher = {EDP-Sciences},
volume = {42},
number = {1},
year = {2008},
doi = {10.1051/ita:2007050},
zbl = {1149.03028},
mrnumber = {2382551},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007050/}
}
TY  - JOUR
AU  - Carton, Olivier
AU  - Finkel, Olivier
AU  - Simonnet, Pierre
TI  - On the continuity set of an Omega rational function
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
DA  - 2008///
SP  - 183
EP  - 196
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007050/
UR  - https://zbmath.org/?q=an%3A1149.03028
UR  - https://www.ams.org/mathscinet-getitem?mr=2382551
UR  - https://doi.org/10.1051/ita:2007050
DO  - 10.1051/ita:2007050
LA  - en
ID  - ITA_2008__42_1_183_0
ER  - 
Carton, Olivier; Finkel, Olivier; Simonnet, Pierre. On the continuity set of an Omega rational function. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 183-196. doi : 10.1051/ita:2007050. http://www.numdam.org/articles/10.1051/ita:2007050/

[1] Ya. M. Barzdin and B.A. Trakhtenbrot, Finite Automata, Behaviour and Synthesis. Nauka, Moscow (1970) (English translation, North Holland, Amsterdam, 1973). | MR 265078 | Zbl 0271.94032

[2] M.-P. Béal and O. Carton, Determinization of transducers over infinite words, in Proceedings of the International Conference ICALP 2000, edited by U. Montanari et al. Lect. Notes Comput. Sci. 1853 (2000) 561-570. | MR 1795917 | Zbl 0973.68113

[3] M.-P. Béal, O. Carton, C. Prieur and J. Sakarovitch, Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theor. Comput. Sci. 292 (2003) 45-63. | MR 1964625 | Zbl 1064.68050

[4] J. Berstel, Transductions and Context Free Languages. Teubner Verlag (1979). | MR 549481 | Zbl 0424.68040

[5] J.R. Büchi, On a decision method in restricted second order arithmetic, Logic Methodology and Philosophy of Science, Proc. 1960 Int. Congr. Stanford University Press (1962) 1-11. | MR 183636 | Zbl 0147.25103

[6] C. Choffrut, Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles. Theor. Comput. Sci. 5 (1977) 325-338. | MR 504457 | Zbl 0376.94022

[7] C. Choffrut and S. Grigorieff, Uniformization of rational relations, Jewels are Forever, edited by J. Karhumäki, H. Maurer, G. Paun and G. Rozenberg. Springer (1999) 59-71. | MR 1719021 | Zbl 0944.68107

[8] J. Engelfriet and H.J. Hoogeboom, X-automata on $\omega$-Words. Theor. Comput. Sci. 110 (1993) 1-51. | MR 1208658 | Zbl 0777.68058

[9] O. Finkel, On the topological complexity of infinitary rational relations. RAIRO-Theor. Inf. Appl. 37 (2003) 105-113. | Numdam | MR 2015686 | Zbl 1112.03313

[10] O. Finkel, Undecidability of topological and arithmetical properties of infinitary rational relations. RAIRO-Theor. Inf. Appl. 37 (2003) 115-126. | Numdam | MR 2015687 | Zbl 1112.03312

[11] O. Finkel, On Infinitary rational relations and Borel sets, in Proceedings of the Fourth International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS'03, 7-12 July 2003, Dijon, France. Lect. Notes Comput. Sci. 2731 (2003) 155-167. | MR 2062215 | Zbl 1040.03033

[12] O. Finkel, On the accepting power of 2-Tape Büchi automata, in Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, STACS (2006), Marseille, France. Lect. Notes Comput. Sci. (2006) 3884 301-312. | Zbl 1137.03023

[13] O. Finkel, Borel ranks and Wadge degrees of omega context free languages. Math. Structures Comput. Sci. 16 (2006) 813-840. | MR 2268344 | Zbl 1121.03047

[14] C. Frougny and J. Sakarovitch, Synchronized rational relations of finite and infinite words. Theor. Comput. Sci. 108 (1993) 45-82. | MR 1203822 | Zbl 0783.68065

[15] F. Gire, Relations rationnelles infinitaires. PhD thesis, Université Paris 7 (1981).

[16] F. Gire, Une extension aux mots infinis de la notion de transduction rationnelle, 6th GI Conf. Lect. Notes Comput. Sci. 145 (1983) 123-139. | Zbl 0495.68063

[17] F. Gire and M. Nivat, Relations rationnelles infinitaires. Calcolo XXI (1984) 91-125. | MR 799616 | Zbl 0552.68064

[18] A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). | MR 1321597 | Zbl 0819.04002

[19] A.S. Kechris, D. Marker and R.L. Sami, ${\Pi }_{1}^{1}$ Borel sets. J. Symbolic Logic 54 (1989) 915-920. | MR 1011178 | Zbl 0686.03025

[20] K. Kuratowski, Topology. Academic Press, New York (1966). | MR 217751 | Zbl 0158.40802

[21] L.H. Landweber, Decision problems for $\omega$-automata. Math. Syst. Theory 3 (1969) 376-384. | MR 260595 | Zbl 0182.02402

[22] H. Lescow and W. Thomas, Logical specifications of infinite computations, in A Decade of Concurrency, edited by J.W. de Bakker et al. Lect. Notes Comput. Sci. 803 (1994) 583-621. | MR 1292687

[23] R. Lindner and L. Staiger, Algebraische Codierungstheorie - Theorie der Sequentiellen Codierungen. Akademie-Verlag, Berlin (1977). | MR 469495 | Zbl 0363.94016

[24] Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980). | MR 561709 | Zbl 0433.03025

[25] D. Perrin and J.-E. Pin, Infinite words, automata, semigroups, logic and games. Pure Appl. Math. 141 (2004). | Zbl 1094.68052

[26] J-E. Pin, Logic, semigroups and automata on words. Ann. Math. Artif. Intell. 16 (1996) 343-384. | MR 1389853 | Zbl 0860.68071

[27] C. Prieur, Fonctions rationnelles de mots infinis et continuité. PhD thesis, Université Paris 7 (2000).

[28] C. Prieur, How to decide continuity of rational functions on infinite words. Theor. Comput. Sci. 250 (2001) 71-82. | MR 1795237 | Zbl 0952.68076

[29] P. Simonnet, Automates et théorie descriptive. PhD thesis, Université Paris 7, (1992). | JFM 48.0679.04

[30] L. Staiger, Hierarchies of recursive $\omega$-languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241. | MR 855527 | Zbl 0627.03024

[31] L. Staiger, $\omega$-Languages, in Handbook of Formal languages, Volume 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin. | MR 1470017 | Zbl 0866.68057

[32] L. Staiger and K. Wagner, Rekursive Folgenmengen I. Z. Math Logik Grundlag. Math. 24 (1978) 523-538. | MR 511706 | Zbl 0421.03035

[33] W. Thomas, Automata and quantifier hierarchies, in Formal Properties of Finite automata and Applications, Ramatuelle (1988). Lect. Notes Comput. Sci. 386 (1989) 104-119. | MR 1051954

[34] W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science, Volume B, edited by J. Van Leeuwen. Elsevier, Amsterdam (1990) 133-191. | MR 1127189 | Zbl 0900.68316

Cité par Sources :