Weighted tree automata and weighted logics

DOI10.1016/j.tcs.2006.08.025zbMath1154.68068OpenAlexW2087912140MaRDI QIDQ860890

Manfred Droste, Heiko Vogler

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.08.025

zbMATH Keywords

tree automataformal power seriesweighted automataMSO logics

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70)

Related Items (39)

Crisp-determinization of weighted tree automata over strong bimonoids ⋮ A note on cut-worthiness of recognizable tree series ⋮ Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids ⋮ Weighted automata and weighted logics ⋮ Weighted automata and weighted logics with discounting ⋮ Weighted automata and weighted logics on infinite words ⋮ Weighted Automata and Weighted Logics ⋮ Weighted Unranked Tree Automata over Tree Valuation Monoids and Their Characterization by Weighted Logics ⋮ Weighted automata and weighted MSO logics for average and long-time behaviors ⋮ Weighted Automata and Weighted Logics with Discounting ⋮ A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings ⋮ Unnamed Item ⋮ A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices ⋮ Learning Tree Languages ⋮ Weighted logics for unranked tree automata ⋮ Weighted picture automata and weighted logics ⋮ Weighted Logics for Nested Words and Algebraic Formal Power Series ⋮ Weighted monadic Datalog ⋮ Weighted automata and logics for infinite nested words ⋮ A Büchi-like theorem for weighted tree automata over multioperator monoids ⋮ Pebble Weighted Automata and Weighted Logics ⋮ MSO logics for weighted timed automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic ⋮ Characterizations of recognizable weighted tree languages by logic and bimorphisms ⋮ A unifying survey on weighted logics and weighted automata. Core weighted logic: minimal and versatile specification of quantitative properties ⋮ Kleene and Büchi theorems for weighted forest languages over M-monoids ⋮ Weighted Automata and Logics on Infinite Graphs ⋮ On Finite and Polynomial Ambiguity of Weighted Tree Automata ⋮ Automatic Termination ⋮ Weighted versus Probabilistic Logics ⋮ Weighted Timed MSO Logics ⋮ Weighted operator precedence languages ⋮ Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics ⋮ Weighted automata and multi-valued logics over arbitrary bounded lattices ⋮ Weighted Operator Precedence Languages ⋮ Characterizing weighted MSO for trees by branching transitive closure logics ⋮ A link between multioperator and tree valuation automata and logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Effective construction of the syntactic algebra of a recognizable series on trees
• Recognizable formal power series on trees
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Equational elements in additive algebras
• Finite tree automata with cost functions
• Tree automata for code selection
• Logical description of context-free graph languages
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• A Kleene theorem for weighted tree automata
• Cut sets as recognizable tree languages
• Tree acceptors and some of their applications
• On the Determinization of Weighted Finite Automata
• Weak Second‐Order Arithmetic and Finite Automata
• On the definition of a family of automata
• Deciding Equivalence of Finite Tree Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Bottom-up and top-down tree transformations— a comparison
• Some remarks on recognizable treeseries
• On the Determinization of Weighted Finite Automata
• Implementation and Application of Automata
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Automata, Languages and Programming

This page was built for publication: Weighted tree automata and weighted logics