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

Involved external institutions

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://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