In this work we use a framework of finite-state automata constructions based on equivalences over words to provide new insights on the relation between well-known methods for computing the minimal deterministic automaton of a language.
In conclusion, we establish a connection between well-known independent minimization methods through Theorem . Given a DFA, the left languages of its states form a partition on words, (P ), and thus, each left language is identified by a state. Intuitively, Moore's algorithm merges states to enforce the condition of Theorem , which results in merging blocks of (P ) that belong to the same Nerode's equivalence class. Note that Hopcroft's partition refinement method @cite_13 achieves the same goal at the end of its execution though, stepwise, the partition computed may differ from Moore's. On the other hand, any co-deterministic NFA satisfies the right-hand side of Equation hence, by Lemma , satisfies the condition of Theorem . Therefore, the double-reversal method, which essentially determinizes a co-determinized NFA, yields the minimal DFA. Finally, the left-right duality (Lemma ) of the language-based equivalences shows that the condition of Theorem is equivalent to that of Brzozowski and Tamm @cite_4 .
@cite_13 @cite_4
1768118166 2963702702
We show that every regular language defines a unique nondeterministic finite automaton (NFA), which we call "atomaton", whose states are the "atoms" of the language, that is, non-empty intersections of complemented or uncomplemented left quotients of the language. We describe methods of constructing the atomaton, and prove that it is isomorphic to the normal automaton of Sengoku, and to an automaton of Matz and Potthoff. We study "atomic" NFA's in which the right language of every state is a union of atoms. We generalize Brzozowski's double-reversal method for minimizing a deterministic finite automaton (DFA), showing that the result of applying the subset construction to an NFA is a minimal DFA if and only if the reverse of the NFA is atomic. We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of Kahn's result that a disjoint union of copies of Kd;d maximizes the number of independent sets of a bipartite d-regular graph, Galvin and Tet ali's result that the independence polynomial is maximized by the same, and Zhao's extension of both results to all d-regular graphs. For matchings, this shows that the matching polynomial and the total number of matchings of a d-regular graph are maximized by a union of copies of Kd;d. Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstrom. In probabilistic language, our main theorems state that for all d-regular graphs and all �, the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity � are maximized by Kd;d. Our method involves constrained optimization problems over distributions of random variables and applies to all d-regular graphs directly, without a reduction to the bipartite case. Using a variant of the method we prove a lower bound on the occupancy fraction of the hard-core model on any d-regular, vertex-transitive, bipartite graph: the occupancy fraction of such a graph is strictly greater than the occupancy fraction of the unique translationinvariant hard-core measure on the infinite d-regular tree