Simulations of Weighted Tree Automata

Details Simulations of Weighted Tree Automata Simulations of Weighted Tree Automata

2010-05-12

arxiv.org/abs/1005.2079v1

Computer Science

Formal Languages and Automata Theory

17 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Simulations of Weighted Tree Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simulations of Weighted Tree Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simulations of Weighted Tree Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-499532