|
Organizers |
Applying Semigroup Theory to Solve a Problem in Trace Theory
by
Daniel Kirsten
Dresden University of Technology
Free, partially commutative monoids, also called trace monoids are a well studied formalism to model concurrency in theoretical computer science. A central topic in trace theory is the examination of recognizable trace languages. There are two famous open decision problems: The star problem, which means to decide whether the iteration of some recognizable trace language L is recognizable, and the finite power problem which means to decide whether there is some n such that L*=L0 \cup L1 \cup ... \cup Ln. For several years, one conjectured that in some trace monoid the star problem is decidable if and only if the finite power problem is decidable in the same trace monoid. We prove this conjecture by applying ideal theory of semigroups to complete an earlier proof idea from the literature.
Date received: May 24, 2000
Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caee-76.