Weighted logics for unranked tree automata (Q2429720): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00224-009-9224-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2040997422 / rank | |||
Normal rank |
Revision as of 21:03, 19 March 2024
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
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