CIAA2003

START ConferenceManager

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

Dietrich Kuske, Ingmar Meinecke

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

Costs in word or tree automata are calculated by means of a semiring. The costs along a path are multiplied, and then the costs of all successful paths with the same label are summed up. This does not provide the possibility to distinguish qualitatively between the ways of calculation of sequential as opposed to parallel compositions. 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 Schuetzenberger's theorems.