# Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?

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.

## 1 Answer

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.

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