Transformations Between Different Models of Unranked Bottom-Up Tree Automata

• Autorzy: Piao X. , Salomaa K.
• Języki publikacji: EN

Abstrakty

EN

We consider the representational state complexity of unranked tree automata. The bottomup computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT’05, LNCS 3623, pp. 68–79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata

Słowa kluczowe

EN

tree automata; unranked trees; state complexity; nondeterminism

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 109, nr 4
• Strony: 405--424
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Piao X.

autor

Salomaa K.

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

Bibliografia

• [1] Alur, J., Madhusudan, P.: Adding nesting structure to words, Proceedings of DLT'06, (O.H. Ibarra, Z. Dang, Eds.), LNCS 3580, Springer, 2005, 1102-1114.
• [2] Alur, J., Madhusudan, P.: Adding nesting structure to words. Journal of the ACM, 56(3), 2009.
• [3] Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets, HKUST Technical report, 2001.
• [4] Carme, J., Niehren, J., Tommasi, M.: Querying unranked trees with stepwise tree automata, Proceedings of RTA'04, LNCS 3091, Springer-Verlag, 2004, 105-118.
• [5] Champavère, J., Gilleron, R., Lemay, A., Niehren, J.: Efficient inclusion checking for deterministic tree automata and XML schemas, Information and Computation, 207, 2009, 1181-1208.
• [6] Cristau, J., Löding, C., Thomas, W.: Deterministic automata on unranked trees, Proc. of FCT'05, LNCS 3623, Springer, 2005, 68-79.
• [7] Comon, H., Dauchet,M., Gilleron, R., Jacquemard, F., Lugiez, D., Löding, C., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications, electronic book available at tata.gforge.inria.fr, 2007.
• [8] Esik, Z., Gao, Y., Liu, G., Yu, S.: Estimation of state complexity of combined operations, Theoretical Computer Science, 410(35), 2009, 3272-3280.
• [9] Gécseg, F., Steinby, M.: Tree languages, Handbook of Formal Languages, vol. III, (G. Rozenberg, A. Salomaa Eds.), Springer, 1997, 1-68.
• [10] Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata, Proc. of LATA'09, LNCS 5457, Springer, 2009, 23-42.
• [11] Holzer, M., Kutrib, M.: Nondeterministic finite automata - Recent results on the descriptional and computational complexity, International Journal of Foundations of Computer Science, 20(4), 2009, 563-580.
• [12] Liu, G., Martin-Vide, C., Salomaa, A., Yu, S.: State complexity of basic language operations combined with reversal, Information and Compututation, 206, 2008, 1178-1186.
• [13] Martens, W.: Static Analysis of XML transformation and schema languages, PhD thesis, Hasselt University, 2006.
• [14] Martens, W., Niehren, J.: On the minimization of XML schemas and tree automata for unranked trees, Journal of Computer and System Sciences, 73, 2007, 550-583.
• [15] Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers, Journal of Computer and System Sciences, 66, 2003, 66-97.
• [16] Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata, IEEE Transactions on Computers, 20, 1971, 1211-1214.
• [17] Neven, F.: Automata theory for XML researchers, SIGMOD Record, 31, 2002, 39-46.
• [18] Okhotin, A., Salomaa, K.: Descriptional complexity of unambiguous nested word automata, Proceedings of LATA 2011, LNCS 6638, Springer, 2011, to appear.
• [19] Piao, X., Salomaa, K.: Operational state complexity of nested word automata, Theoretical Computer Science, 410, 2009, 3290-3302.
• [20] Piao, X., Salomaa, K.: State trade-offs in unranked tree automata, Proceedings of DCFS 2011, Springer LNCS, to appear.
• [21] Raeymaekers, S., Bruynooghe,M.: Minimization of finite unranked tree automata, manuscript, 2004.
• [22] Schwentick, T.: Automata for XML, Journal of Computer and System Sciences, 73, 2007, 289-315.
• [23] Shallit, J.: A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2009.
• [24] Yu, S.: Regular languages, Handbook of Formal Languages, Vol. I, (G. Rozenberg, A. Salomaa, Eds.), Springer, 1997, 41-110.