Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

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

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: word equation

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.

Subwords and power-free words are not expressible by word equations

100%

Ilie L.

Fundamenta Informaticae

1999

tom Vol. 38, Nr 1,2

109-118

We consider several open problems of Karhumäki, Mignosi and Plandowski, cf. [KMP], con-cerning the expressibility of languages and relations as solutions of word equations. We show first that the (scattered) subword relation is not expressible. Then, we consider the set of k-power-free finite words and solve it negatively for all nontrivial integer values of k. Finally, we consider the Fibonacci finite words. We do not solve the problem of the expressibility of the set of these words but prove that a negative answer (as believed) cannot be given using the tools in [KMP].