{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:11Z","timestamp":1761611231561},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,5]]},"DOI":"10.1007\/s00224-008-9151-9","type":"journal-article","created":{"date-parts":[[2008,10,24]],"date-time":"2008-10-24T14:57:46Z","timestamp":1224860266000},"page":"561-589","source":"Crossref","is-referenced-by-count":14,"title":["Axiomatizing the Logical Core of XPath\u00a02.0"],"prefix":"10.1007","volume":"44","author":[{"given":"Balder","family":"ten Cate","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,10,25]]},"reference":[{"key":"9151_CR1","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)"},{"issue":"1","key":"9151_CR2","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF01048403","volume":"4","author":"R. Backofen","year":"1995","unstructured":"Backofen, R., Rogers, J., Vijay-Shanker, K.: A first-order axiomatization of the theory of finite trees. J. Logic Lang. Inf. 4(1), 5\u201339 (1995)","journal-title":"J. Logic Lang. Inf."},{"key":"9151_CR3","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J. Assoc. Comput. Mach. 55(2), (2008)","DOI":"10.1145\/1346330.1346333"},{"issue":"1","key":"9151_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2004.10.030","volume":"336","author":"M. Benedikt","year":"2005","unstructured":"Benedikt, M., Fan, W., Kuper, G.: Structural properties of XPath fragments. Theor. Comput. Sci. 336(1), 3\u201331 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9151_CR5","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-24615-2_1","volume-title":"Theory and Applications of Relational Structures as Knowledge Instruments","author":"R. Berghammer","year":"2003","unstructured":"Berghammer, R., Schmidt, G., Winter, M.: RelView and Rath\u2014two systems for dealing with relations. In: Theory and Applications of Relational Structures as Knowledge Instruments. LNCS, vol.\u00a02929, pp.\u00a01\u201316. Springer, Berlin (2003)"},{"key":"9151_CR6","doi-asserted-by":"crossref","unstructured":"Bojanczyk, M., Muscholl, A., Schwentick, Th., Segoufin, L., David, C.: Two-variable logic on words with data. In: Proceedings LICS\u201906, pp.\u00a07\u201316 (2006)","DOI":"10.1109\/LICS.2006.51"},{"key":"9151_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59207-2","volume-title":"The Classical Decision Problem","author":"E. B\u00f6rger","year":"1997","unstructured":"B\u00f6rger, E., Gr\u00e4del, E., Gurevich, Y.: The Classical Decision Problem. Springer, Berlin (1997)"},{"key":"9151_CR8","first-page":"489","volume-title":"We will Show Them: Essays in Honour of Dov Gabbay","author":"A. Dawar","year":"2005","unstructured":"Dawar, A.: How many first-order variables are needed on finite ordered structures? In: Artemov, S., et al. (eds.) We will Show Them: Essays in Honour of Dov Gabbay, pp. 489\u2013520. College Publications, Woodend Vic. (2005)"},{"key":"9151_CR9","unstructured":"Doets, H.C.: Completeness and definability: applications of the ehrenfeucht game in intensional and second-order logic. Ph.D. Thesis, Department of Mathematics and Computer Science, University of Amsterdam (1987)"},{"key":"9151_CR10","doi-asserted-by":"crossref","unstructured":"Geerts, F., Fan, W.: Satisfiability of XPath queries with sibling axes. In: Proceedings DBPL\u201905, pp.\u00a0122\u2013137 (2005)","DOI":"10.1007\/11601524_8"},{"key":"9151_CR11","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. In: VLDB\u201902, pp.\u00a095\u2013106 (2002)","DOI":"10.1016\/B978-155860869-6\/50017-2"},{"key":"9151_CR12","doi-asserted-by":"crossref","unstructured":"Gyssens, M., Paredaens, J., Van Gucht, D., Fletcher, G.: Structural characterizations of the semantics of XPath as navigation tool on a document. In: Proceedings PODS\u201906, pp.\u00a0318\u2013327 (2006)","DOI":"10.1145\/1142351.1142397"},{"key":"9151_CR13","volume-title":"Cylindric Algebras, Part II","author":"L. Henkin","year":"1985","unstructured":"Henkin, L., Monk, J.D., Tarski, A.: Cylindric Algebras, Part II. North-Holland, Amsterdam (1985)"},{"key":"9151_CR14","series-title":"LNCS","first-page":"21","volume-title":"Proceedings DBPL","author":"J. Hidders","year":"2003","unstructured":"Hidders, J.: Satisfiability of XPath expressions. In: Proceedings DBPL. LNCS, vol.\u00a02921, pp. 21\u201336. Springer, Berlin (2003)"},{"key":"9151_CR15","volume-title":"Studies in Logic and the Foundations of Mathematics","author":"R. Hirsch","year":"2002","unstructured":"Hirsch, R., Hodkinson, I.: Relation algebras by games. In: Studies in Logic and the Foundations of Mathematics, vol.\u00a0147. North-Holland, Amsterdam (2002)"},{"key":"9151_CR16","unstructured":"Kay, M.: XPath\u00a02.0 Programmer\u2019s Reference. Wrox (2004)"},{"key":"9151_CR17","doi-asserted-by":"crossref","first-page":"707","DOI":"10.2307\/1969375","volume":"51","author":"R.C. Lyndon","year":"1950","unstructured":"Lyndon, R.C.: The representation of relation algebras. Ann. Math. 51, 707\u2013729 (1950)","journal-title":"Ann. Math."},{"key":"9151_CR18","doi-asserted-by":"crossref","first-page":"294","DOI":"10.2307\/1969611","volume":"63","author":"R.C. Lyndon","year":"1956","unstructured":"Lyndon, R.C.: The representation of relation algebras, Part II. Ann. Math. 63, 294\u2013307 (1956)","journal-title":"Ann. Math."},{"issue":"4","key":"9151_CR19","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/1114244.1114247","volume":"30","author":"M. Marx","year":"2005","unstructured":"Marx, M.: Conditional XPath. ACM Trans. Database Syst. (TODS) 30(4), 929\u2013959 (2005)","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"9151_CR20","doi-asserted-by":"crossref","first-page":"73","DOI":"10.2307\/2268577","volume":"6","author":"A. Tarski","year":"1941","unstructured":"Tarski, A.: On the calculus of relations. J. Symb. Log. 6, 73\u201389 (1941)","journal-title":"J. Symb. Log."},{"key":"9151_CR21","series-title":"AMS Colloquium Publications","doi-asserted-by":"crossref","DOI":"10.1090\/coll\/041","volume-title":"A Formalization of Set Theory without Variables","author":"A. Tarski","year":"1987","unstructured":"Tarski, A., Givant, S.: A Formalization of Set Theory without Variables. AMS Colloquium Publications, vol.\u00a041. Rhode Island, Providence (1987)"},{"key":"9151_CR22","unstructured":"ten Cate, B., Litak, T., Marx, M.: Complete axiomatizations for XPath fragments. In: Proceedings LID (Logic in Databases) Rome, Italy, 19\u201320 May 2008"},{"key":"9151_CR23","doi-asserted-by":"crossref","unstructured":"ten Cate, B., Lutz, C.: The complexity of query containment in expressive fragments of XPath\u00a02.0. In: Proceedings PODS\u201907 (2007)","DOI":"10.1145\/1265530.1265541"},{"key":"9151_CR24","volume-title":"Many-dimensional modal logic","author":"Y. Venema","year":"1992","unstructured":"Venema, Y.: Many-dimensional modal logic. Ph.D. Thesis, Institute for Logic, Language and Computation, University of Amsterdam (1992)"},{"key":"9151_CR25","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/978-94-015-8242-1_12","volume-title":"Diamonds and Defaults","author":"Y. Venema","year":"1993","unstructured":"Venema, Y.: Completeness by completeness: since and until. In: de Rijke, M. (ed.) Diamonds and Defaults, pp. 349\u2013358. Kluwer Academic, Dordrecht (1993)"},{"issue":"3","key":"9151_CR26","doi-asserted-by":"crossref","first-page":"1003","DOI":"10.2307\/2275109","volume":"58","author":"Y. Venema","year":"1993","unstructured":"Venema, Y.: Derivation rules as anti-axioms in modal logic. J. Symb. Log. 58(3), 1003\u20131034 (1993)","journal-title":"J. Symb. Log."},{"key":"9151_CR27","unstructured":"Venema, Y.: Completeness through flatness. In: Gabbay, D., Ohlbach, H.J. (eds.) Temporal Logic, First International Conference ICTL\u201994, pp.\u00a0149\u2013164 (1994)"},{"issue":"2","key":"9151_CR28","doi-asserted-by":"crossref","first-page":"591","DOI":"10.2307\/2275853","volume":"60","author":"Y. Venema","year":"1995","unstructured":"Venema, Y.: Cylindrical modal logic. J. Symb. Log. 60(2), 591\u2013623 (1995)","journal-title":"J. Symb. Log."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9151-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,7]],"date-time":"2019-04-07T07:09:05Z","timestamp":1554620945000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9151-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,25]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["9151"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9151-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,25]]}}}