On the Shuffle of Star-Free Languages

• Autorzy: Castiglione G. , Restivo A.
• Języki publikacji: EN

Abstrakty

EN

Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is starfree. Some of the special cases here approached give rise to new problems in combinatorics on words.

Słowa kluczowe

EN

regular language; star-free languages; shuffle of languages; pure submonoids; combinatorics on words

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 35--44
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Castiglione G.

autor

Restivo A.

• Dipartimento di Matematica e Informatica, Universita di Palermo Via Archirafi 34, 90123 Palermo, Italy,

Bibliografia

• [1] Baeten, J., Weijland, W.: Process Algebra, Cambridge University Press, 1990.
• [2] Berstel, J., Boasson, L., Carton, O., Pin, J.-E., Restivo, A.: The expressive power of the shuffle product, Inf. Comput., 208(11), 2010, 1258-1272.
• [3] Eilenberg, S.: Automata, Languages, and Machines, Academic Press, Inc., Orlando, FL, USA, 1976.
• [4] Huang, C. C.: A note on pure codes, Acta Inf., 47, 2010, 347-357.
• [5] Lothaire, M.: Algebraic Combinatorics on Words, Cambridge University Press, 2002.
• [6] Lyndon, R. C., Schützenberger, M. P.: The equation aM = bNcP in a free group, Michigan Math. J., 9(4), 1962, 289-298.
• [7] McNaughton, R., Papert, S.: Counter-Free Automata, MIT Press, Cambridge, 1971.
• [8] Perrin, D.: Finite Automata, in: Handbook of Theoretical Computer Science, Formal Models and Sematics, vol. B, Elsevier and MIT Press, 1990, 1-57.
• [9] Perrot, J. F.: Varietes de Langages et Operations, Theor. Comput. Sci., 7, 1978, 197-210.
• [10] Pin, J.-E.: Semigroupe des parties et relations de Green, Canadian Journal of Math, 36, 1984, 327-343.
• [11] Pin, J.-E.: Varieties of formal languages, North Oxford, LondonPlenum, New-York, 1986, (Traduction de Variétés de langages formels).
• [12] Pin, J.-E.: Syntactic semigroups, in: Handbook of formal languages (G. Rozenberg, A. Salomaa, Eds.), vol. 1, chapter 10, Springer, 1997, 679-746.
• [13] Putcha, M. S.: Subgroups of the Power Semigroup of a Finite Semigroup, Can. J. Math., 31(5), 1979, 1077-1083.
• [14] Restivo, A.: Codes and aperiodic languages, Lecture Notes in Computer Science, 2, Springer, 1973, 175-181.
• [15] Schützenberger, M. P.: On Finite Monoids Having Only Trivial Subgroups, Information and Control, 8(2), 1965, 190-194.
• [16] Schützenberger,M. P.: Sur le Produit de concaténation non Ambigu, Semigroup Forum, 13(1), 1976, 47-75.
• [17] Shyr, H. J., Yu, S. S.: Non-primitive words in the Language p+q+, Soochow J. Math., 20(4), 1994, 535-546.
• [18] Silva, P. V.: An Application of First-Order Logic to The Study of Recognizable Languages, IJAC, 14(5-6), 2004, 785-799.
• [19] Tesson, P., Therien, D.: Diamonds Are Forever: The Variety DA, Semigroups, Algorithms, Automata and Languages, Coimbra (Portugal) 2001,World Scientific, 2002, 475-500.