TY - GEN
T1 - Query automata for nested words
AU - Madhusudan, P.
AU - Viswanathan, Mahesh
PY - 2009
Y1 - 2009
N2 - We study visibly pushdown automata (VPA) models for expressing and evaluating queries on words with a nesting structure. We define a query VPA model, which is a 2-way deterministic VPA that can mark in one run all positions in a document that satisfy a query, and show that it is equi-expressive as unary monadic queries. This surprising result parallels a classic result by Hopcroft and Ullman for queries on regular word languages. We also compare our model to query models on unranked trees, and show that our result is fundamentally different from those known for automata on trees.
AB - We study visibly pushdown automata (VPA) models for expressing and evaluating queries on words with a nesting structure. We define a query VPA model, which is a 2-way deterministic VPA that can mark in one run all positions in a document that satisfy a query, and show that it is equi-expressive as unary monadic queries. This surprising result parallels a classic result by Hopcroft and Ullman for queries on regular word languages. We also compare our model to query models on unranked trees, and show that our result is fundamentally different from those known for automata on trees.
UR - http://www.scopus.com/inward/record.url?scp=70349332749&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349332749&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03816-7_48
DO - 10.1007/978-3-642-03816-7_48
M3 - Conference contribution
AN - SCOPUS:70349332749
SN - 3642038158
SN - 9783642038150
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 561
EP - 573
BT - Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
T2 - 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
Y2 - 24 August 2009 through 28 August 2009
ER -