The problem of approximate computation of reset thresholds of synchronizing automata has gained a lot of attention recently. We introduce a broad class of algorithms that compute reset words and analyze their approximation ratios. We present three series of automata that reveal inherent limitations of greedy strategies for approximation of reset thresholds.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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ć.