Laboratory of Mathematical Logic at PDMI

Пятница, 2 ноября, ауд. 106. Начало в 14:00.

Докладчик: Jarkko Peltomäki (University of Turku).

Тема: On Numeration Systems and Automatic Sequences.

Abstract

A sequence is k-automatic if its elements are obtained when the base-k representations of integers are successively fed into a given finite automaton. For example, the famous Thue-Morse sequence abbabaabbaab... is 2-automatic: symbol a occurs at position n (indexing from 0) if and only if the base-2 representation of n contains an even number of 1's (this is checkable by a simple automaton). These k-automatic sequences are a well-studied object in combinatorics on words, and they have many good properties. One important feature is that any property of a k-automatic word that is expressible in a certain first-order logic is decidable. Moreover, these sequences satisfy many closure properties. For instance, taking the symbols whose indices are in an arithmetic progression in a k-automatic sequence is again k-automatic.

Using a more exotic way of representing integers than the usual base-k representation, this notion of a k-automatic word can be generalized. In the talk, I will introduce some unusual numeration systems, like Pisot numeration systems and Parry numeration systems. I will compare the corresponding automatic sequences with k-automatic sequences, and sketch ideas that show that the Pisot case is similar to the k-automatic case while the more general Parry-automatic sequences break many of the good properties (like decidability and closure properties mentioned above) of k-automatic sequences.

I will give definitions of automatic sequences and numeration systems, so no prior knowledge of them is needed.