Automata, Borel functions and real numbers in Pisot base

Benoit Cagnard; Pierre Simonnet

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 1, page 27-44
  • ISSN: 0988-3754

Abstract

top
This note is about functions ƒ : Aω → Bω whose graph is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function f : ℝ → ℝ is Baire class 1 if and only if both the overgraph and the undergraph of f are Fσ. We show that such characterization is also true for functions on infinite words if we replace the real ordering by the lexicographical ordering on Bω. From this we deduce that it is decidable whether such function are of Baire class 1 or not. We extend this result to real functions definable by automata in Pisot base.

How to cite

top

Cagnard, Benoit, and Simonnet, Pierre. "Automata, Borel functions and real numbers in Pisot base." RAIRO - Theoretical Informatics and Applications 41.1 (2007): 27-44. <http://eudml.org/doc/250036>.

@article{Cagnard2007,
abstract = { This note is about functions ƒ : Aω → Bω whose graph is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function $f : \mathbb\{ R\} \rightarrow \mathbb\{R\} $ is Baire class 1 if and only if both the overgraph and the undergraph of f are Fσ. We show that such characterization is also true for functions on infinite words if we replace the real ordering by the lexicographical ordering on Bω. From this we deduce that it is decidable whether such function are of Baire class 1 or not. We extend this result to real functions definable by automata in Pisot base. },
author = {Cagnard, Benoit, Simonnet, Pierre},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Borel set; Borel function; automata; sequential machine.},
language = {eng},
month = {4},
number = {1},
pages = {27-44},
publisher = {EDP Sciences},
title = {Automata, Borel functions and real numbers in Pisot base},
url = {http://eudml.org/doc/250036},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Cagnard, Benoit
AU - Simonnet, Pierre
TI - Automata, Borel functions and real numbers in Pisot base
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/4//
PB - EDP Sciences
VL - 41
IS - 1
SP - 27
EP - 44
AB - This note is about functions ƒ : Aω → Bω whose graph is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function $f : \mathbb{ R} \rightarrow \mathbb{R} $ is Baire class 1 if and only if both the overgraph and the undergraph of f are Fσ. We show that such characterization is also true for functions on infinite words if we replace the real ordering by the lexicographical ordering on Bω. From this we deduce that it is decidable whether such function are of Baire class 1 or not. We extend this result to real functions definable by automata in Pisot base.
LA - eng
KW - Borel set; Borel function; automata; sequential machine.
UR - http://eudml.org/doc/250036
ER -

References

top
  1. A. Avizienis, Signed-digit number representation for fast parallel aritmetic. IRE Trans. Electronic Comput.10 (1961) 389–400.  
  2. J.R. Büchi, On a decision method in restricted second order arithmetic, in Methodology and Philosophy of Science. Stanford Univ. Press, Calif. (1962) 1–11.  
  3. C. Choffrut, H. Pelibossian and P. Simonnet, Decision issues on functions realized by finite automata. J. Automata Languages Combin.4 (1999) 171–182.  
  4. A. Edgar, Classics On Fractals. Studies in non linearity. Westview Press (2004).  
  5. S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York London (1974).  
  6. M.D. Ercegovac and T. Lang, On-the-fly convertion of redundant into conventional representations. IEEE Trans. Comput.36 (1987) 895–897.  
  7. O. Finkel, On the topological complexity of infinitary rational relations. Theor. Inform. Appl.37 (2003) 105–113.  
  8. O. Finkel, Undecidability of topological and arithmetical properties of infinitary rational relations. Theor. Inform. Appl.37 (2003) 115–126.  
  9. G. Flory, Topologie, Analyse. Vuibert (1976).  
  10. C. Frougny and J . Sakarovitch, Synchronized relations of finite and infinite words. Theoret. Comput. Sci. (1993) 45–82.  
  11. C. Frougny and B. Solomyak, On representation of integers in linear numeration systems, in Ergodic Theory of Zd-Actions. New Brunswick, New Jersey (1996) 345–368.  
  12. C. Frougny, On-the-fly algorithms and sequential machines. IEEE Trans. Comput.49 (2000) 859–863.  
  13. C. Frougny, Numeration Systems. Chapter 7 of M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002).  
  14. F. Gire, Two decidability problems for infinite words. Inform. Proc. Lett.22 (1986) 135–140.  
  15. A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995).  
  16. P. Kornerup, Digit-set convertions: Generalizations and applications. IEEE Trans. Comput.43 (1994) 622–629.  
  17. L.H. Landweber, Decision problem for ω-automata. Math. Systems. Theory3 (1969) 376–384.  
  18. B. Maurey and J.P. Tacchi, Ludwig Scheeffer et les extensions du Théorème des Accroissements Finis, in Séminaire du Luxembourg, Travaux mathématiques, fascicule XIII (2002) 1–60.  
  19. J.M. Muller, Arithmétique des ordinateurs. Masson, Paris (1989).  
  20. D. Perrin and J.-E. Pin, Infinite words, Automata, Semigroups, Logic and Games. Pure Appl. Mathematics Series 141, Academic Press, Elsevier (2004).  
  21. C. Prieur, How to decide continuity of rationnal functions on infinite words. Theoret. Comput. Sci.250 (2001) 71–82.  
  22. C. Prieur, How to decide continuity of rationnal functions on infinite words (Errata). Theoret. Comput. Sci.276 (2002) 445–447.  
  23. J. Saint Raymond, Fonctions boréliennes sur un quotient. Bull. Soc. Math. France100 (1976) 141–147.  
  24. J. Sakarovitch, Éléments de théorie des automates. Vuibert informatique (2003).  
  25. W. Sierpinski, Sur les fonctions de première classe. C. R. Acad. Sci. Paris170 (1920) 919–922.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.