2009/07/01 by Narad Rampersad, Jeffrey Shallit, Rampersad, N. +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0907.0159
openalex publication_date 2009/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Sigma is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Sigma*? In the case of testing universality for factors of languages represented by DFA's, we find an interesting connection to Cerny's conjecture on synchronizing words.