1999 Best Student ICALP Paper Award

Daniel Kirsten

Daniel Kirsten:
"A connection between the star problem and the finite power property in trace monoids"
Abstract:

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 C4-submonoid [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

EATCS homepage