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/687

Title: Query Automata
Authors: NEVEN, Frank
Schwentick, Thomas
Issue Date: 1999
Publisher: ACM Press
Citation: Neven, F. & Schwentick, T. (Ed.) PODS. p. 205-214.
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. We want 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 (MS O). Surprisingly, 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 their non-emptiness, containment, and equivalence problem to be complete for EXPTIME.
URI: http://hdl.handle.net/1942/687
ISBN: 1-58113-062-7
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A551.36 kBAdobe PDF

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