On Direct Product and Quotient of Strongly Connected Automata
Zino H. Hu · arXiv (Cornell University) · 2011
Let $A \ \times \ B$ be the direct product of a strongly connected permutation automaton $A$ and a strongly connected synchronizing (reset) automaton $B$, then $A \ \times \ B$ is strongly connected and $$\boldsymbol{A \cong (A \times B)/π}$$ $$\boldsymbol{B \cong (A \times B)/ρ}$$ $$\boldsymbol{(A \times B) \ \cong \ (A \times B)/π\ \times \ (A \times B)/ρ}$$ where $π$ and $ρ$ are automaton congruence relations defined in this paper, $(A \times B)/π$ and $(A \times B)/ρ$ are quotient automata constructed by $π$ and $ρ$ respectively.