1999 Best Student ICALP Paper Award

Daniel Kirsten

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

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.

EATCS homepage


e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.