A Congruence-Based Perspective on Finite Tree Automata

Autor:	Ganty, Pierre, Gutiérrez, Elena, Valero, Pedro
Rok vydání:	2021
Předmět:	Computer Science - Formal Languages and Automata Theory F.4.3
Zdroj:	Fundamenta Informaticae, Volume 184, Issue 1 (December 23, 2021) fi:7402
Druh dokumentu:	Working Paper
Popis:	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. Comment: 47 pages, 2 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2104.11453 Zobrazit plný text záznamu View this record from Arxiv