Star-free Star and Trace Languages

Issue title: SPECIAL ISSUE ON CONCURRENCY SPECIFICATION AND PROGRAMMING (CS&P 2005) Ruciane-Nide, Poland, 28–30 September 2005

Article type: Research Article

Authors: Ochmański, Edward | Stawikowska, Krystyna

Affiliations: Faculty of Mathematics and Computer Science Nicolaus Copernicus University, Toruń, Poland. E-mails: edoch@mat.uni.torun.pl; entropia@mat.uni.torun.pl

Abstract: The paper deals with star-free languages in free monoids and trace monoids. We introduce the notion of star-free star, fundamental for this paper, and show that the classes of star-free languages and star-free star languages coincide. Then, using this result, we obtain a general characterization of star-free trace languages, containing a result of Guaiana/Restivo/Salemi (star-free=aperiodic in trace monoids), originally proved in a more involved, combinatorial way.

Keywords: star-free languages, traces languages

Journal: Fundamenta Informaticae, vol. 72, no. 1-3, pp. 323-331, 2006