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 t...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2004-11, Vol.328 (1), p.53-75
Main Authors: Kuske, Dietrich, Meinecke, Ingmar
Format: Article
Language:English
Subjects:
Algebra
Applied sciences
Automata. Abstract machines. Turing machines
Bisemiring
Combinatorics. Ordered structures
Commutative rings and algebras
Computer science
control theory
systems
Concurrency
Exact sciences and technology
Formal power series
Mathematics
Order, lattices, ordered algebraic structures
Sciences and techniques of general use
sp-posets
Theoretical computing
Weighted automata
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Schützenberger's theorems.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2004.07.005