Back to Search
Start Over
The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages.
- Source :
-
Fundamenta Informaticae . 2012, Vol. 116 Issue 1-4, p223-236. 14p. 2 Diagrams. - Publication Year :
- 2012
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01692968
- Volume :
- 116
- Issue :
- 1-4
- Database :
- Academic Search Index
- Journal :
- Fundamenta Informaticae
- Publication Type :
- Academic Journal
- Accession number :
- 75231144
- Full Text :
- https://doi.org/10.3233/fi-2012-680