Logic-based queries
Lists
Only you see this
Abstract
In this chapter we present the third approach to subtree extraction, namely, firstorder (predicate) logic, and its extension, monadic second-order logic (MSO). An advantage of using logic-based queries is that this allows a direct way of expressing retrieval conditions. That is, we do not need to specify the structure of a whole tree (as for patterns in Chapter 5) nor to navigate around the tree (as for path expressions in Chapter 12); we simply need to specify the logical relationships among relevant nodes. Furthermore MSO can express any regular queries, that is, it is at least as powerful as marking tree automata (and thus patterns). However, MSO can express no more than regular queries; indeed, any MSO formula can be translated to a marking tree automaton (Chapter 6). It does mean, however, that we can use efficient on-the-fly algorithms (Chapter 8).
BibTeX
@inproceedings{hosoya2010logic,
author = {Haruo Hosoya},
title = {{Logic-based queries}},
booktitle = {Cambridge},
year = {2010},
doi = {10.1017/cbo9780511762093.014},
}Loading related content...