Helmut Seidl. Finite Tree Automata with Cost Functions. In Jean-Claude Raoult, editor, Trees in Algebra and Programming, volume 581 of Lecture Notes in Computer Science, pages 279-299, Rennes, France, February 1992. Springer.

Cost functions for tree automata are mappings from transitions to (tuples of) polynomials over some semiring. We consider four semirings, namely $N$ the semiring of nonnegative integers, $A$ the ldquoarctical semiringrdquo, $T$ the tropical semiring and $F$ the semiring of finite subsets of nonnegative integers. We show: for semirings $N$ and $A$ it is decidable in polynomial time whether or not the costs of accepting computations is bounded; for $F$ it is decidable in polynomial time whether or not the cardinality of occurring cost sets is bounded. In all three cases we derive explicit upper bounds. For semiring $T$ we are able to derive similar results at least in case of polynomials of degree at most 1. For $N$ and $A$ we extend our results to multi-dimensional cost functions.

Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com