Trees and languages with periodic signature

详细信息    查看全文

• 作者：Victor Marsault^a ; ^{Victor.Marsault@liafa.univ-paris-diderot.fr} ; ; Jacques Sakarovitch^b
• 关键词：Rational base numeration system ; Breadth-first signature ; Abstract numeration system
• 刊名：Indagationes Mathematicae
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：28
• 期：1
• 页码：221-246
• 全文大小：480 K
• 卷排序：28

文摘

The signature of a labelled tree (and hence of its prefix-closed branch language) is the sequence of the degrees of the nodes of the tree in the breadth-first traversal. In a previous work, we have characterised the signatures of the regular languages. Here, the trees and languages that have the simplest possible signatures, namely the periodic ones, are characterised as the sets of representations of the integers in rational base numeration systems.For any pair of co-prime integers pp and qq, p>q>1p>q>1, the language Lpq of representations of the integers in base pq looks chaotic and does not fit in the classical Chomsky hierarchy of formal languages. On the other hand, the most basic example given by L32, the set of representations in base 32, exhibits a remarkable regularity: its signature is the infinite periodic   sequence: 2,1,2,1,2,1,…2,1,2,1,2,1,…We first show that Lpq has a periodic signature and the period (a sequence of qq integers whose sum is pp) is directly derived from the Christoffel word   of slope pq. Conversely, we give a canonical way to label a tree generated by any periodic signature; its branch language then proves to be the set of representations of the integers in a rational base (determined by the period) and written with a non-canonical alphabet of digits. This language is very much of the same kind as a Lpq since rational base numeration systems have the key property that, even though Lpq is not regular, normalisation is realised by a finite letter-to-letter transducer.