On continuous nondeterminism and state minimality

J Adámek, RSR Myers, H Urbat, S Milius - Electronic Notes in Theoretical …, 2014 - Elsevier
J Adámek, RSR Myers, H Urbat, S Milius
Electronic Notes in Theoretical Computer Science, 2014Elsevier
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 …
Abstract
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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果