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

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: synchronizing automaton

Sortuj według:

Ogranicz wyniki do:

Principal Ideal Languages and Synchronizing Automata

100%

Gusev V. V. , Maslennikova M. I. , Pribavkina E. V.

tom Vol. 132, nr 1

95--108

We study ideal languages generated by a single word. We provide an algorithm to construct a strongly connected synchronizing automaton for which such a language serves as the language of synchronizing words. Also we present a compact formula to calculate the syntactic complexity of this language.

The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages

58%

Rampersad N. , Shallit J. , Xu Z.

tom Vol. 116, nr 1-4

223-236

In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ*? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černy, and Restivo's conjecture on the minimal uncompletable word.