On Synchronizing Tree Automata and Their Work–Optimal Parallel Run, Usable for Parallel Tree Pattern Matching
Autoři
Rok
2020
Publikováno
SOFSEM 2020: Theory and Practice of Computer Science. Cham: Springer, 2020. p. 576-586. Lecture Notes in Computer Science. vol. 12011. ISSN 0302-9743. ISBN 978-3-030-38918-5.
Typ
Stať ve sborníku
Pracoviště
Anotace
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 O(log n) time with ⌈n/ log n⌉ processors, for k ≤ log n,
or in O(k) time with ⌈n/ k⌉ processors, for k ≥ 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.