State complexity of the concatenation of regular tree languages
We consider the state complexity of basic concatenation operations for regular tree languages. We show that the sequential (respectively, parallel) concatenation of tree languages recognized by deterministic bottom-up automata with m and n states can be recognized by an automaton with (n+1).(m.2(n)+2(n-1))-1(respectively, m.2(n)+2(n-1)-1) states, and establish matching state complexity lower bounds. The bound for sequential concatenation of tree languages differs by an order of magnitude from the corresponding bound for regular string languages. (C) 2011 Elsevier B.V. All rights reserved.
state complexity lower bounds tree automata sequential and parallel concatenation