State Complexity of k-Parallel Tree Concatenation

• Autorzy: Han Y.-S. , Ko S.-K. , Salomaa K.

Identyfikatory

DOI

10.3233/FI-2017-1560

• Języki publikacji: EN

Abstrakty

EN

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+1/2)(n+1)⋅2^nk−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.

Słowa kluczowe

EN

tree automata; state complexity; regular tree languages; tree concatenation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 185--199
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Han Y.-S.

• Department of Computer Science, Yonsei University, 50 Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea

autor

Ko S.-K.

• Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 3BX, United Kingdom

autor

Salomaa K.

• School of Computing, Queen’s University, Kingston, Ontario K7L 3N6, Canada

Bibliografia

• [1] Maslov A. Estimates on the number of states of finite automata. Soviet Mathematics Doklady, 1970;11:1373–1375.
• [2] Yu S, Zhuang Q, Salomaa K. The state complexities of some basic operations on regular languages. Theoretical Computer Science, 1994;125(2):315–328. doi:10.1016/0304-3975(92)00011-F.
• [3] Salomaa A, Salomaa K, Yu S. State complexity of combined operations. Theoretical Computer Science, 2007;383(2-3):140–152. URL https://doi.org/10.1016/j.tcs.2007.04.015.
• [4] Holzer M, Kutrib M. Descriptional and computational complexity of finite automata. Information and Computation, 2011;209(3):456–470. URL https://doi.org/10.1016/j.ic.2010.11.013.
• [5] Gao Y, Moreira N, Reis R, Yu S. A survey on operational state complexity. URL https://arxiv.org/abs/1509.03254.
• [6] Cristau J, Löding C, Thomas W. Deterministic automata on unranked trees. In: Proceedings of the 15th International Symposium on Fundamentals of Computation Theory, pp. 68–79. 2005. doi:10.1007/11537311_7.
• [7] Han YS, Ko SK, Piao X, Salomaa K. State complexity of Kleene-star operations on regular tree languages. Acta Cybernetica, 2015;22(2):403–422. URL http://dblp.uni-trier.de/db/journals/actaC/actaC22.html#HanKPS15.
• [8] Piao X, Salomaa K. Transformations between different models of unranked bottom-up tree automata. Fundamenta Informaticae, 2011;109(4):405–424. dooi:10.3233/FI-2011-519.
• [9] Han YS, Salomaa K. Nondeterministic state complexity of nested word automata. Theoretical Computer Science, 2009;410(30-32):2961–2971. URL https://doi.org/10.1016/j.tcs.2009.01.004.
• [10] Okhotin A, Salomaa K. State complexity of operations on input-driven pushdown automata. Journal of Computer and System Sciences, 2017;86:207–228. URL Statecomplexityofoperationsoninput-drivenpushdownautomata..
• [11] Piao X, Salomaa K. State complexity of the concatenation of regular tree languages. Theoretical Computer Science, 2012;429:273–281. URL https://doi.org/10.1016/j.tcs.2011.12.048.
• [12] Ko SK, Eom HS, Han YS. Operational state complexity of subtree free regular tree languages. International Journal of Foundations of Computer Science, 2016;27(6):705–724. URL https://doi.org/10.1142/S0129054116500246.
• [13] Ko SK, Lee HR, Han YS. State complexity of regular tree languages for tree matching. International Journal of Foundations of Computer Science, 2016;27(8):965–980. URL https://doi.org/10.1142/S0129054116500398.
• [14] Comon H, Dauchet M, Jacquemard F, Lugiez D, Tison S, Tommasi M. Tree Automata Techniques and Applications. 2007. Electronic book available at http://www.tata.gforge.inria.fr.
• [15] Gécseg F, Steinby M. Tree languages. In: Rozenberg G, Salomaa A (eds.), Handbook of Formal Languages, Vol. 3: Beyond Words, pp. 1–68. Springer-Verlag New York, Inc., 1997. ISBN:3-540-60649-1.
• [16] Brüggemann-Klein A, Wood D. Caterpillars: A context specification technique. Markup Languages, 2000;2(1):81–106. doi:10.1162/109966200750410613.
• [17] Neven F. Automata theory for XML researchers. ACM SIGMOD Record, 2002;31(3):39–46. doi:10.1145/601858.601869.
• [18] Schwentick T. Automata for XML–A survey. Journal of Computer and System Sciences, 2007;73(3):289–315. URL https://doi.org/10.1016/j.jcss.2006.10.003.
• [19] Gécseg F, Steinby M. Tree Automata. Akadémiai Kiadó, 1984. URL arxiv.org/abs/1509.06233.