Query automata
- 1 May 1999
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 205-214
- https://doi.org/10.1145/303976.303997
Abstract
A main task in document transformation and information retrievalis locating subtrees satisfying some pattern. Therefore, unary queries,i.e., queries that map a tree to a set of its nodes, play an importantrole in the context of structured document databases. We want to understandhow the natural and well-studied computation model of treeautomata can be used to compute such queries. We dene a queryautomaton (QA) as a deterministic two-way nite automaton overtrees that has the...Keywords
This publication has 14 references indexed in Scilit:
- A logical view of structured filesThe VLDB Journal, 1998
- Complexity results for two-way and multi-pebble automata and their logicsTheoretical Computer Science, 1996
- Integrating contents and structure in text retrievalACM SIGMOD Record, 1996
- Quantifiers and Logical ReductionsPublished by Springer Nature ,1995
- Standard Generalized Markup Language: Mathematical and philosophical issuesPublished by Springer Nature ,1995
- A Grammar-Based Approach Towards Unifying Hierarchical Data ModelsSIAM Journal on Computing, 1994
- On two-way tree automataInformation Processing Letters, 1994
- Generalizations of regular sets and their application to a study of context-free languagesInformation and Control, 1975
- Définition et etude des Bilangages réguliersInformation and Control, 1968
- An Approach to a Unified Theory of AutomataBell System Technical Journal, 1967