Ing. Štěpán Plachý


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

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.
Stať ve sborníku
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.