Journal article

Publication year: 2018

Pages: 225-236

Journal: Information and Computation

Volume number: 259

ISSN: 0890-5401

eISSN: 1090-2651

Open access status: Bronze

DOI Link: https://doi.org/10.1016/j.ic.2017.09.003

Publisher: Elsevier

Abstract: 
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(Sigma)* -> 2(Sigma)* with L bar right arrow 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)) = D-2(L(A)). (c) 2017 Elsevier Inc. All rights reserved.

Harvard Citation style: Holzer, M. and Jakobi, S. (2018) On the computational complexity of problems related to distinguishability sets, Information and Computation, 259, pp. 225-236. https://doi.org/10.1016/j.ic.2017.09.003

APA Citation style: Holzer, M., & Jakobi, S. (2018). On the computational complexity of problems related to distinguishability sets. Information and Computation. 259, 225-236. https://doi.org/10.1016/j.ic.2017.09.003