A compatibility relation on letters induces a reflexive and
symmetric relation on words of equal length. We consider these word
relations with respect to the theory of variable length codes and
free monoids. We define an -code and an -free monoid
for arbitrary word relations and . Modified
Sardinas-Patterson algorithm is presented for testing whether finite
sets of words are -codes. Coding capabilities of relational
codes are measured algorithmically by finding minimal and maximal
relations. We...
We divide infinite sequences of subword complexity into
four subclasses with respect to left and right special elements
and examine the structure of the subclasses with the help of Rauzy
graphs. Let ≥ 2 be an integer. If the expansion in base
of a number is an Arnoux-Rauzy word, then it belongs to Subclass I
and the number is known to be transcendental. We prove the
transcendence of numbers with expansions in the subclasses II and
III.
We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.
An infinite word is -automatic if, for all , its st letter is the output of a deterministic automaton fed with the representation of in the considered numeration system . In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for , we state that a multidimensional infinite word over a finite alphabet is -automatic for some abstract numeration...
We consider relational periods, where the relation is a
compatibility relation on words induced by a relation on letters. We
prove a variant of the theorem of Fine and Wilf for a (pure) period
and a relational period.
The theorem of Fraenkel and Simpson states that the maximum number
of distinct squares that a word of length can contain is
less than . This is based on the fact that no more than two
squares can have their last occurrences starting at the same
position. In this paper we show that the maximum number of the last
occurrences of squares per position in a partial word containing one
hole is , where is the size of the alphabet. Moreover, we
prove that the number of distinct squares in a partial word...
Download Results (CSV)