Deciding determinism of unary languages

详细信息    查看全文

• 作者：Ping Lu^a ; ^b ; ^c ; ^{luping@ios.ac.cn" class="auth_mail" title="E-mail the corresponding author} ; Feifei Peng^a ; ^b ; ^c ; ¹ ; Haiming Chen^a ; ^{chm@ios.ac.cn" class="auth_mail" title="E-mail the corresponding author} ; Lixiao Zheng^d ;
• 关键词：Regular expressions ; Regular expressions with counting ; Deterministic languages ; Minimal DFA ; coNP-complete ; Π2p
• 刊名：Information and Computation
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：245
• 期：Complete
• 页码：181-196
• 全文大小：515 K

文摘

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)$\mathcal{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 ${\mathbf{\Pi }}_{\mathbf{2}}^{\mathbf{p}}$. We also establish a tight upper bound for the size of the minimal DFA for expressions with counting.