On the Real-state Processing of Regular Operations and The Sakoda-Sipser Problem

详细信息    查看全文

• 作者：J. Andres Montoya¹ ; ^{jamontoyaa@unal.edu.co" class="auth_mail" title="E-mail the corresponding author} ; David Casas ^{dfcasast@unal.edu.co" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Finite automata ; State complexity ; Regular expressions ; Regular operation
• 刊名：Electronic Notes in Theoretical Computer Science
• 出版年：2016
• 出版时间：14 March 2016
• 年：2016
• 卷：321
• 期：Complete
• 页码：23-39
• 全文大小：261 K

文摘

In this work we study some aspects of state-complexity related to the very famous Sakoda-Sipser problem. We study the state-complexity of the regular operations, we survey the known facts and, by the way, we find some new and simpler proofs of some well known results. The analysis of the state of art allowed us to find a new and meaningful notion: Real-state processing. We investigate this notion, looking for a model of deterministic finite automata holding such an interesting property. We establish some preliminary results, which seem to indicate that there does not exists a model of deterministic finite automata having real-state processing of regular expressions, but, on the other hand, we are able of exhibiting a deterministic model of finite automata having real-state processing of star free regular expressions.