Search

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.

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 (R, S)-code and an (R, S)-free monoid for arbitrary word relations R and S. Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are (R,S)-codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations. We generalize the stability criterion of Schiitzenberger and Tilson's closure result for (R, S)-free monoids. The (R, S)-free hull of a set of words is introduced and we show how it can be computed. We prove a defect theorem for (R, S)-free hulls. In addition, a defect theorem of partial words is proved as a corollary.

We divide infinite sequences of subword complexity 2n+1 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 k > 2 be an integer. If the expansion in base k 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.