# 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

## Access Full Article

top## Abstract

top## How to cite

topCagnard, 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- A. Avizienis, Signed-digit number representation for fast parallel aritmetic. IRE Trans. Electronic Comput.10 (1961) 389–400.
- 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.
- 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
- A. Edgar, Classics On Fractals. Studies in non linearity. Westview Press (2004).
- S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York London (1974). Zbl0317.94045
- M.D. Ercegovac and T. Lang, On-the-fly convertion of redundant into conventional representations. IEEE Trans. Comput.36 (1987) 895–897.
- O. Finkel, On the topological complexity of infinitary rational relations. Theor. Inform. Appl.37 (2003) 105–113. Zbl1112.03313
- O. Finkel, Undecidability of topological and arithmetical properties of infinitary rational relations. Theor. Inform. Appl.37 (2003) 115–126. Zbl1112.03312
- G. Flory, Topologie, Analyse. Vuibert (1976).
- C. Frougny and J . Sakarovitch, Synchronized relations of finite and infinite words. Theoret. Comput. Sci. (1993) 45–82. Zbl0783.68065
- 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
- C. Frougny, On-the-fly algorithms and sequential machines. IEEE Trans. Comput.49 (2000) 859–863.
- C. Frougny, Numeration Systems. Chapter 7 of M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). Zbl1152.11303
- F. Gire, Two decidability problems for infinite words. Inform. Proc. Lett.22 (1986) 135–140. Zbl0587.68072
- A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). Zbl0819.04002
- P. Kornerup, Digit-set convertions: Generalizations and applications. IEEE Trans. Comput.43 (1994) 622–629.
- L.H. Landweber, Decision problem for ω-automata. Math. Systems. Theory3 (1969) 376–384. Zbl0182.02402
- 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.
- J.M. Muller, Arithmétique des ordinateurs. Masson, Paris (1989).
- D. Perrin and J.-E. Pin, Infinite words, Automata, Semigroups, Logic and Games. Pure Appl. Mathematics Series 141, Academic Press, Elsevier (2004). Zbl1094.68052
- C. Prieur, How to decide continuity of rationnal functions on infinite words. Theoret. Comput. Sci.250 (2001) 71–82. Zbl0952.68076
- C. Prieur, How to decide continuity of rationnal functions on infinite words (Errata). Theoret. Comput. Sci.276 (2002) 445–447. Zbl1052.68080
- J. Saint Raymond, Fonctions boréliennes sur un quotient. Bull. Soc. Math. France100 (1976) 141–147. Zbl0336.54015
- J. Sakarovitch, Éléments de théorie des automates. Vuibert informatique (2003).
- W. Sierpinski, Sur les fonctions de première classe. C. R. Acad. Sci. Paris170 (1920) 919–922. Zbl47.0236.02

## NotesEmbed ?

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