×

Automata, Borel functions and real numbers in Pisot base. (English) Zbl 1156.03036

A Büchi (nondeterministic) automata \({\mathcal A}\) is a 5-tuple \({\mathcal A}= \langle A,Q,J,T,F\rangle\), where \(A\) is a finite alphabet, \(Q\) is a finite set of states, \(J\subset Q\) is the set of initial states, \(T\subset Q\times A\times Q\) is the set of transitions and \(F\subset Q\) is the set of final states. Let \(\omega\) be the set of natural numbers. A path \(c\) of label \(\alpha\) in \({\mathcal A}\) is an infinite word \(c= c(0)c(1)\dots c(n)\dots\) from \((Q\times A\times Q)^\omega\), so that for any \(n\in \omega\), \(c(n)\) is of the form \((\beta(n), \alpha(n), \beta(+1))\) with \(\beta(0)\in J\) and \(c(n)\in T\).
Let \(\text{Infinity}(c)\) denote the set of states that appear infinitely many times in \(c\). An accepting path \(c\) is a path so that \(\text{Infinity}(c)\cap T\neq \emptyset\). An accepted word \(\alpha\) is a word such that there exists an accepting path \(c\) of label \(\alpha\). The word \(\alpha\) is said to be recognized by \({\mathcal A}\).
The present work studies, from a topological point of view, functions \(f: A^\omega\to B^\omega\) with a graph recognized by a Büchi finite automaton on the product alphabet \(A\times B\). It is known that such functions form the Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such functions are continuous or not. The authors prove that it is decidable whether such functions are of Baire class 1 or not.

MSC:

03D05 Automata and formal grammars in connection with logical questions
03E15 Descriptive set theory
68Q45 Formal languages and automata
54H05 Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets)
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML Link

References:

[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 . Zbl 0943.68106 · Zbl 0943.68106
[4] A. Edgar , Classics On Fractals . Studies in non linearity. Westview Press ( 2004 ). Zbl 1062.28007 · Zbl 1062.28007
[5] S. Eilenberg , Automata , Languages and Machines, Vol. A. Academic Press, New York London ( 1974 ). MR 530382 | Zbl 0317.94045 · Zbl 0317.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 . Numdam | Zbl 1112.03313 · Zbl 1112.03313 · doi:10.1051/ita:2003016
[8] O. Finkel , Undecidability of topological and arithmetical properties of infinitary rational relations . Theor. Inform. Appl. 37 ( 2003 ) 115 - 126 . Numdam | Zbl 1112.03312 · Zbl 1112.03312 · doi:10.1051/ita:2003013
[9] G. Flory , Topologie , Analyse. Vuibert ( 1976 ). · Zbl 0452.00006
[10] C. Frougny and J . Sakarovitch, Synchronized relations of finite and infinite words. Theoret. Comput. Sci. (1993) 45-82. Zbl 0783.68065 · Zbl 0783.68065 · doi:10.1016/0304-3975(93)90230-Q
[11] C. Frougny and B. Solomyak , On representation of integers in linear numeration systems , in Ergodic Theory of \(Z^d\)-Actions. New Brunswick, New Jersey ( 1996 ) 345 - 368 . Zbl 0856.11007 · Zbl 0856.11007
[12] C. Frougny , On-the-fly algorithms and sequential machines . IEEE Trans. Comput. 49 ( 2000 ) 859 - 863 . · Zbl 1392.68438
[13] C. Frougny , Numeration Systems . Chapter 7 of M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press ( 2002 ). · Zbl 1152.11303
[14] F. Gire , Two decidability problems for infinite words . Inform. Proc. Lett. 22 ( 1986 ) 135 - 140 . Zbl 0587.68072 · Zbl 0587.68072 · doi:10.1016/0020-0190(86)90058-X
[15] A.S. Kechris , Classical Descriptive Set Theory . Springer-Verlag ( 1995 ). MR 1321597 | Zbl 0819.04002 · Zbl 0819.04002
[16] P. Kornerup , Digit-set convertions: Generalizations and applications . IEEE Trans. Comput. 43 ( 1994 ) 622 - 629 .
[17] L.H. Landweber , Decision problem for \(\omega \)-automata . Math. Systems. Theory 3 ( 1969 ) 376 - 384 . Zbl 0182.02402 · Zbl 0182.02402 · doi:10.1007/BF01691063
[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 . Zbl 1101.01009 · Zbl 1101.01009
[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 ). Zbl 1094.68052 · Zbl 1094.68052
[21] C. Prieur , How to decide continuity of rationnal functions on infinite words . Theoret. Comput. Sci. 250 ( 2001 ) 71 - 82 . Zbl 0952.68076 · Zbl 0952.68076 · doi:10.1016/S0304-3975(99)00115-2
[22] C. Prieur , How to decide continuity of rationnal functions on infinite words (Errata). Theoret. Comput. Sci. 276 ( 2002 ) 445 - 447 . Zbl 1052.68080 · Zbl 1052.68080 · doi:10.1016/S0304-3975(01)00307-3
[23] J. Saint Raymond , Fonctions boréliennes sur un quotient . Bull. Soc. Math. France 100 ( 1976 ) 141 - 147 . Zbl 0336.54015 · Zbl 0336.54015
[24] J. Sakarovitch , Éléments de théorie des automates . Vuibert informatique ( 2003 ). · Zbl 1178.68002
[25] W. Sierpinski , Sur les fonctions de première classe . C. R. Acad. Sci. Paris 170 ( 1920 ) 919 - 922 . JFM 47.0236.02 · JFM 47.0236.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.