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 has at least one point of continuity and that its continuity set 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 -subset of for some alphabet is the continuity set of an -rational synchronous function defined on .
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}, mrnumber = {2382551}, zbl = {1149.03028}, 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 SP - 183 EP - 196 VL - 42 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2007050/ DO - 10.1051/ita:2007050 LA - en ID - ITA_2008__42_1_183_0 ER -
%0 Journal Article %A Carton, Olivier %A Finkel, Olivier %A Simonnet, Pierre %T On the continuity set of an Omega rational function %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 183-196 %V 42 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2007050/ %R 10.1051/ita:2007050 %G en %F ITA_2008__42_1_183_0
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] Finite Automata, Behaviour and Synthesis. Nauka, Moscow (1970) (English translation, North Holland, Amsterdam, 1973). | MR | Zbl
and ,[2] 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 | Zbl
and ,[3] Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theor. Comput. Sci. 292 (2003) 45-63. | MR | Zbl
, , and ,[4] Transductions and Context Free Languages. Teubner Verlag (1979). | MR | Zbl
,[5] 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 | Zbl
,[6] 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 | Zbl
,[7] Uniformization of rational relations, Jewels are Forever, edited by J. Karhumäki, H. Maurer, G. Paun and G. Rozenberg. Springer (1999) 59-71. | MR | Zbl
and ,[8] X-automata on -Words. Theor. Comput. Sci. 110 (1993) 1-51. | MR | Zbl
and ,[9] On the topological complexity of infinitary rational relations. RAIRO-Theor. Inf. Appl. 37 (2003) 105-113. | Numdam | MR | Zbl
,[10] Undecidability of topological and arithmetical properties of infinitary rational relations. RAIRO-Theor. Inf. Appl. 37 (2003) 115-126. | Numdam | MR | Zbl
,[11] 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 | Zbl
,[12] 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
,[13] Borel ranks and Wadge degrees of omega context free languages. Math. Structures Comput. Sci. 16 (2006) 813-840. | MR | Zbl
,[14] Synchronized rational relations of finite and infinite words. Theor. Comput. Sci. 108 (1993) 45-82. | MR | Zbl
and ,[15] Relations rationnelles infinitaires. PhD thesis, Université Paris 7 (1981).
,[16] Une extension aux mots infinis de la notion de transduction rationnelle, 6th GI Conf. Lect. Notes Comput. Sci. 145 (1983) 123-139. | Zbl
,[17] Relations rationnelles infinitaires. Calcolo XXI (1984) 91-125. | MR | Zbl
and ,[18] Classical Descriptive Set Theory. Springer-Verlag (1995). | MR | Zbl
,[19] Borel sets. J. Symbolic Logic 54 (1989) 915-920. | MR | Zbl
, and ,[20] Topology. Academic Press, New York (1966). | MR | Zbl
,[21] Decision problems for -automata. Math. Syst. Theory 3 (1969) 376-384. | MR | Zbl
,[22] 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
and ,[23] Algebraische Codierungstheorie - Theorie der Sequentiellen Codierungen. Akademie-Verlag, Berlin (1977). | MR | Zbl
and ,[24] Descriptive Set Theory. North-Holland, Amsterdam (1980). | MR | Zbl
,[25] Infinite words, automata, semigroups, logic and games. Pure Appl. Math. 141 (2004). | Zbl
and ,[26] Logic, semigroups and automata on words. Ann. Math. Artif. Intell. 16 (1996) 343-384. | MR | Zbl
,[27] Fonctions rationnelles de mots infinis et continuité. PhD thesis, Université Paris 7 (2000).
,[28] How to decide continuity of rational functions on infinite words. Theor. Comput. Sci. 250 (2001) 71-82. | MR | Zbl
,[29] Automates et théorie descriptive. PhD thesis, Université Paris 7, (1992). | JFM
,[30] Hierarchies of recursive -languages. J. Inform. Process. Cybernetics EIK 22 (1986) 219-241. | MR | Zbl
,[31] -Languages, in Handbook of Formal languages, Volume 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin. | MR | Zbl
,[32] Rekursive Folgenmengen I. Z. Math Logik Grundlag. Math. 24 (1978) 523-538. | MR | Zbl
and ,[33] Automata and quantifier hierarchies, in Formal Properties of Finite automata and Applications, Ramatuelle (1988). Lect. Notes Comput. Sci. 386 (1989) 104-119. | MR
,[34] Automata on infinite objects, in Handbook of Theoretical Computer Science, Volume B, edited by J. Van Leeuwen. Elsevier, Amsterdam (1990) 133-191. | MR | Zbl
,Cité par Sources :