Star-free Star and Trace Languages

• Autorzy: Ochmański, E. , Stawikowska, K.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

star-free languages; trace language

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 72, nr 1-3
• Strony: 323-331
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Ochmański, E.

autor

Stawikowska, K.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland

Bibliografia

• [1] Guaiana, G., Restivo, A., Salemi, S.: Star-free trace languages. Theoretical Computer Science, 97, 1992, 301-311 .
• [2] Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 2001.
• [3] Mazurkiewicz, A.: Concurrent program schemes and their interpretations. Report DAIMI-PB-78, Aarhus University, 1977.
• [4] McNaughton, R., Yamada, R.: Regular expressions and state graphs for automata. Trans. of IRE EC-9(1), 1960, 11-18.
• [5] Ochmański, E., Stawikowska, K.: On closures of lexicographic star-free languages. Proc. of 11th International Conference on Automata and Formal Languages (AFL'05), Institute of Informatics, University of Szeged, Hungary, 2005, 227-234.
• [6] Perrin, D.: Finite Automata, Handbook of Theoretical Computer Science, vol. B, Elsevier, 1990, 1-57.
• [7] Schützenberger, M. P.: On finite monoids having only trivial subgroups, Information and Control, 8 , 1965, 190-194.