We provide new insights on the determinization and minimization of tree
automata using congruences on trees. From this perspective, we study a
Brzozowski's style minimization algorithm for tree automata. First, we prove
correct this method relying on the following fact: when the automata-based and
the language-based congruences coincide, determinizing the automaton yields the
minimal one. Such automata-based congruences, in the case of word automata, are
defined using pre and post operators. Now we extend these operators to tree
automata, a task that is particularly challenging due to the reduced expressive
power of deterministic top-down (or equivalently co-deterministic bottom-up)
automata. We leverage further our framework to offer an extension of the
original result by Brzozowski for word automata.
In the context of signed line graphs, this article introduces a modified
inflation technique to study strong Gram congruence of non-negative (integral
quadratic) unit forms, and uses it to show that weak and strong Gram congruence
coincide among positive unit forms of Dynkin type A. The concept of inverse of
a quiver is also introduced, and is used to obtain and analyze the Coxeter
matrix of non-negative unit forms of Dynkin type A. Connected principal unit
forms of such type are also classified.