Affiliations: [a] Department of Computer Science, Yonsei University, 50 Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea. emmous@yonsei.ac.kr | [b] Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 3BX, United Kingdom. sangkiko@liverpool.ac.uk | [c] School of Computing, Queen’s University, Kingston, Ontario K7L 3N6, Canada. ksalomaa@cs.queensu.ca
Correspondence:
[†]
Address for correspondence: Department of Computer Science, Yonsei University, 50 Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea
Note: [*] Han was supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government (MSIP) (R0124-16-0002).
Note: [‡] Ko was partially supported by EPSRC grant “Reachability problems for words, matrices and maps” (EP/M00077X/1)
Note: [§] Salomaa was supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.
Abstract: We give an optimized construction of a tree automaton recognizing the k-parallel, k ≥ 1, tree concatenation of two regular tree languages. For tree automata with m and n states, respectively, the construction yields an upper bound (m+12)(n+1)⋅2nk−1 for the state complexity of k-parallel tree concatenation. We give a matching lower bound in the case k = 2. We conjecture that the upper bound is tight for all values of k. We also consider the special case where one of the tree languages is the set of all ranked trees and in this case establish a different tight state complexity bound for all values of k.
Keywords: tree automata, state complexity, regular tree languages, tree concatenation
