On the Equivalence Checking Problem for Deterministic Top-Down Tree Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913778377949184 |
|---|---|
| author | Deng, Zhibo Zakharov, Vladimir A. |
| author_facet | Deng, Zhibo Zakharov, Vladimir A. |
| contents | We present an efficient algorithm for checking language equivalence of states in top-down deterministic finite tree automata (DFTAs). Unlike string automata, tree automata operate over hierarchical structures, posing unique challenges for algorithmic analysis. Our approach reduces the equivalence checking problem to that of checking the solvability of a system of language-theoretic equations, which specify the behavior of a DFTA. By constructing such a system of equations and systematically manipulating with it through substitution and conflict detection rules, we develop a decision procedure that determines whether two states accept the same tree language. We formally prove the correctness and termination of the algorithm and establish its worst-case time complexity as $O(n^2)$ under the RAM (Random Access Machine) model of computation augmented with pointers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04206 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Equivalence Checking Problem for Deterministic Top-Down Tree Automata Deng, Zhibo Zakharov, Vladimir A. Formal Languages and Automata Theory Logic 68Q45 F.4.3 We present an efficient algorithm for checking language equivalence of states in top-down deterministic finite tree automata (DFTAs). Unlike string automata, tree automata operate over hierarchical structures, posing unique challenges for algorithmic analysis. Our approach reduces the equivalence checking problem to that of checking the solvability of a system of language-theoretic equations, which specify the behavior of a DFTA. By constructing such a system of equations and systematically manipulating with it through substitution and conflict detection rules, we develop a decision procedure that determines whether two states accept the same tree language. We formally prove the correctness and termination of the algorithm and establish its worst-case time complexity as $O(n^2)$ under the RAM (Random Access Machine) model of computation augmented with pointers. |
| title | On the Equivalence Checking Problem for Deterministic Top-Down Tree Automata |
| topic | Formal Languages and Automata Theory Logic 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2504.04206 |