On Synchronizing Tree Automata and Their Work–Optimal Parallel Run, Usable for Parallel Tree Pattern Matching

We present a way of synchronizing finite tree automata: We define a synchronizing term and a k-local deterministic finite bottom–up tree automaton. Furthermore, we present a work–optimal parallel algorithm for parallel run of the deterministic k-local tree automaton in \(\mathcal {O}(\log {n})\) time with \(\lceil \frac{n}{\log {n}}\rceil \) processors, for \(k \le \log {n}\), or in \(\mathcal {O}(k)\) time with \(\lceil \frac{n}{k}\rceil \) processors, for \(k \ge \log {n}\), where n is the number of nodes of an input tree, on EREW PRAM. Finally, we prove that the deterministic finite bottom–up tree automaton that is used as a standard tree pattern matcher is k-local with respect to the height of a tree pattern.