Corrigendum: On multiperiodic words
An algorithm is corrected here that was presented as Theorem 2 in [Š. Holub, 40 (2006) 583–591]. It is designed to calculate the maximum length of a nontrivial word with a given set of periods.
Corrigendum: On multiperiodic words
An algorithm is corrected here that was presented as Theorem 2 in [Š. Holub, (2006) 583–591]. It is designed to calculate the maximum length of a nontrivial word with a given set of periods.
Parikh test sets for commutative languages
A set is a Parikh test set of if is a test set of . We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters.
On multiperiodic words
In this note we consider the longest word, which has periods , and does not have the period gcd(). The length of such a word can be established by a simple algorithm. We give a short and natural way to prove that the algorithm is correct. We also give a new proof that the maximal word is a palindrome.
Linear size test sets for certain commutative languages
We prove that for each positive integer the finite commutative language possesses a test set of size at most Moreover, it is shown that each test set for has at least elements. The result is then generalized to commutative languages containing a word such that (i) and (ii) each symbol occurs at least twice in if it occurs at least twice in some word of : each such possesses a test set of size , where . The considerations rest on the analysis of some basic types of word equations....
Binary equality words with two ’s
Deciding whether a given word is an equality word of two nonperiodic morphisms is also known as the dual Post correspondence problem. Although the problem is decidable, there is no practical decision algorithm. Already in the binary case, the classification is a large project dating back to 1980s. In this paper we give a full classification of binary equality words in which one of the letters has two occurrences.
Complexity of testing morphic primitivity
We analyze an algorithm that decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in , where is the length of the word and the size of the alphabet.
Linear size test sets for certain commutative languages
We prove that for each positive integer the finite commutative language = ( ...) possesses a test set of size at most Moreover, it is shown that each test set for has at least -1 elements. The result is then generalized to commutative languages containing a word such that (i) alph() = alph}(); and (ii) each symbol ∈ alph}() occurs at least twice in if it occurs at least twice in some word of : each such possesses a test set...
Page 1