Finite tree automata with cost functions

DOI10.1016/0304-3975(94)90271-2zbMath0805.68085OpenAlexW2118117473MaRDI QIDQ1325851

Helmut Seidl

Publication date: 1994

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

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90271-2

zbMATH Keywords

cost functionstropical semiringfinite tree automataarctical semiringcost automatondecidability of boundednesssemiring of finite subsets of nonnegative integerssemiring of nonnegative integers

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Semirings (16Y60)

Related Items (12)

Crisp-determinization of weighted tree automata over strong bimonoids ⋮ Weighted tree automata and weighted logics ⋮ Automata-Based Axiom Pinpointing ⋮ Automata-based axiom pinpointing ⋮ Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations ⋮ Cut sets as recognizable tree languages ⋮ Determinization of weighted finite automata over strong bimonoids ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics ⋮ Weighted automata ⋮ Decidable first-order transition logics for PA-processes

Cites Work

• Single-valuedness of tree transducers is decidable in polynomial time
• Monadic second-order evaluations on tree-decomposable graphs
• On the finite degree of ambiguity of finite tree automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finite tree automata with cost functions