Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/20632
DOI: 10.1007/s00224-015-9623-7
ISI #: 000365792200006
ISSN: 1432-4350
Category: A1
Type: Journal Contribution
Validation: ecoom, 2016
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
published version910.31 kBAdobe PDF

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