Adámek J, Milius S, Myers R, Urbat H, Urbat H (2014)
Publication Type: Journal article
Publication year: 2014
Publisher: Elsevier BV
Book Volume: 308
Pages Range: 3-23
URI: http://www8.cs.fau.de/publications
DOI: 10.1016/j.entcs.2014.10.002
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.
APA:
Adámek, J., Milius, S., Myers, R., Urbat, H., & Urbat, H. (2014). On Continuous Nondeterminism and State Minimality. Electronic Notes in Theoretical Computer Science, 308, 3-23. https://doi.org/10.1016/j.entcs.2014.10.002
MLA:
Adámek, Jiří, et al. "On Continuous Nondeterminism and State Minimality." Electronic Notes in Theoretical Computer Science 308 (2014): 3-23.
BibTeX: Download