Ing. Štěpán Plachý

Stať ve sborníku

10.1007/978-3-031-40247-0_5

Katedra teoretické informatiky

This paper deals with properties of synchronizing terms for finite tree automata, which is a generalization of the synchronization principle of deterministic finite string automata (DFA) and such terms correspond to a connected subgraph, where a state in the root is always the same regardless of states of subtrees attached to it. We ask, what is the maximum height of the smallest synchronizing term of a deterministic bottom-up tree automaton (DFTA) with n states, which naturally leads to two types of synchronizing terms, called weak and strong, that depend on whether a variable, i.e., a placeholder for a subtree, must be present in at least one leaf or all of them. We prove that the maximum height in the case of weak synchronization has a theoretical upper bound sl(𝑛)+𝑛−1, where sl(𝑛) is the maximum length of the shortest synchronizing string of an n-state DFAs. For strong synchronization, we prove exponential bounds. We provide a theoretical upper bound of 2^𝑛−𝑛−1 for the height and two constructions of automata approaching it. One achieves the height of Θ(2^(𝑛−√𝑛)) with an alphabet of linear size, and the other achieves 2^(𝑛−1)−1 with an alphabet of quadratic size.

Stať ve sborníku

10.1007/978-3-030-38919-2_47

Katedra teoretické informatiky

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.