Digital Library
Close Browse articles from a journal
 
<< previous    next >>
     Journal description
       All volumes of the corresponding journal
         All issues of the corresponding volume
           All articles of the corresponding issues
                                       Details for article 20 of 22 found articles
 
 
  The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages
 
 
Title: The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages
Author: Rampersad, Narad
Shallit, Jeffrey
Xu, Zhi
Appeared in: Fundamenta informaticae
Paging: Volume 116 (2012) nr. 1-4 pages 223-236
Year: 2012-05-16
Contents: 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.
Publisher: IOS Press
Source file: Elektronische Wetenschappelijke Tijdschriften
 
 

                             Details for article 20 of 22 found articles
 
<< previous    next >>
 
 Koninklijke Bibliotheek - National Library of the Netherlands