Currently displaying 1 – 19 of 19

Showing per page

Order by Relevance | Title | Year of publication

Morphisms fixing words associated with exchange of three intervals

Petr AmbrožZuzana MasákováEdita Pelantová — 2010

RAIRO - Theoretical Informatics and Applications

We consider words coding exchange of three intervals with permutation (3,2,1), here called 3iet words. Recently, a characterization of substitution invariant 3iet words was provided. We study the opposite question: what are the morphisms fixing a 3iet word? We reveal a narrow connection of such morphisms and morphisms fixing Sturmian words using the new notion of amicability.

Complexity of infinite words associated with beta-expansions

Christiane FrougnyZuzana MasákováEdita Pelantová — 2004

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

We study the complexity of the infinite word u β associated with the Rényi expansion of 1 in an irrational base β > 1 . When β is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity ( n ) = n + 1 . For β such that d β ( 1 ) = t 1 t 2 t m is finite we provide a simple description of the structure of special factors of the word u β . When t m = 1 we show that ( n ) = ( m - 1 ) n + 1 . In the cases when t 1 = t 2 = = t m - 1 or t 1 > max { t 2 , , t m - 1 } we show that the first difference of the complexity function ( n + 1 ) - ( n ) takes value in { m - 1 , m } for every n , and consequently we determine...

Sturmian jungle (or garden?) on multiliteral alphabets

L'ubomíra BalkováEdita PelantováŠtěpán Starosta — 2010

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

The properties characterizing sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions...

Palindromes in infinite ternary words

L'ubomíra BalkováEdita PelantováŠtěpán Starosta — 2009

RAIRO - Theoretical Informatics and Applications

We study infinite words over an alphabet 𝒜 satisfying the property 𝒫 : 𝒫 ( n ) + 𝒫 ( n + 1 ) = 1 + # 𝒜 for any n , where 𝒫 ( n ) denotes the number of palindromic factors of length occurring in the language of . We study also infinite words satisfying a stronger property 𝒫ℰ : every palindrome of has exactly one palindromic extension in . For binary words, the properties 𝒫 and 𝒫ℰ coincide and these properties characterize Sturmian words, i.e., words with the complexity + 1 for any n . In this paper, we focus on ternary infinite words with...

Combinatorial and arithmetical properties of infinite words associated with non-simple quadratic Parry numbers

Lubomíra BalkováEdita PelantováOndřej Turek — 2007

RAIRO - Theoretical Informatics and Applications

We study some arithmetical and combinatorial properties of -integers for being the larger root of the equation . We determine with the accuracy of 1 the maximal number of -fractional positions, which may arise as a result of addition of two -integers. For the infinite word coding distances between the consecutive -integers, we determine precisely also the balance. The word is the only fixed point of the morphism → and → . In the case , the corresponding infinite word is sturmian, and, therefore,...

Sturmian jungle (or garden?) on multiliteral alphabets

L'ubomíra BalkováEdita PelantováŠtěpán Starosta — 2011

RAIRO - Theoretical Informatics and Applications

The properties characterizing Sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of Sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of Sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized definitions...

Complexity of infinite words associated with beta-expansions

Christiane FrougnyZuzana MasákováEdita Pelantová — 2010

RAIRO - Theoretical Informatics and Applications

We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine the complexity...

Greedy and lazy representations in negative base systems

Tomáš HejdaZuzana MasákováEdita Pelantová — 2013

Kybernetika

We consider positional numeration systems with negative real base - β , where β > 1 , and study the extremal representations in these systems, called here the greedy and lazy representations. We give algorithms for determination of minimal and maximal ( - β ) -representation with respect to the alternate order. We also show that both extremal representations can be obtained as representations in the positive base β 2 with a non-integer alphabet. This enables us to characterize digit sequences admissible as greedy...

Combinatorial properties of infinite words associated with cut-and-project sequences

Louis-Sébastien GuimondZuzana MasákováEdita Pelantová — 2003

Journal de théorie des nombres de Bordeaux

The aim of this article is to study certain combinatorial properties of infinite binary and ternary words associated to cut-and-project sequences. We consider here the cut-and-project scheme in two dimensions with general orientation of the projecting subspaces. We prove that a cut-and-project sequence arising in such a setting has always either two or three types of distances between adjacent points. A cut-and-project sequence thus determines in a natural way a symbolic sequence (infinite word)...

Palindromic complexity of infinite words associated with simple Parry numbers

Petr AmbrožZuzana MasákováEdita PelantováChristiane Frougny — 2006

Annales de l’institut Fourier

A simple Parry number is a real number β > 1 such that the Rényi expansion of 1 is finite, of the form d β ( 1 ) = t 1 t m . We study the palindromic structure of infinite aperiodic words u β that are the fixed point of a substitution associated with a simple Parry number β . It is shown that the word u β contains infinitely many palindromes if and only if t 1 = t 2 = = t m - 1 t m . Numbers β satisfying this condition are the so-called Pisot numbers. If t m = 1 then u β is an Arnoux-Rauzy word. We show that if β is a confluent Pisot number then 𝒫 ( n + 1 ) + 𝒫 ( n ) = 𝒞 ( n + 1 ) - 𝒞 ( n ) + 2 , where...

Page 1

Download Results (CSV)