Pierre Ganty ; Elena Gutiérrez ; Pedro Valero - A Congruence-Based Perspective on Finite Tree Automata

fi:7402 - Fundamenta Informaticae, December 23, 2021, Volume 184, Issue 1
A Congruence-Based Perspective on Finite Tree AutomataArticle

Authors: Pierre Ganty ; Elena Gutiérrez ; Pedro Valero

    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.

    Volume: Volume 184, Issue 1
    Published on: December 23, 2021
    Accepted on: December 16, 2021
    Submitted on: April 26, 2021
    Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3

    Consultation statistics

    This page has been seen 206 times.
    This article's PDF has been downloaded 120 times.