For a given language L, we study the languages X such that for all distinct words u, v ∈ L, there exists a word x ∈ X that appears a different number of times as a factor in u and in v. In particular, we are interested in the following question: For which languages L does there exist a finite language X satisfying the above condition? We answer this question for all regular languages and for all sets of factors of infinite words.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We describe an intersection of the family of expressible relations and another natural family of relations. This is the first result of this kind existing in the literature. To obtain it we extend a tool for proving nonexpressibility of languages to a tool for proving nonexpressibility of relations.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is starfree. Some of the special cases here approached give rise to new problems in combinatorics on words.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xaya, and outputs w' = xayax, where x denotes the Watson- Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words a and a that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of a and a, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of a and a, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However as we show, the prefix rank forms an exception.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.