A Congruence-Based Perspective on Finite Tree Automata

Article type: Research Article

Authors: Ganty, Pierre^{; *} | Gutiérrez, Elena | Valero, Pedro

Affiliations: IMDEA Software Institute, Madrid, Spain. pierre.ganty@imdea.org, elenagutiv@gmail.com, pevalme@fb.com

Correspondence: [*]

Abstract: 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.

DOI: 10.3233/FI-2021-2091

Journal: Fundamenta Informaticae, vol. 184, no. 1, pp. 1-47, 2021