Branching automata with costs - a way of reflecting parallelism in costs

摘要

Extending work by Lodaya and Weil, we propose a model of branching automata with costs in which the calculation of the cost of a parallel composition is handled differently from the calculation of the cost of a sequential composition. Our main result characterizes the behavior of these automata in the spirit of Kleene's and Schiitzenberger's theorems.