×

Affinely recursive sets and orderings of languages. (English) Zbl 1091.68066

Summary: An affinely recursive set \(S\) consists of integers defined by these rules: \(1 \in S\), and if \(x \in S\), then \(f(x)\in S\) for every \(f\) in a prescribed set \(F\) of affine functions with integer coefficients. If these functions are indexed by a set \(A\), then each \(x\) in \(S\) except 1 corresponds to a word in the language \(L(A)\) of nonempty words over the alphabet \(A\). Conditions are found for the correspondence to be bijective, so that the ordering of numbers in \(S\) induces an ordering of \(L(A)\). Moreover, since each \(x\) except 1 in \(S\) is of the form \(f(y)\) for some \(y\) in \(S\) and \(f\) in \(F\), the set \(S\) is partitioned by \(F\). The partition extends to \(L(A)\); viz., a component consists of words that end in the same letter. The distribution and limiting density within \(S\) of the numbers in each component is considered.

MSC:

68Q45 Formal languages and automata
68R15 Combinatorics on words

Software:

OEIS
Full Text: DOI

References:

[1] J.-P. Allouche, J.O. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in: C. Ding, T. Helleseth, H. Niederreiter (Eds.), Sequences and Their Applications: Proceedings of SETA ’98, Springer-Verlag, Berlin, 1999, pp. 1-16.; J.-P. Allouche, J.O. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in: C. Ding, T. Helleseth, H. Niederreiter (Eds.), Sequences and Their Applications: Proceedings of SETA ’98, Springer-Verlag, Berlin, 1999, pp. 1-16. · Zbl 1005.11005
[2] Allouche, J.-P.; Shallit, J. O., The ring of \(k\)-regular sequences, Theoret. Comput. Sci., 98, 163-197 (1992) · Zbl 0774.68072
[3] Guy, R., Unsolved Problems in Number Theory (1994), Springer-Verlag: Springer-Verlag Berlin · Zbl 0805.11001
[4] N.J.A. Sloane, On-line Encyclopedia of Integer Sequences, http://www.research.att.com/njas/sequences; N.J.A. Sloane, On-line Encyclopedia of Integer Sequences, http://www.research.att.com/njas/sequences · Zbl 1274.11001
[5] J. Tamura, Some problems and results having their origin in the power series \(Σ_n^{+∞}z^{[ αn }zn\); J. Tamura, Some problems and results having their origin in the power series \(Σ_n^{+∞}z^{[ αn }zn\)
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.