2
$\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$
3
$\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$
  • $\begingroup$ Could you please point out which result in the first paper you are refering to? $\endgroup$ – Agnishom Chattopadhyay Sep 26 '18 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$ – Yuval Filmus Sep 26 '18 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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