Decision Problems for Subregular Classes

We study the computational complexity of deciding whether a given deterministic or nondeterministic finite automaton (DFA or NFA) recognizes a language in a given subclass of regular languages. We prove NL-completeness of this problem on both automata models for the classes of comma-free codes, solid codes, and singleton languages. For the classes of combinational, finitely generated left ideal, star, comet, group, and co-finite languages, the membership problem is NL-complete on DFAs and PSPACE-complete on NFAs. We also show that the membership problem on NFAs is NL-complete for the classes of prefix-, suffix-, factor-, and subword-free, singletons, and finite languages and it is PSPACE-hard for symmetric definite languages. Next, we show that deciding whether a given unary partial DFA recognizes an ordered language is L-complete and deciding whether a partial DFA can be ordered is NP-complete. Finally, deciding whether a given DFA (NFA) recognizes an ordered or power-separating language is NL-hard (PSPACE-hard, respectively).