Nondeterministic Automata and JSL-dfas

MaRDI QIDQ6344916zbMATH OpenFDO

Authors Robert Myers

Publication date 12 July 2020

Abstract: We introduce the category of dependency automata. A dependency automaton consists of two nondeterministic finite automata, with a relation between their states satisfying conditions. This category is equivalent to deterministic finite automata interpreted in join-semilattices i.e. JSL-dfas. The canonical dependency automaton accepting $L$ amounts to the state-minimal dfas for $L$ and $rev(L)$ connected by the `dependency relation'. We describe many canonical JSL-dfas as dependency automata and also explain/extend Brzozowski's algorithm. Call an nfa `subatomic' if its individual states accept a language in the closure of $L$ under left/right quotients and set-theoretic boolean operations. We prove an nfa $N$ is subatomic iff $rsc(rev(N))$'s transition monoid is syntactic.

This page was built for publication: Nondeterministic Automata and JSL-dfas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6344916)