Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6873969 | Information and Computation | 2015 | 16 Pages |
Abstract
In this paper, we investigate the complexity of deciding determinism of unary languages. First, we give a method to derive a set of arithmetic progressions from a regular expression E over a unary alphabet, and establish relations between numbers represented by these arithmetic progressions and words in L(E). Next, we define a problem relating to arithmetic progressions and investigate the complexity of this problem. Then by a reduction from this problem we show that deciding determinism of unary languages is coNP-complete. Finally, we extend our derivation method to expressions with counting, and prove that deciding whether an expression over a unary alphabet with counting defines a deterministic language is in Î 2p. We also establish a tight upper bound for the size of the minimal DFA for expressions with counting.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ping Lu, Feifei Peng, Haiming Chen, Lixiao Zheng,