On the periodicity of morphisms on free monoids
Density of critical factorizations
We investigate the density of critical factorizations of infinite sequences of words. The density of critical factorizations of a word is the ratio between the number of positions that permit a critical factorization, and the number of all positions of a word. We give a short proof of the Critical Factorization Theorem and show that the maximal number of noncritical positions of a word between two critical ones is less than the period of that word. Therefore, we consider only words of index one,...
Undecidability of the equivalence of finite substitutions on regular language
Towards a characterization of bipartite switching classes by means of forbidden subgraphs
We investigate which switching classes do not contain a bipartite graph. Our final aim is a characterization by means of a set of critically non-bipartite graphs: they do not have a bipartite switch, but every induced proper subgraph does. In addition to the odd cycles, we list a number of exceptional cases and prove that these are indeed critically non-bipartite. Finally, we give a number of structural results towards proving the fact that we have indeed found them all. The search for critically...
Undecidability of the equivalence of finite substitutions on regular language
A simplified proof is given for the following result due to Lisovik: it is undecidable for two given –free finite substitutions, whether they are equivalent on the regular language {0,1} .
Density of Critical Factorizations
We investigate the density of critical factorizations of infinite sequences of words. The density of critical factorizations of a word is the ratio between the number of positions that permit a critical factorization, and the number of all positions of a word. We give a short proof of the Critical Factorization Theorem and show that the maximal number of noncritical positions of a word between two critical ones is less than the period of that word. Therefore, we consider only words of...
Undecidability of infinite post correspondence problem for instances of Size 9
In the infinite Post Correspondence Problem an instance consists of two morphisms and , and the problem is to determine whether or not there exists an infinite word such that . This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini ( (2003) 231–245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable for instances where the morphisms...
The theorem of Fine and Wilf for relational periods
We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.
The theorem of Fine and Wilf for relational periods
We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.
On the number of squares in partial words
The theorem of Fraenkel and Simpson states that the maximum number of distinct squares that a word of length can contain is less than . This is based on the fact that no more than two squares can have their last occurrences starting at the same position. In this paper we show that the maximum number of the last occurrences of squares per position in a partial word containing one hole is , where is the size of the alphabet. Moreover, we prove that the number of distinct squares in a partial word...
Equality sets for recursively enumerable languages
We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter , where deletes the letters not in . Then we deduce...
Equality sets for recursively enumerable languages
We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter...
Bordered conjugates of words over large alphabets.
The number of positions starting a square in binary words.
Page 1