On Continuous Nondeterminism and State Minimality
On Continuous Nondeterminism and State Minimality
复制标题
DOI：
10.1016/j.entcs.2014.10.002
复制
发表时间：
2014-10-29
影响因子：
--
通讯作者：
Milius, Stefan
中科院分区：
文献类型：
--
作者：
Adamek, Jiri;Myers, Robert S. R.;Milius, Stefan
本文致力于研究非确定闭包自动机，即在状态集上配备严格闭包算子和连续变迁结构的非确定有限自动机。我们证明了，对于每一个正规语言L有一个唯一的最小不确定闭包自动机，其基础NFA接受L。这里的极小性意味着不存在真的子自动机或商自动机，就像它在极小dfas的情况下一样。此外，在重要的情况下，该机器的封闭运营商是拓扑，其基础NFA被证明是状态最小的。这些结果的基础是有限半格范畴与有限严格闭包空间范畴之间的等价。
This paper is devoted to the study of nondeterministic closure automata, that is, nondeterministic finite automata (nfas) equipped with a strict closure operator on the set of states and continuous transition structure. We prove that for each regular language L there is a unique minimal nondeterministic closure automaton whose underlying nfa accepts L. Here minimality means no proper sub or quotient automata exist, just as it does in the case of minimal dfas. Moreover, in the important case where the closure operator of this machine is topological, its underlying nfa is shown to be state-minimal. The basis of these results is an equivalence between the categories of finite semilattices and finite strict closure spaces.