Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 6

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: combinatorics on words

Sortuj według:

Ogranicz wyniki do:

Complete Characterization of Zero-expressible Functions

100%

Dąbrowski R. , Plandowski W.

Fundamenta Informaticae

2015

tom 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.

Defect theorems for trees

100%

Karhumäki J. , Mantaci S.

Fundamenta Informaticae

1999

tom 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.

Separating the Words of a Language by Counting Factors

100%

Saarela A.

Fundamenta Informaticae

2021

tom 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.

On the Shuffle of Star-Free Languages

88%

Castiglione G. , Restivo A.

Fundamenta Informaticae

2012

tom 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.

Pattern avoidance in partial words over a ternary alphabet

75%

Gągol A.

Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica

2015

tom 69

nr 1

Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with \(m\) distinct variables and of length at least \(2^m\) is avoidable over a ternary alphabet and if the length is at least \(3\cdot 2^{m-1}\) it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words – sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words.

On the Regularity of Iterated Hairpin Completion of a Single Word

75%

Kari L. , Seki S. , Kopecki S.

Fundamenta Informaticae

2011

tom 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.