4
$\begingroup$

Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?

I would not expect this would work over an alphabet of size two or more, since it is PSPACE-complete to check whether a regular expression is universal. However, since regular languages over unary alphabets have nice characterizations, I would expect there would be some way to check the universality of an NFA over an unary alphabet.

$\endgroup$

1 Answer 1

4
$\begingroup$

Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for Finite and Unary Languages, for more results in this vein.

$\endgroup$
3
  • $\begingroup$ Could you please point out which result in the first paper you are refering to? $\endgroup$ Sep 26, 2018 at 11:43
  • $\begingroup$ The first paper is cited in the second paper as containing this classical result. Unfortunately no pointer is given. The main hurdle toward reading the first paper is the antiquated terminology. $\endgroup$ Sep 26, 2018 at 15:54
  • 1
    $\begingroup$ Section 6 in the Stockmeyer/Meyer paper is about unary alphabets, and Theorem 6.1 is the NP-completeness of non-universality. (I refer to the version of the paper on Albert Meyer's personal homepage, just in case: people.csail.mit.edu/meyer/meyer-stockmeyer-word-probs.pdf ) $\endgroup$ Oct 31, 2022 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.