Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/16522
Title: | Extending two-variable logic on data trees with order on data values and its automata | Authors: | TAN, Tony | Issue Date: | 2014 | Source: | ACM Transactions on Computational Logic, 15(1), (ART N° 8) | Abstract: | Data trees are trees in which each node, besides carrying a label from a finite alphabet, also carries a data value from an infinite domain. They have been used as an abstraction model for reasoning tasks on XML and verification. However, most existing approaches consider the case where only equality test can be performed on the data values. In this paper we study data trees in which the data values come from a linearly ordered domain, and in addition to equality test, we can test whether the data value in a node is greater than the one in another node. We introduce an automata model for them which we call ordered-data tree automata (ODTA), provide its logical characterisation, and prove that its non-emptiness problem is decidable in 3-NExpTime. We also show that the two-variable logic on unranked data trees, studied by Bojanczyk, Muscholl, Schwentick and Segoufin in 2009, corresponds precisely to a special subclass of this automata model. Then we define a slightly weaker version of ODTA, which we call weak ODTA, and provide its logical characterisation. The complexity of the non-emptiness problem drops to NP. However, a number of existing formalisms and models studied in the literature can be captured already by weak ODTA. We also show that the definition of ODTA can be easily modified, to the case where the data values come from a tree-like partially ordered domain, such as strings. | Notes: | Tan, T (reprint author), Hasselt Univ, Diepenbeek, Belgium, | Keywords: | finite-state automata; two-variable logic; data trees; ordered data values | Document URI: | http://hdl.handle.net/1942/16522 | ISSN: | 1529-3785 | e-ISSN: | 1557-945X | DOI: | 10.1145/2559945 | ISI #: | 000332383000008 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2015 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tan_extending.pdf | Published version | 433.49 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
8
checked on Sep 7, 2020
WEB OF SCIENCETM
Citations
9
checked on Sep 28, 2024
Page view(s)
60
checked on Sep 5, 2022
Download(s)
172
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.