Abstract
A data tree is a tree where each node has a label from a finite set, and a data value from a possibly infinite set. We consider data trees whose depth is bounded beforehand. By developing an appropriate automaton model, we show that under this assumption various formalisms, including a two variable first-order logic and a subset of XPath, have decidable emptiness problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Milo, T., Neven, F., Suciu, D., Vianu, V.: XML with Data Values: Typechecking Revisited. In JCSS 66(4), 688–727 (2003)
Arenas, M., Fan, W., Libkin, L.: Consistency of XML specifications. In: Bertossi, L., Hunter, A., Schaub, T. (eds.) Inconsistency Tolerance. LNCS, vol. 3300, pp. 15–41. Springer, Heidelberg (2005)
Björklund, H., Schwentick, T.: On notions of regularity for data languages Manuscript (2006), available at http://lrb.cs.uni-dortmund.de/~bjork/papers/regular-data.pdf
Benedikt, M., Fan, W., Geerts, F.: XPath Satisfiability in the Presence of DTDs. In: PODS 2005
Bojańczyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on words with data. In: LICS 2006, pp. 7–16 (2006)
Bojańczyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-Variable Logic on Data Trees and XML Reasoning. In: PODS 2006 (2006)
Bouyer, P., Petit, A., Thérien, D.: An algebraic approach to data languages and timed languages. Inf. Comput. 182(2), 137–162 (2003)
Buneman, P., Davidson, S.B., Fan, W., Hara, C.S., Tan, W.C.: Reasoning about keys for XML. In Inf. Syst. 28(8), 1037–1063 (2003)
Choi, B.: What are real DTDs like. In: WebDB 2002, pp. 43–48 (2002)
Cristau, J., Löding, C., Thomas, W.: Deterministic Automata on Unranked Trees. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 68–79. Springer, Heidelberg (2005)
David, C.: Mots et données infinis. Master thesis, Université Paris 7, LIAFA (2004)
de Groote, P., Guillaume, B., Salvati, S.: Vector Addition Tree Automata. In: LICS 2004, pp. 64–73 (2004)
Demri, S., Lazic, R., Nowak, D.: On the Freeze Quantifier in Constraint LTL: Decidability and Complexity. In: TIME 2005
Demri, S., Lazic, R.: LTL with the Freeze Quantifier and Register Automata. In: LICS 2006, pp. 17–26 (2006)
Etessami, K., Vardi, M.Y., Wilke, T.: First-Order Logic with Two Variables and Unary Temporal Logic. Inf. Comput. 179(2), 279–295 (2002)
Geerts, F., Fan, W.: Satisfiability of XPath Queries with Sibling Axes. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, Springer, Heidelberg (2005)
Gottlob, G., Koch, C., Pichler, R.: Efficient Algorithms for Processing XPath Queries. In: Bressan, S., Chaudhri, A.B., Lee, M.L., Yu, J.X., Lacroix, Z. (eds.) CAiSE 2002 and VLDB 2002. LNCS, vol. 2590, Springer, Heidelberg (2003)
Grädel, E., Otto, M.: On Logics with Two Variables. TCS 224, 73–113 (1999)
Kaminski, M., Francez, N.: Finite memory automata. TCS 134, 329–363 (1994)
Kieroński, E., Otto, M.: Small Substructures and Decidability Issues for First-Order Logic with Two Variables. In: LICS 2005 (2005)
Kosaraju, S.R.: Decidability of reachability in vector addition systems. In: STOC 1982, pp. 267–281 (1982)
Lazić, R.: Safely Freezing LTL. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, Springer, Heidelberg (2006)
Martens, W.: Static analysis of XML transformation and schema. PhD Thesis, Hasselt University (2006)
Martens, W., Niehren, J.: Minimizing Tree Automata for Unranked Trees. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, Springer, Heidelberg (2005)
Marx, M.: First order paths in ordered trees. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, Springer, Heidelberg (2004)
Mayr, E.: An algorithm for the general Petri net reachability problem. In: STOC 1981, pp. 238–246 (1981)
Mortimer, M.: On languages with two variables. Zeitschr. f. math. Logik u. Grundlagen d. Math. 21, 135–140 (1975)
Neeraj Verma, K., Seidl, H., Schwentick, T.: On the Complexity of Equational Horn Clauses. In: Nieuwenhuis, R. (ed.) Automated Deduction – CADE-20. LNCS (LNAI), vol. 3632, Springer, Heidelberg (2005)
Neven, F.: Automata, Logic, and XML. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol. 2471, pp. 2–26. Springer, Heidelberg (2002)
Neven, F., Schwentick, T.: XPath Containment in the Presence of Disjunction, DTDs, and Variables. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, Springer, Heidelberg (2002)
Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log. 15(3), 403–435 (2004)
Reinhardt, K.: Counting as Method, Model and Task in Theoretical Computer Science. Habilitation-thesis (2005)
XML Path Language (XPath), W3C Recommendation (November 16, 1999) available at http://www.w3.org/TR/xpath
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Björklund, H., Bojańczyk, M. (2007). Bounded Depth Data Trees. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds) Automata, Languages and Programming. ICALP 2007. Lecture Notes in Computer Science, vol 4596. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73420-8_74
Download citation
DOI: https://doi.org/10.1007/978-3-540-73420-8_74
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73419-2
Online ISBN: 978-3-540-73420-8
eBook Packages: Computer ScienceComputer Science (R0)