Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13962
Title: | Deciding twig-definability of node selecting tree automata | Authors: | ANTONOPOULOS, Timos HOVLAND, Dag MARTENS, Wim NEVEN, Frank |
Issue Date: | 2012 | Publisher: | ACM | Source: | Deutsch, Alin (Ed.). Proceedings of the 15th International Conference on Database Theory, p. 61-73 | 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 de- cide whether the query by a given NSTA is definable by a node selecting string automaton. | Keywords: | automata; twigs; complexity; definability | Document URI: | http://hdl.handle.net/1942/13962 | Link to publication/dataset: | http://dl.acm.org/citation.cfm?doid=2274576.2274584 | ISBN: | 978-1-4503-0791-8 | DOI: | 10.1145/2274576.2274584 | Rights: | Copyright 2012 ACM 978-1-4503-0791-8/12/03 | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
p61-antonopoulos.pdf | 485.54 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
3
checked on Sep 3, 2020
Page view(s)
186
checked on Nov 7, 2023
Download(s)
414
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.