Please use this identifier to cite or link to this item:
Title: Query automata over finite trees
Authors: NEVEN, Frank 
Schwentick, Thomas
Issue Date: 2002
Publisher: Elsevier
Source: Theoretical Computer Science, 275(1-2). p. 633-674
Abstract: A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an important role in the context of structured document databases. The motivation of this work is to understand how the natural and well-studied computation model of tree automata can be used to compute such queries. We define a query automaton (QA) as a deterministic two-way finite automaton over trees that has the ability to select nodes depending on the state and the label at those nodes. We study QAs over ranked as well as over unranked trees. Unranked trees differ from ranked ones in that there is no bound on the number of children of nodes. We characterize the expressiveness of the different formalisms as the unary queries definable in monadic second-order logic (MSO). In contrast to the ranked case, special stay transitions had to be added to QAs over unranked trees to capture MSO. We establish the complexity of the non-emptiness, containment, and equivalence of QAs to be complete for EXPTIME.
Document URI:
ISSN: 0304-3975
e-ISSN: 1879-2294
DOI: 10.1016/S0304-3975(01)00301-2
ISI #: 000175989300020
Category: A1
Type: Journal Contribution
Validations: ecoom 2003
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
19neven.pdf524.17 kBAdobe PDFView/Open
Show full item record

Google ScholarTM



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