www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/13962
Link to publication: http://dl.acm.org/citation.cfm?doid=2274576.2274584
DOI: 10.1145/2274576.2274584
ISBN: 978-1-4503-0791-8
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A485.54 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.