FINITE TREE AUTOMATA WITH COST-FUNCTIONS

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 ''arctical semiring'', 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 Lime whether or not the cardinality of occurring cost sets is bounded. In all three cases wc 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 wc extend our results to multi-dimensional cost functions.