{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T17:40:22Z","timestamp":1737394822625,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_74","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"862-874","source":"Crossref","is-referenced-by-count":7,"title":["Bounded Depth Data Trees"],"prefix":"10.1007","author":[{"given":"Henrik","family":"Bj\u00f6rklund","sequence":"first","affiliation":[]},{"given":"Miko\u0142aj","family":"Boja\u0144czyk","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"74_CR1","first-page":"688","volume":"66","author":"N. Alon","year":"2003","unstructured":"Alon, N., Milo, T., Neven, F., Suciu, D., Vianu, V.: XML with Data Values: Typechecking Revisited. In JCSS\u00a066(4), 688\u2013727 (2003)","journal-title":"In JCSS"},{"key":"74_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-540-30597-2_2","volume-title":"Inconsistency Tolerance","author":"M. Arenas","year":"2005","unstructured":"Arenas, M., Fan, W., Libkin, L.: Consistency of XML specifications. In: Bertossi, L., Hunter, A., Schaub, T. (eds.) Inconsistency Tolerance. LNCS, vol.\u00a03300, pp. 15\u201341. Springer, Heidelberg (2005)"},{"key":"74_CR3","unstructured":"Bj\u00f6rklund, 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"},{"key":"74_CR4","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath Satisfiability in the Presence of DTDs. In: PODS 2005","DOI":"10.1145\/1065167.1065172"},{"key":"74_CR5","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on words with data. In: LICS 2006, pp. 7\u201316 (2006)","DOI":"10.1109\/LICS.2006.51"},{"key":"74_CR6","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-Variable Logic on Data Trees and XML Reasoning. In: PODS 2006 (2006)","DOI":"10.1145\/1142351.1142354"},{"issue":"2","key":"74_CR7","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0890-5401(03)00038-5","volume":"182","author":"P. Bouyer","year":"2003","unstructured":"Bouyer, P., Petit, A., Th\u00e9rien, D.: An algebraic approach to data languages and timed languages. Inf. Comput.\u00a0182(2), 137\u2013162 (2003)","journal-title":"Inf. Comput."},{"issue":"8","key":"74_CR8","doi-asserted-by":"publisher","first-page":"1037","DOI":"10.1016\/S0306-4379(03)00028-0","volume":"28","author":"P. Buneman","year":"2003","unstructured":"Buneman, P., Davidson, S.B., Fan, W., Hara, C.S., Tan, W.C.: Reasoning about keys for XML. In Inf. Syst.\u00a028(8), 1037\u20131063 (2003)","journal-title":"In Inf. Syst."},{"key":"74_CR9","doi-asserted-by":"crossref","unstructured":"Choi, B.: What are real DTDs like. In: WebDB 2002, pp. 43\u201348 (2002)","DOI":"10.1023\/A:1022665831622"},{"key":"74_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/11537311_7","volume-title":"Fundamentals of Computation Theory","author":"J. Cristau","year":"2005","unstructured":"Cristau, J., L\u00f6ding, C., Thomas, W.: Deterministic Automata on Unranked Trees. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 68\u201379. Springer, Heidelberg (2005)"},{"key":"74_CR11","unstructured":"David, C.: Mots et donn\u00e9es infinis. Master thesis, Universit\u00e9 Paris 7, LIAFA (2004)"},{"key":"74_CR12","doi-asserted-by":"crossref","unstructured":"de Groote, P., Guillaume, B., Salvati, S.: Vector Addition Tree Automata. In: LICS 2004, pp. 64\u201373 (2004)","DOI":"10.1109\/LICS.2004.1319601"},{"key":"74_CR13","unstructured":"Demri, S., Lazic, R., Nowak, D.: On the Freeze Quantifier in Constraint LTL: Decidability and Complexity. In: TIME 2005"},{"key":"74_CR14","doi-asserted-by":"crossref","unstructured":"Demri, S., Lazic, R.: LTL with the Freeze Quantifier and Register Automata. In: LICS 2006, pp. 17\u201326 (2006)","DOI":"10.1109\/LICS.2006.31"},{"issue":"2","key":"74_CR15","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1006\/inco.2001.2953","volume":"179","author":"K. Etessami","year":"2002","unstructured":"Etessami, K., Vardi, M.Y., Wilke, T.: First-Order Logic with Two Variables and Unary Temporal Logic. Inf. Comput.\u00a0179(2), 279\u2013295 (2002)","journal-title":"Inf. Comput."},{"key":"74_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_8","volume-title":"Database Programming Languages","author":"F. Geerts","year":"2005","unstructured":"Geerts, F., Fan, W.: Satisfiability of XPath Queries with Sibling Axes. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol.\u00a03774, Springer, Heidelberg (2005)"},{"key":"74_CR17","series-title":"Lecture Notes in Computer Science","volume-title":"Efficiency and Effectiveness of XML Tools and Techniques and Data Integration over the Web","author":"G. Gottlob","year":"2003","unstructured":"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.\u00a02590, Springer, Heidelberg (2003)"},{"key":"74_CR18","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0304-3975(98)00308-9","volume":"224","author":"E. Gr\u00e4del","year":"1999","unstructured":"Gr\u00e4del, E., Otto, M.: On Logics with Two Variables. TCS\u00a0224, 73\u2013113 (1999)","journal-title":"TCS"},{"key":"74_CR19","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M. Kaminski","year":"1994","unstructured":"Kaminski, M., Francez, N.: Finite memory automata. TCS\u00a0134, 329\u2013363 (1994)","journal-title":"TCS"},{"key":"74_CR20","unstructured":"Kiero\u0144ski, E., Otto, M.: Small Substructures and Decidability Issues for First-Order Logic with Two Variables. In: LICS 2005 (2005)"},{"key":"74_CR21","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R.: Decidability of reachability in vector addition systems. In: STOC 1982, pp. 267\u2013281 (1982)","DOI":"10.1145\/800070.802201"},{"key":"74_CR22","series-title":"Lecture Notes in Computer Science","volume-title":"FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science","author":"R. Lazi\u0107","year":"2006","unstructured":"Lazi\u0107, R.: Safely Freezing LTL. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol.\u00a04337, Springer, Heidelberg (2006)"},{"key":"74_CR23","unstructured":"Martens, W.: Static analysis of XML transformation and schema. PhD Thesis, Hasselt University (2006)"},{"key":"74_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_15","volume-title":"Database Programming Languages","author":"W. Martens","year":"2005","unstructured":"Martens, W., Niehren, J.: Minimizing Tree Automata for Unranked Trees. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol.\u00a03774, Springer, Heidelberg (2005)"},{"key":"74_CR25","series-title":"Lecture Notes in Computer Science","volume-title":"Database Theory - ICDT 2005","author":"M. Marx","year":"2004","unstructured":"Marx, M.: First order paths in ordered trees. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol.\u00a03363, Springer, Heidelberg (2004)"},{"key":"74_CR26","doi-asserted-by":"crossref","unstructured":"Mayr, E.: An algorithm for the general Petri net reachability problem. In: STOC 1981, pp. 238\u2013246 (1981)","DOI":"10.1145\/800076.802477"},{"key":"74_CR27","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/malq.19750210118","volume":"21","author":"M. Mortimer","year":"1975","unstructured":"Mortimer, M.: On languages with two variables. Zeitschr. f. math. Logik u. Grundlagen d. Math.\u00a021, 135\u2013140 (1975)","journal-title":"Zeitschr. f. math. Logik u. Grundlagen d. Math."},{"key":"74_CR28","series-title":"Lecture Notes in Artificial Intelligence","volume-title":"Automated Deduction \u2013 CADE-20","author":"K. Neeraj Verma","year":"2005","unstructured":"Neeraj Verma, K., Seidl, H., Schwentick, T.: On the Complexity of Equational Horn Clauses. In: Nieuwenhuis, R. (ed.) Automated Deduction \u2013 CADE-20. LNCS (LNAI), vol.\u00a03632, Springer, Heidelberg (2005)"},{"key":"74_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/3-540-45793-3_2","volume-title":"Computer Science Logic","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata, Logic, and XML. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol.\u00a02471, pp. 2\u201326. Springer, Heidelberg (2002)"},{"key":"74_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36285-1_21","volume-title":"Database Theory - ICDT 2003","author":"F. Neven","year":"2002","unstructured":"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.\u00a02572, Springer, Heidelberg (2002)"},{"issue":"3","key":"74_CR31","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1013560.1013562","volume":"15","author":"F. Neven","year":"2004","unstructured":"Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log.\u00a015(3), 403\u2013435 (2004)","journal-title":"ACM Trans. Comput. Log."},{"key":"74_CR32","unstructured":"Reinhardt, K.: Counting as Method, Model and Task in Theoretical Computer Science. Habilitation-thesis (2005)"},{"key":"74_CR33","unstructured":"XML Path Language (XPath), W3C Recommendation (November 16, 1999) available at http:\/\/www.w3.org\/TR\/xpath"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_74.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T17:15:23Z","timestamp":1737393323000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_74","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}