Displaying similar documents to “Abstract β -expansions and ultimately periodic representations”

On multiplicatively dependent linear numeration systems, and periodic points

Christiane Frougny (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers β and γ respectively, such that β and γ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.

*-sturmian words and complexity

Izumi Nakashima, Jun-Ichi Tamura, Shin-Ichi Yasutomi (2003)

Journal de théorie des nombres de Bordeaux

Similarity:

We give analogs of the complexity p ( n ) and of Sturmian words which are called respectively the * -complexity p * ( n ) and * -Sturmian words. We show that the class of * -Sturmian words coincides with the class of words satisfying p * ( n ) ≤ n + 1 , and we determine the structure of * -Sturmian words. For a class of words satisfying p * ( n ) = n + 1 , we give a general formula and an upper bound for p ( n ) . Using this general formula, we give explicit formulae for p ( n ) for some words belonging to this class. In general, p ( n ) can take large...

Some Algebraic Properties of Machine Poset of Infinite Words

Aleksandrs Belovs (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

On the size of one-way quantum finite automata with periodic behaviors

Carlo Mereghetti, Beatrice Palano (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We show that, for any stochastic event p of period n , there exists a measure-once one-way quantum finite automaton (1qfa) with at most 2 6 n + 25 states inducing the event a p + b , for constants a > 0 , b ≥ 0 , satisfying a + b ≤ 1 . This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than 2 6 n + 26 states. Our results give added evidence of the strength...