×

Generalization of automatic sequences for numeration systems on a regular language. (English) Zbl 0945.68105

Summary: Let \(L\) be an infinite regular language on a totally ordered alphabet (\(\Sigma,<)\). Feeding a finite deterministic automaton (with output) with the words of \(L\), enumerated lexicographically with respect to \(<\), leads to an infinite sequence over the output alphabet of the automaton. This process generalizes the concept of \(k\)-automatic sequence for abstract numeration systems on a regular language (instead of systems in base \(k\)). Here, we study the first properties of these sequences and their relations with numeration systems.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.-P. Allouche, \(qq\); J.-P. Allouche, \(qq\)
[2] Allouche, J.-P., Sur la complexité des suites infinies, Bull. Belg. Math. Soc., 1, 133-143 (1994) · Zbl 0803.68094
[3] Bruyère, V.; Hansel, G., Bertrand numeration systems and recognizability, Theoret. Comput. Sci., 181, 17-43 (1997) · Zbl 0957.11015
[4] A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, IEEE Conf. Record of 1968 Ninth Ann. Symp. on Switching and Automata Theory, pp. 51-60.; A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, IEEE Conf. Record of 1968 Ninth Ann. Symp. on Switching and Automata Theory, pp. 51-60.
[5] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 186-192 (1972) · Zbl 0253.02029
[6] F.M. Dekking, M. Mendès France, A. van der Poorten, Folds!, Math. Intelligencer 4 (1982) 130-138, 173-181, 190-195.; F.M. Dekking, M. Mendès France, A. van der Poorten, Folds!, Math. Intelligencer 4 (1982) 130-138, 173-181, 190-195. · Zbl 0493.10001
[7] C. Frougny, Numeration systems, Algebraic Combinatorics on Words, Ch. 7, Cambridge University Press, Cambridge, to appear.; C. Frougny, Numeration systems, Algebraic Combinatorics on Words, Ch. 7, Cambridge University Press, Cambridge, to appear. · Zbl 0787.68057
[8] C. Frougny, B. Solomyak, On representation of integers in linear numeration systems, in: Ergodic Theory of \(Z^d\); C. Frougny, B. Solomyak, On representation of integers in linear numeration systems, in: Ergodic Theory of \(Z^d\) · Zbl 0856.11007
[9] Hollander, M., Greedy numeration systems and regularity, Theory Comput. Systems, 31, 2, 111-133 (1998) · Zbl 0895.68088
[10] P.B.A. Lecomte, M. Rigo, Numeration systems on a regular language, preprint (1999), see also http://xxx.lanl.gov/abs/cs.OH/9903005.; P.B.A. Lecomte, M. Rigo, Numeration systems on a regular language, preprint (1999), see also http://xxx.lanl.gov/abs/cs.OH/9903005. · Zbl 0969.68095
[11] A. Maes, Morphic predicates and applications to the decidability of arithmetic theories, Doctoral dissertation, Université de Mons-Hainaut, 1999.; A. Maes, Morphic predicates and applications to the decidability of arithmetic theories, Doctoral dissertation, Université de Mons-Hainaut, 1999.
[12] Mauduit, C., Sur l’ensemble normal des substitutions de longueur quelconque, J. Number Theory, 29, 3, 235-250 (1988) · Zbl 0655.10053
[13] C. Mauduit, Propriétés arithmétiques des substitutions, Séminaire de Théorie des Nombres, Paris (1989-90) Progress in Mathematics, vol. 102, Birkhäuser, Boston, 1992, pp. 177-190.; C. Mauduit, Propriétés arithmétiques des substitutions, Séminaire de Théorie des Nombres, Paris (1989-90) Progress in Mathematics, vol. 102, Birkhäuser, Boston, 1992, pp. 177-190. · Zbl 0741.11016
[14] J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Lecture Notes in Computer Science, vol. 172, Springer, Berlin, 1984, pp. 380-389.; J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Lecture Notes in Computer Science, vol. 172, Springer, Berlin, 1984, pp. 380-389. · Zbl 0554.68053
[15] Shallit, J., A generalization of automatic sequences, Theoret. Comput. Sci., 61, 1-16 (1988) · Zbl 0662.68052
[16] Shallit, J., Numeration systems, linear recurrences, and regular sets, Inform. and Comput., 113, 2, 331-347 (1994) · Zbl 0810.11006
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.