RAIRO - Theoretical Informatics and Applications

Research Article

On the continuity set of an Omega rational function

Olivier Cartona1, Olivier Finkela2 and Pierre Simonneta3

a1 LIAFA, Université Paris 7 et CNRS, 2 Place Jussieu 75251 Paris Cedex 05, France; Olivier.Carton@liafa.jussieu.fr

a2 Équipe Modèles de Calcul et Complexité,

a3 UMR 6134-Systèmes Physiques de l'Environnement, Faculté des Sciences, Université de Corse, Quartier Grossetti BP52 20250, Corte, France; simonnet@univ-corse.fr

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 Σ ω .

(Online publication January 18 2008)

Key Words:

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

Mathematics Subject Classification:

  • 68Q05;
  • 68Q45;
  • 03D05
Metrics