Wyniki wyszukiwania - BazTech

Ograniczanie wyników

5 Fundamenta Informaticae

Znaleziono wyników: 5

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: combinatorics on words

Sortuj według:

Ogranicz wyniki do:

Separating the Words of a Language by Counting Factors

Saarela Aleksi

Fundamenta Informaticae

2021

Vol. 180, nr 4

375--393

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.

Complete Characterization of Zero-expressible Functions

Dąbrowski R., Plandowski W.

Fundamenta Informaticae

2015

Vol. 138, nr 3

339--350

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.

On the Shuffle of Star-Free Languages

Castiglione G., Restivo A.

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

35-44

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.

On the Regularity of Iterated Hairpin Completion of a Single Word

Kari L., Seki S., Kopecki S.

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

201-215

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.

Defect theorems for trees

Karhumäki J., Mantaci S.

Fundamenta Informaticae

1999

Vol. 38, Nr 1,2

119-133

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.