Deciding Determinism of Unary Languages Is coNP-Complete

摘要

In this paper, we give the complexity of deciding determinism of unary languages. First, we derive a set of arithmetic progressions from an expression E over a unary alphabet, and give the relations between numbers in these arithmetic progressions and words in L(E). Next, we define a problem related to arithmetic progressions and investigate the complexity of this problem. Finally, by reduction from this problem we show that deciding determinism of unary languages is coNP-complete.