1999 Best Student ICALP Paper AwardDaniel Kirsten Daniel Kirsten: This paper deals with a connection between two decision problems for recognizable trace languages: the star problem and the finite power problem. Both problems are decidable in trace monoids without C4submonoid [Richomme 1994] but remain open in all other trace monoids. We show a connection between these problems. Assume two disjoint trace monoids M(\Sigma_1,I_1) and M(\Sigma_2,I_2). Assume further a recognizable language L\subseteq\Mon(\Sigma_1,I_1)\times\Mon(\Sigma_2,I_2) such that every trace in L contains at least one letter in \Sigma_1 and at least one letter in \Sigma_2. Our main theorem asserts that L^* is recognizable iff L has the finite power property. Back
