Query automata for nested words

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
Pages561-573
Number of pages13
DOIs
StatePublished - Sep 28 2009
Event34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 - Novy Smokovec, High Tatras, Slovakia
Duration: Aug 24 2009Aug 28 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5734 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
Country/TerritorySlovakia
CityNovy Smokovec, High Tatras
Period8/24/098/28/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Query automata for nested words'. Together they form a unique fingerprint.

Cite this