Simulations of weighted tree automata

DOI10.1007/978-3-642-18098-9_34MaRDI QIDQ3073652zbMATH OpenOpenAlexFDO

Authors Andreas Maletti, Zoltán Ésik

Publication date 11 February 2011

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.2079

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: Simulations of weighted tree automata (wta) are considered. It is shown how such simulations can be decomposed into simpler functional and dual functional simulations also called forward and backward simulations. In addition, it is shown in several cases (fields, commutative rings, Noetherian semirings, semiring of natural numbers) that all equivalent wta M and N can be joined by a finite chain of simulations. More precisely, in all mentioned cases there exists a single wta that simulates both M and N. Those results immediately yield decidability of equivalence provided that the semiring is finitely (and effectively) presented.

Recommendations

• THE CATEGORY OF SIMULATIONS FOR WEIGHTED TREE AUTOMATA
• A Backward and a Forward Simulation for Weighted Tree Automata
• Bisimulations for weighted automata over an additively idempotent semiring
• Bisimulation Minimisation for Weighted Tree Automata

Cites work

• scientific article; zbMATH DE number 4170851 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1257742 (Why is no real title available?)
• scientific article; zbMATH DE number 1136085 (Why is no real title available?)
• scientific article; zbMATH DE number 2040320 (Why is no real title available?)
• scientific article; zbMATH DE number 1903380 (Why is no real title available?)
• scientific article; zbMATH DE number 233974 (Why is no real title available?)
• A calculus of communicating systems
• A completeness theorem for Kleene algebras and the algebra of regular events
• Automata, Languages and Programming
• Axiomatizing the equational theory of regular tree languages
• Bisimulation Minimisation for Weighted Tree Automata
• Bisimulation relations for weighted automata
• Conjugacy and Equivalence of Weighted Automata and Functional Transducers
• Continuous monoids and semirings
• Effective construction of the syntactic algebra of a recognizable series on trees
• Représentations matricielles des séries d'arbre reconnaissables
• Tiburon: A Weighted Tree Automata Toolkit

Cited in

(7)

• Bisimulations for weighted automata over an additively idempotent semiring
• Hopf monoids in varieties
• On algebras with effectful iteration
• A Backward and a Forward Simulation for Weighted Tree Automata
• Multi-linear iterative \(K\)-\(\Sigma\)-semialgebras.
• Proper functors and fixed points for finite behaviour
• THE CATEGORY OF SIMULATIONS FOR WEIGHTED TREE AUTOMATA

Describes a project that uses

Uses Software

• MONA
• Tiburon
• Forest FIRE

This page was built for publication: Simulations of weighted tree automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073652)