|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 20 van 22 gevonden artikelen
| Titel: |
The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages |
| Auteur: |
Rampersad, Narad Shallit, Jeffrey Xu, Zhi |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 116 (2012) nr. 1-4 pagina's 223-236 |
| Jaar: |
2012-05-16 |
| Inhoud: |
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 Černý, and Restivo's conjecture on the minimal uncompletable word. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 20 van 22 gevonden artikelen
| << vorige | volgende >> |