Undecidability of the equivalence of finite substitutions on regular language
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} .
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...
Page 1