On Continuous Nondeterminism and State Minimality
Adámek J, Milius S, Myers R, Urbat H, Urbat H (2014)
Publication Type: Journal article
Publication year: 2014
Journal
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
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.
Authors with CRIS profile
Stefan Milius
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Henning Urbat
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Involved external institutions
Germany (DE)How to cite
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://dx.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