@article{10.3233/FI-2021-2091,
    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.},
    Address = {NLD},
    Author = {Ganty, Pierre and Guti\'{e}rrez, Elena and Valero, Pedro},
    File = {A Congruence-Based Perspective on Finite Tree Automata - 2104.11453.pdf},
    ISSN = {0169-2968},
    Journal = {Fundam. Inf.},
    Month = {jan},
    Number = {1},
    Pages = {1--47},
    Publisher = {IOS Press},
    Title = {A Congruence-Based Perspective on Finite Tree Automata},
    URL = {https://doi.org/10.3233/FI-2021-2091},
    Volume = {184},
    Year = {2021},
    bdsk-url-1 = {https://doi.org/10.3233/FI-2021-2091},
    date-added = {2022-07-16 15:43:14 +0200},
    date-modified = {2022-07-16 15:43:14 +0200},
    issue_date = {2021},
    numpages = {47},
    doi = {10.3233/FI-2021-2091}
}

@article{10.3233/FI-2021-2091, 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.}, Address = {NLD}, Author = {Ganty, Pierre and Guti\'{e}rrez, Elena and Valero, Pedro}, File = {A Congruence-Based Perspective on Finite Tree Automata - 2104.11453.pdf}, ISSN = {0169-2968}, Journal = {Fundam. Inf.}, Month = {jan}, Number = {1}, Pages = {1--47}, Publisher = {IOS Press}, Title = {A Congruence-Based Perspective on Finite Tree Automata}, URL = {https://doi.org/10.3233/FI-2021-2091}, Volume = {184}, Year = {2021}, bdsk-url-1 = {https://doi.org/10.3233/FI-2021-2091}, date-added = {2022-07-16 15:43:14 +0200}, date-modified = {2022-07-16 15:43:14 +0200}, issue_date = {2021}, numpages = {47}, doi = {10.3233/FI-2021-2091} }