Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/20632
Title: | Deciding Twig-definability of Node Selecting Tree Automata | Authors: | ANTONOPOULOS, Timos HOVLAND, Dag MARTENS, Wim NEVEN, Frank |
Issue Date: | 2015 | Publisher: | SPRINGER | Source: | THEORY OF COMPUTING SYSTEMS, 57 (4), p. 967-1007 | Abstract: | Node selecting tree automata (NSTAs) constitute a general formalism defining unary queries over trees. Basically, a node is selected by an NSTA when it is visited in a selecting state during an accepting run. We consider twig patterns as an abstraction of XPath. Since the queries definable by NSTAs form a strict superset of twig-definable queries, we study the complexity of the problem to decide whether the query by a given NSTA is twig-definable. In particular, we obtain that the latter problem is EXPTIME-complete. In addition, we show that it is also EXPTIME-complete to decide whether the query by a given NSTA is definable by a node selecting string automaton. | Notes: | [Antonopoulos, Timos; Neven, Frank] Hasselt Univ, Hasselt, Belgium. [Antonopoulos, Timos; Neven, Frank] Transnat Univ Limburg, Hasselt, Belgium. [Hovland, Dag] Univ Oslo, Oslo, Norway. [Martens, Wim] Univ Bayreuth, Bayreuth, Germany. | Keywords: | Automata; Twigs; Complexity; Definability;automata; twigs; complexity; definability | Document URI: | http://hdl.handle.net/1942/20632 | ISSN: | 1432-4350 | e-ISSN: | 1433-0490 | DOI: | 10.1007/s00224-015-9623-7 | ISI #: | 000365792200006 | Rights: | © Springer Science+Business Media New York 2015 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2016 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
art%3A10.1007%2Fs00224-015-9623-7.pdf Restricted Access | Published version | 910.31 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
1
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
1
checked on Oct 12, 2024
Page view(s)
84
checked on Sep 5, 2022
Download(s)
64
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.