Helmut Seidl. Finite Tree Automata with Cost Functions. Theor. Comput. Sci., 126(1):113-142, 1994.

Cost functions for tree automata are mappings from transitions to (tuples of) polynomials over some semiring. We consider four semirings, namely, the semiring of nonnegative integers, the “arctical semiring”. the tropical semiring and the semiring of finite subsets of nonnegative integers. We show: for semirings and it is decidable in polynomial time whether or not the costs of accepting computations is bounded; for it is decidable in polynomial time whether or not the cardinalities of occurring cost sets are bounded. In all three cases, we derive explicit upper bounds. For semiring , we prove decidability of boundedness as well, but obtain a polynomial-time algorithm only in case that the degrees of occurring polynomials are at most . For and , we extend our results to multidimensional cost functions.

Download: PDF Reference: Bibtex