On-the-fly algorithms

Haruo HosoyaCambridge 2010 · DOI · OpenAlex

Abstract

This chapter presents efficient algorithms for several important problems related to XML processing, namely: (1) membership for tree automata (to test whether a given tree is accepted by a given tree automaton); (2) evaluation of marking tree automata (to collect the set of bindings yielded by the matching of a given tree against a given marking tree automaton); and (3) containment for tree automata (to test whether the languages of given two tree automata are in subset relation). For these problems we describe several “on-the-fly” algorithms, in which only a part of the whole state space is explored to obtain the final result. In such algorithms there are two basic approaches, top-down and bottom-up. The top-down approach explores the state space from the initial states whereas the bottom-up approach does this from the final states. In general, the bottom-up approach tends to have a lower complexity in the worst case whereas the top-down often gives a higher efficiency in practical cases. We will also consider a further improvement from combining these ideas.
BibTeX
@inproceedings{hosoya2010fly,
  author = {Haruo Hosoya},
  title = {{On-the-fly algorithms}},
  booktitle = {Cambridge},
  year = {2010},
  doi = {10.1017/cbo9780511762093.009},
}

Loading related content...

Figure