# On the continuity set of an Omega rational function

Olivier Carton; Olivier Finkel; Pierre Simonnet

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 1, page 183-196
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCarton, Olivier, Finkel, Olivier, and Simonnet, Pierre. "On the continuity set of an Omega rational function." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 183-196. <http://eudml.org/doc/250351>.

@article{Carton2008,

abstract = {
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(f)
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 $\{\bf \Pi\}^0_2$-subset of Σω for some alphabet Σ
is the continuity set C(f) of an ω-rational synchronous
function f defined on Σω.
},

author = {Carton, Olivier, Finkel, Olivier, Simonnet, Pierre},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Infinitary rational relations; omega rational functions;
topology; points of continuity; decision problems; omega rational
languages; omega context-free languages.},

language = {eng},

month = {1},

number = {1},

pages = {183-196},

publisher = {EDP Sciences},

title = {On the continuity set of an Omega rational function},

url = {http://eudml.org/doc/250351},

volume = {42},

year = {2008},

}

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

DA - 2008/1//

PB - EDP Sciences

VL - 42

IS - 1

SP - 183

EP - 196

AB -
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(f)
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 ${\bf \Pi}^0_2$-subset of Σω for some alphabet Σ
is the continuity set C(f) of an ω-rational synchronous
function f defined on Σω.

LA - eng

KW - Infinitary rational relations; omega rational functions;
topology; points of continuity; decision problems; omega rational
languages; omega context-free languages.

UR - http://eudml.org/doc/250351

ER -

## References

top- Ya. M. Barzdin and B.A. Trakhtenbrot, Finite Automata, Behaviour and Synthesis. Nauka, Moscow (1970) (English translation, North Holland, Amsterdam, 1973).
- 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. Zbl0973.68113
- 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. Zbl1064.68050
- J. Berstel, Transductions and Context Free Languages. Teubner Verlag (1979).
- 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.
- 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. Zbl0376.94022
- 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. Zbl0944.68107
- J. Engelfriet and H.J. Hoogeboom, X-automata on ω-Words. Theor. Comput. Sci.110 (1993) 1–51.
- O. Finkel, On the topological complexity of infinitary rational relations. RAIRO-Theor. Inf. Appl.37 (2003) 105–113.
- O. Finkel, Undecidability of topological and arithmetical properties of infinitary rational relations. RAIRO-Theor. Inf. Appl.37 (2003) 115–126.
- 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.
- 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. Zbl1137.03023
- O. Finkel, Borel ranks and Wadge degrees of omega context free languages. Math. Structures Comput. Sci.16 (2006) 813–840. Zbl1121.03047
- C. Frougny and J. Sakarovitch, Synchronized rational relations of finite and infinite words. Theor. Comput. Sci.108 (1993) 45–82. Zbl0783.68065
- F. Gire, Relations rationnelles infinitaires. PhD thesis, Université Paris 7 (1981). Zbl0552.68064
- F. Gire, Une extension aux mots infinis de la notion de transduction rationnelle, 6th GI Conf. Lect. Notes Comput. Sci.145 (1983) 123–139.
- F. Gire and M. Nivat, Relations rationnelles infinitaires. CalcoloXXI (1984) 91–125. Zbl0552.68064
- A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). Zbl0819.04002
- A.S. Kechris, D. Marker and R.L. Sami, ${\Pi}_{1}^{1}$ Borel sets. J. Symbolic Logic54 (1989) 915–920. Zbl0686.03025
- K. Kuratowski, Topology. Academic Press, New York (1966).
- L.H. Landweber, Decision problems for ω-automata. Math. Syst. Theory3 (1969) 376–384. Zbl0182.02402
- 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.
- R. Lindner and L. Staiger, Algebraische Codierungstheorie – Theorie der Sequentiellen Codierungen. Akademie-Verlag, Berlin (1977). Zbl0363.94016
- Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980).
- D. Perrin and J.-E. Pin, Infinite words, automata, semigroups, logic and games. Pure Appl. Math.141 (2004). Zbl1094.68052
- J-E. Pin, Logic, semigroups and automata on words. Ann. Math. Artif. Intell.16 (1996) 343–384.
- C. Prieur, Fonctions rationnelles de mots infinis et continuité. PhD thesis, Université Paris 7 (2000).
- C. Prieur, How to decide continuity of rational functions on infinite words. Theor. Comput. Sci.250 (2001) 71–82. Zbl0952.68076
- P. Simonnet, Automates et théorie descriptive. PhD thesis, Université Paris 7, (1992).
- L. Staiger, Hierarchies of recursive ω-languages. J. Inform. Process. Cybernetics EIK22 (1986) 219–241. Zbl0627.03024
- L. Staiger, ω-Languages, in Handbook of Formal languages, Volume 3, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Berlin. Zbl0634.68070
- L. Staiger and K. Wagner, Rekursive Folgenmengen I. Z. Math Logik Grundlag. Math.24 (1978) 523–538. Zbl0421.03035
- W. Thomas, Automata and quantifier hierarchies, in Formal Properties of Finite automata and Applications, Ramatuelle (1988). Lect. Notes Comput. Sci.386 (1989) 104–119.
- W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science, Volume B, edited by J. Van Leeuwen. Elsevier, Amsterdam (1990) 133–191.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.