The number of primitive words of unbounded exponent in the language of an HD0L-system is finite
Authors
Year
2024
Published
Journal of Combinatorial Theory, Series A. 2024, 206 ISSN 0097-3165.
Type
Article
Departments
Annotation
Let H be an HD0L-system. We show that there are only finitely many primitive words v with the property that , for all integers k, is an element of the factorial language of H. In particular, this result applies to the set of all factors of a morphic word. We provide a formalized proof in the proof assistant Isabelle/HOL as part of the Combinatorics on Words Formalized project.
Characterization of circular D0L-systems
Authors
Year
2019
Published
Theoretical Computer Science. 2019, 790 131-137. ISSN 0304-3975.
Type
Article
Departments
Annotation
We give a characterization of circularity of a D0L-system. The characterizing condition is simple to verify and yields an efficient algorithm. To derive it, we prove that every non-circular D0L-system contains arbitrarily long repetitions. This result was already published in 1993 by Mignosi and Séébold, however their proof is only a sketch. We give a complete proof that, in addition, is valid for a slightly relaxed definition of circularity, called weak circularity.
Fixed Points of Sturmian Morphisms and Their Derivated Words
Authors
Klouda, K.; Medková, K.; Pelantová, E.; Starosta, Š.
Year
2018
Published
Theoretical Computer Science. 2018, 743 23-37. ISSN 0304-3975.
Type
Article
Departments
Annotation
Any infinite uniformly recurrent word u can be written as concatenation of a finite number of return words to a chosen prefix w of u. Ordering of the return words to w in this concatenation is coded by derivated word d_u(w). In 1998, Durand proved that a fixed point u of a primitive morphism has only finitely many derivated words d_u(w) and each derivated word d_u(w) is fixed by a primitive morphism as well. In our article we focus on Sturmian words fixed by a primitive morphism. We provide an algorithm which to a given Sturmian morphism ψ lists the morphisms fixing the derivated words of the Sturmian word u = psi(u). We provide a sharp upper bound on length of the list.
Synchronizing delay for binary uniform morphisms
Authors
Klouda, K.; Medková, K.
Year
2016
Published
Theoretical Computer Science. 2016, 615 12-22. ISSN 0304-3975.
Type
Article
Departments
Annotation
Circular D0L-systems are those with finite synchronizing delay. We introduce a tool called graph of overhangs which can be used to find the minimal value of synchronizing delay of a given D0L-system. By studying the graphs of overhangs, a general upper bound on the minimal value of a synchronizing delay of a circular D0L-system with a binary uniform morphism is given.
An algorithm for enumerating all infinite repetitions in a D0L-system
Authors
Year
2015
Published
Journal of Discrete Algorithms. 2015, 33 130-138. ISSN 1570-8667.
Type
Article
Departments
Annotation
We describe a simple algorithm that finds all primitive words v such that v^k is a factor of the language of a given D0L-system for all k. It follows that the number of such words is finite. This polynomial-time algorithm can be also used to decide whether a D0L-system is repetitive.
An Exact Polynomial Time Algorithm for Computing the Least Trimmed Squares Estimate
Authors
Year
2015
Published
Computational Statistics and Data Analysis. 2015, 84 27-40. ISSN 0167-9473.
Type
Article
Departments
Annotation
An exact algorithm for computing the estimates of regression coefficients given by the least trimmed squares method is presented. The algorithm works under very weak assumptions and has polynomial complexity. Simulations show that in the case of two or three explanatory variables, the presented algorithm is often faster than the exact algorithms based on a branch-and-bound strategy whose complexity is not known. The idea behind the algorithm is based on a theoretical analysis of the respective objective function, which is also given.
Factor and Palindromic Complexity of The-Morse's Avatars
Authors
Klouda, K.; Frougny, Ch.
Year
2013
Published
Acta Polytechnica. 2013, 53(6), 868-871. ISSN 1210-2709.
Type
Article
Departments
Annotation
Two infinite words that are connected with some significant univoque numbers are
studied. It is shown that their factor and palindromic complexities almost coincide with the
factor and palindromic complexities of the famous Thue-Morse word. Keywords: factor
complexity, palindromic complexity, univoque numbers, Thue-Morse word.
Bispecial factors in circular non-pushy D0L languages
Authors
Year
2012
Published
Theoretical Computer Science. 2012, 445 63-74. ISSN 0304-3975.
Type
Article
Departments
Annotation
We study bispecial factors in fixed points of morphisms. In particular, we propose a simple method of finding all bispecial words of non-pushy circular D0L-systems. This method can be formulated as an algorithm. Moreover, we prove that non-pushy circular D0L-systems are exactly those with finite critical exponents.
Rational base number systems for p-adic numbers
Authors
Frougny, Ch.; Klouda, K.
Year
2012
Published
RAIRO - Theoretical Informatics and Applications. 2012, 46(01), 87-106. ISSN 0988-3754.
Type
Article
Departments
Annotation
This paper deals with rational base number systems for p-adic numbers. We mainly focus on the system proposed by Akiyama et al. in 2008, but we also show that this system is in some sense isomorphic to some other rational base number systems by means of finite transducers. We identify the numbers with finite and eventually periodic representations and we also determine the number of representations of a given p-adic number.
Critical Exponent of Infinite Words Coding Beta-integers Associated with Non-simple Parry Numbers
Authors
Balková, L.; Pelantová, E.; Klouda, K.
Year
2011
Published
Integers: Electronic Journal of Combinatorial Number Theory. 2011, 11b 1-25. ISSN 1553-1732.
Type
Article
Departments
Annotation
In this paper, we study the critical exponent of infinite words u coding beta-
integers for beta being a non-simple Parry number. In other words, we investigate
the maximal consecutive repetitions of factors that occur in the infinite word in
question. We calculate also the ultimate critical exponent that expresses how long
repetitions occur in the infinite word u when the factors of length growing ad
infinitum are considered. The basic ingredients of our method are the description
of all bispecial factors of u and the notion of return words. This method can be
applied to any fixed point of any primitive substitution.