{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T04:11:03Z","timestamp":1751429463903,"version":"3.41.0"},"reference-count":0,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2022,1,10]],"date-time":"2022-01-10T00:00:00Z","timestamp":1641772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2022,1,10]]},"abstract":"<jats:p> We provide new insights on the determinization and minimization of tree automata using congruences on trees. From this perspective, we study a Brzozowski\u2019s 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. <\/jats:p>","DOI":"10.3233\/fi-2021-2091","type":"journal-article","created":{"date-parts":[[2022,1,11]],"date-time":"2022-01-11T18:02:18Z","timestamp":1641924138000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Congruence-Based Perspective on Finite Tree Automata"],"prefix":"10.1177","volume":"184","author":[{"given":"Pierre","family":"Ganty","sequence":"first","affiliation":[{"name":"IMDEA Software Institute, Madrid, Spain. , ,"}]},{"given":"Elena","family":"Guti\u00e9rrez","sequence":"additional","affiliation":[{"name":"IMDEA Software Institute, Madrid, Spain. , ,"}]},{"given":"Pedro","family":"Valero","sequence":"additional","affiliation":[{"name":"IMDEA Software Institute, Madrid, Spain. , ,"}]}],"member":"179","published-online":{"date-parts":[[2022,1,10]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2021-2091","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2021-2091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:55:41Z","timestamp":1751367341000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2021-2091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,10]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,10]]}},"alternative-id":["10.3233\/FI-2021-2091"],"URL":"https:\/\/doi.org\/10.3233\/fi-2021-2091","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"type":"print","value":"0169-2968"},{"type":"electronic","value":"1875-8681"}],"subject":[],"published":{"date-parts":[[2022,1,10]]}}}