On the computational complexity of problems related to distinguishability sets

• Published in: Information and computation 2018-04, Vol.259, p.225-236
• Main Authors: Holzer, Markus, Jakobi, Sebastian
• Format: Article
• Language: English
• Subjects: Computational complexity; Deterministic finite automata; Distinguishability sets; State complexity; Synchronization
• ISSN: 0890-5401; 1090-2651
• DOI: 10.1016/j.ic.2017.09.003

We study the computational complexity of problems related to distinguishability sets for regular languages. Roughly speaking, the distinguishability set D(L) for a (not necessarily regular) language L consists of all those words w for which there exists x and y such that word xw is in L if and only if word yx is not in L; hence the word w distinguishes the two prefixes x and y. One can view this mapping from L to its distinguishability set as an operator D:2Σ⁎→2Σ⁎ with L↦D(L). In particular, we investigate the complexity of the representation problem, i.e., deciding for two given automata A and B, whether B accepts the distinguishability set of L(A). It is shown that this problem and some of its variants are highly intractable, namely PSPACE-complete. In fact, determining the size of an automaton for D(L(A)) is already PSPACE-complete. On the other hand, questions related to the hierarchy induced by iterated application of the D-operator turn out to be much easier. For instance, the question whether for a given automaton A, the accepted language is equal to its own distinguishability set, i.e., whether L(A)=D(L(A)) holds, is shown to be NL-complete. As a byproduct of our investigations, we found a nice characterization of synchronizing automata, namely that a (minimal) automaton A is synchronizing if and only if D(L(A))=D2(L(A)).