Ing. Karel Klouda, Ph.D.

Article

10.1016/j.tcs.2019.04.021

Department of Applied Mathematics

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.

Article

10.1016/j.tcs.2018.06.037

Department of Applied Mathematics

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.

Article

10.1016/j.tcs.2015.11.043

Department of Applied Mathematics

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.

Article

10.1016/j.jda.2015.03.006

Department of Applied Mathematics

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.

Article

10.1016/j.csda.2014.11.001

Department of Applied Mathematics

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.

Article

Department of Applied Mathematics

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.

Article

10.1016/j.tcs.2012.05.007

Department of Applied Mathematics

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.

Article

10.1051/ita/2011114

Department of Applied Mathematics

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.

Article

Department of Theoretical Computer Science

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.