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
Source: 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.
Document URI: http://hdl.handle.net/1942/687
ISBN: 1-58113-062-7
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
neven99query.pdf551.36 kBAdobe PDFView/Open
Show full item record

Page view(s)

12
checked on May 27, 2022

Download(s)

2
checked on May 27, 2022

Google ScholarTM

Check

Altmetric


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