Simulations of weighted tree automata

DOI10.1007/978-3-642-18098-9_34zbMATH Open1297.68125arXiv1005.2079OpenAlexW3123881330MaRDI QIDQ3073652FDOQ3073652

Authors: Andreas Maletti, Zoltán Ésik 

Publication date: 11 February 2011

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Tiburon: A Weighted Tree Automata Toolkit
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Axiomatizing the equational theory of regular tree languages
• Title not available (Why is that?)
• A calculus of communicating systems
• Bisimulation relations for weighted automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• A completeness theorem for Kleene algebras and the algebra of regular events
• Title not available (Why is that?)
• Conjugacy and Equivalence of Weighted Automata and Functional Transducers
• Automata, Languages and Programming
• Continuous monoids and semirings
• Représentations matricielles des séries d'arbre reconnaissables
• Effective construction of the syntactic algebra of a recognizable series on trees
• Title not available (Why is that?)
• Bisimulation Minimisation for Weighted Tree Automata

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

Uses Software

• Forest FIRE
• Tiburon
• MONA

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)