Abstract
In a data word or a data tree each position carries a label from a finite alphabet and a data value from an infinite domain.
Over data words we consider the logic \({\sf LTL}^{\downarrow}_{1}(\rm F)\), that extends LTL( F) with one register for storing data values for later comparisons. We show that satisfiability over data words of \({\sf LTL}^{\downarrow}_{1}(\rm F)\) is already non primitive recursive. We also show that the extension of \({\sf LTL}^{\downarrow}_{1}(\rm F)\) with either the backward modality F − 1 or with one extra register is undecidable. All these lower bounds were already known for \({\sf LTL}^{\downarrow}_{1}({\rm X,F})\) and our results essentially show that the X modality was not necessary.
Moreover we show that over data trees similar lower bounds hold for certain fragments of Xpath.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J. ACM 55(2) (2008)
Björklund, H., Martens, W., Schwentick, T.: Optimizing conjunctive queries over trees using schema information. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 132–143. Springer, Heidelberg (2008)
Bojańczyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. In: PODS, pp. 10–19 (2006)
Bojańczyk, M., Muscholl, A., Schwentick, T., Segoufin, L., David, C.: Two-variable logic on words with data. In: LICS, pp. 7–16 (2006)
Bouyer, P., Petit, A., Thérien, D.: An algebraic approach to data languages and timed languages. Inf. Comput. 182(2), 137–162 (2003)
Clark, J., DeRose, S.: XML path language (XPath) (1999), W3C Recommendation, http://www.w3.org/TR/xpath
David, C.: Complexity of data tree patterns over XML documents. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 278–289. Springer, Heidelberg (2008)
Demri, S., Lazić, R.: LTL with the freeze quantifier and register automata. ACM Transactions on Computational Logic (2009)
Demri, S., Lazić, R., Nowak, D.: On the freeze quantifier in constraint LTL: Decidability and complexity. In: TIME, pp. 113–121 (2005)
Figueira, D.: Satisfiability of downward XPath with data equality tests. In: PODS, Providence, Rhode Island, USA. ACM Press, New York (2009)
Geerts, F., Fan, W.: Satisfiability of XPath queries with sibling axes. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 122–137. Springer, Heidelberg (2005)
Jurdziński, M., Lazić, R.: Alternating automata on data trees and XPath satisfiability. CoRR, abs/0805.0330 (2008)
Minsky, M.L.: Computation: finite and infinite machines. Prentice-Hall, Inc., Englewood Cliffs (1967)
Ouaknine, J., Worrell, J.: On Metric temporal logic and faulty Turing machines. In: Aceto, L., Ingólfsdóttir, A. (eds.) FOSSACS 2006. LNCS, vol. 3921, pp. 217–230. Springer, Heidelberg (2006)
Schnoebelen, P.: Verifying lossy channel systems has nonprimitive recursive complexity. Information Processing Letters 83(5), 251–261 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Figueira, D., Segoufin, L. (2009). Future-Looking Logics on Data Words and Trees. In: Královič, R., Niwiński, D. (eds) Mathematical Foundations of Computer Science 2009. MFCS 2009. Lecture Notes in Computer Science, vol 5734. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03816-7_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-03816-7_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03815-0
Online ISBN: 978-3-642-03816-7
eBook Packages: Computer ScienceComputer Science (R0)