Locality Testing for NFAs is PSPACE-complete

Antoine Amarilli, Mikaël Monet, Rémi De Pretto

The class of local languages is a well-known subclass of the regular languages that admits many equivalent characterizations. In this short note we establish the PSPACE-completenes…