Abstract-We develop the theory of regular cost functions over finite trees: a quantitative extension to the notion of regular languages of trees: Cost functions map each input (tree) to a value in ω + 1, and are considered modulo an equivalence relation which forgets about specific values, but preserves boundedness of functions on all subsets of the domain. We introduce nondeterministic and alternating finite tree cost automata for describing cost functions. We show that all these forms of automata are effectively equivalent. We also provide decision procedures for them. Finally, following Büchi's seminal idea, we use cost automata for providing decision procedures for cost monadic logic, a quantitative extension of monadic second order logic.
In REF , the authors extend this notion to regular cost functions over trees.
Regular Cost Functions over Finite Trees
2010 25th Annual IEEE Symposium on Logic in Computer Science
2010 25th Annual IEEE Symposium on Logic in Computer Science
Mathematics Computer Science