×

\(Pm\) numbers, ambiguity, and regularity. (English) Zbl 0806.11007

The authors study the so-called pseudo-\(m\)-ray number system \((Pm)\), where integers are represented by sums \(\sum a_ i {{m^{i+1}-1} \over {m^ i-1}}\), with \(a_ i=0,1,2, \dots,m\) (\(m\) is given \(>1\)). They show that the language consisting of the \(Pm\) representation of the natural integers obtained by the greedy algorithm is regular. Furthermore they show that the language of the representations of the non-ambiguous integers is also regular (a “non-ambiguous” integer admits only one representation in this system).
Note that some of these representations are related to the sequence of parentheses occurring in the recursive definition of integers [see J.-P. Allouche, J. Bétréma and J. O. Shallit, RAIRO, Inf. Théor. Appl. 23, 235-249 (1988; Zbl 0691.68065)], but also (at least for \(q=2\)) to proofs of transcendence of values of the Carlitz zeta function [see J.-P. Allouche, Sémin. Théor. Nombres Bordx., II. Ser. 2, 103-117 (1990; Zbl 0709.11067), see also V. Berthé, Acta Arith. 66, 369-390 (1994) and Combinaisons linéaires de \(\zeta(s)/\pi^ s\) sur \(\mathbb{F}_ q(x)\), pour \(1\leq s\leq q-2\), J. Number Theory (to appear)].
Note also that the \(Pm\) representations are related to \(m\)-ary trees [H. A. Cameron, Extremal cost binary trees, Ph. D. Thesis, University of Waterloo (1991) and H. A. Cameron and D. Wood, Discrete Appl. Math. 55, 15-35 (1994)].
Finally “syms” (first line of the Abstract) should be replaced by “sums” and the usual French word for greedy algorithm is “algorithme glouton”.

MSC:

11A67 Other number representations
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] J.-P. ALLOUCHE, J. BETREMA and J. O. SHALLIT, Sur des points fixes de morphismes d’un monoïde libre, Informatique Théorique et Applications/Theoretical Informatics and Applications, 23, (3), 1989, pp. 235-249. Zbl0691.68065 MR1020473 · Zbl 0691.68065
[2] H. A. CAMERON, Extremal Cost Binary Trees, Ph. D. thesis, University of Waterloo, 1991.
[3] H. A. CAMERON and D. WOOD, The maximal path length of binary trees, Discrete Applied Mathematics, to appear, 1993. Zbl0821.68094 · Zbl 0821.68094
[4] A. S. FRAENKEL, Systems of numeration, The American Mathematical Monthly, 92, (2), 1985, pp. 105-114. Zbl0568.10005 MR777556 · Zbl 0568.10005
[5] J. SHALLIT, Numeration Systems, linear recurrences, and regular sets, Technical Report CS-91-32, University of Waterloo, July 1991. · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.