Weighted logics for unranked tree automata (Q2429720)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Weighted logics for unranked tree automata
scientific article

    Statements

    Weighted logics for unranked tree automata (English)
    0 references
    0 references
    0 references
    1 April 2011
    0 references
    Generalizing similar work on weighted string and tree languages, on the one hand, and work on unranked tree languages, on the other hand, the authors introduce weighted tree automata and a weighted monadic second-order (MSO) logic for unranked trees (i.e., trees in which a node labeled by a given symbol may have any number of children). The resulting notions of recognizability and definability are not fully equivalent but they are closely related. More precisely, every recognizable series of unranked trees over a semiring \(S\) is definable in the weighted MSO-logic, and every series definable in a syntactically restricted form of this logic is recognizable. If \(S\) is commutative, then every recognizable series is definable by an existential formula of the restricted logic. It is also shown that, for series of ranked trees, recognizability is equivalent to definability in an appropriate variant of the restricted logic. Finally, the authors demonstrate by some examples how quantitative queries in XML-type databases can be formulated in their weighted MSO-logic.
    0 references
    weighted logics
    0 references
    monadic second-order logic
    0 references
    weighted tree automata
    0 references
    unranked trees
    0 references
    formal power series
    0 references
    tree series
    0 references
    XML queries
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references