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.  Zbl0943.68106
  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).  Zbl0317.94045
  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.  Zbl1112.03313
  8. O. Finkel, Undecidability of topological and arithmetical properties of infinitary rational relations. Theor. Inform. Appl.37 (2003) 115–126.  Zbl1112.03312
  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.  Zbl0783.68065
  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.  Zbl0856.11007
  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).  Zbl1152.11303
  14. F. Gire, Two decidability problems for infinite words. Inform. Proc. Lett.22 (1986) 135–140.  Zbl0587.68072
  15. A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995).  Zbl0819.04002
  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.  Zbl0182.02402
  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).  Zbl1094.68052
  21. C. Prieur, How to decide continuity of rationnal functions on infinite words. Theoret. Comput. Sci.250 (2001) 71–82.  Zbl0952.68076
  22. C. Prieur, How to decide continuity of rationnal functions on infinite words (Errata). Theoret. Comput. Sci.276 (2002) 445–447.  Zbl1052.68080
  23. J. Saint Raymond, Fonctions boréliennes sur un quotient. Bull. Soc. Math. France100 (1976) 141–147.  Zbl0336.54015
  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.  Zbl47.0236.02

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.