On Associative Omega-Products

• Autorzy: Rędziejowski R.R.
• Języki publikacji: EN

Abstrakty

EN

In recent years, a number of classical results connecting rational languages with finite semigroups have been extended to infinite-word languages using the notion of an w-semigroup : a semigroup augmented with an associative infinite product. This paper takes a closer look at the associative infinite product itself. It suggests some improvements and presents a couple of new facts.

Słowa kluczowe

EN

semigroup; group theory; algebra; infinite product; language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 60, nr 1-4
• Strony: 333--350
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Rędziejowski R.R.

• Ceremonimästarvägen 10, S-18140 Lidingö, Sweden,

Bibliografia

• [1]. Bedon, N.: Automata, semigroups and recognizability of words on ordinals. International Journal of Algebra and Computation, 8, 1998, 1-21.
• [2]. Bruyere, V., Carton, O.: Automata on linear orderings, MFCS'2001 (J. Sgall, A. Pultr. P. Kolman, Eds.), number 2136 in Lecture Notes in Comp. Sci., Springer-Verlag, 2001.
• [3]. Biichi, J.: On a decision method in restricted second-order arithmetic. Proc. Int. Congr. on Logic, Math, and Phil, of Sci. I960, Stanford Univ. Press, Calif., 1962.
• [4]. Carton, O.: Mots infinis, ω-semigroupes et topologie, Ph.D. thesis, Université Paris 7, 1993.
• [5]. Carton, O.: Wreath products and infinite words, Journal of Pure and Applied Algebra, 153, 2000, 129-150.
• [6]. Carton, O., Perrin, D.: Chains and superchains for ω-rational sets, automata and semigroups, International Journal of Algebra and Computation, 7(7), 1997, 673-695.
• [7]. Cohn, P.: Universal Algebra. D.Reidel Publishing Company, 1981.
• [8]. Courcelle, B„ Niwiński. D., Podelski, A.: A Geometrical View of The Determinization and Minimization of Finite-State Automata, Mathematical Systems Theory, 24, 1991. 117-146.
• [9]. Perrin, D.: An introduction to finite automata on infinite words, in: Automata on Infinite Words (M. Nivat, D. Perrin, Eds.), number 192 in Lecture Notes in Comp. Sci., Springer-Verlag, Le Mont Dore, 14-18 May 1984,2-17.
• [10]. Perrin. D., Pin, J.-E.: Mots infinis, Technical Report LITP Report 93.40, Institut Blaise Pascal, Université Paris VII, 1993.
• [11]. Perrin, D., Pin, J.-E.: Semigroups and automata on infinite words, in: NATO Advanced Study Institute Semigroups, Formal Languages and Groups (J. Fountain, Ed.), Kluwer academic publishers. 1995, 49-72.
• [12]. Perrin, D., Pin, J.-E.: Infinite Words. Automata. Semigroups, Logic and Games, Number 141 in Pure and Applied Mathematics, Academic Press, 2004.
• [13]. Pin, J.-E.: Logic, semigroups and automata on words. Annals of Mathematics and Artificial Intelligence, 16, 1996, 343-384.
• [14]. Pin. J.-E.: Positive varieties and infinite words, in: LATIN 98 (C. L. Lucchesi, A. V. Moura, Eds.), number 1380 in Lecture Notes in Comp. Sci., Springer-Verlag, 1998, 76-87.
• [15]. Ramsey, F.: On a problem of formal logic, Proc. London Math. Soc. (Second Series), 30. 1930, 264-286.
• [16]. Redziejowski. R. R.: Infinite-word languages and continuous mappings, Theoretical Computer Science, 43, 1986, 59-79.
• [17]. Redziejowski. R. R.: Adding an infinite product to a semigroup, in: Automata Theory: Infinite Computations (K. Compton, J.-E. Pin, W. Thomas. Eds.), number 28 in Dagstuhl Seminar Report, Internationales Begegungs- und Forschungszentrum für Informatik Schloss Dagstuhl, 1992, page 9.
• [18]. Schützenberger, M.: A propos des relations rationelles fonctionelles, in: Automata. Languages and Programming (M. Nivat, Ed.), North Holland, 1973, 103-114.
• [19]. Słomiński. J.: The Theory of Abstract Algebras with Infinitarу Operations, Number 18 in Rozprawy Matematyczne, Polish Scientific Publishers (PWN), Warsaw, 1959.
• [20]. Staiger, L.: Finite-state .ω-languages. Journal of Computer and System Sciences. 27. 1983, 434-448.
• [21]. Therien, D.: New instruments for improving the analysis of infinitistic behaviour of programs, Technical Report CS-76-46, Dep. of Computer Sci., Univ. of Waterloo, Ont., Canada, 1976.
• [22]. Thomas, W.: A combinatorial approach to the theory of ω-automata. Information and Control, 48, 1981, 261-283.
• [23]. Wechler, W.: Universal Algebra for Computer Scientists, Number 25 in EATCS monographs on Theoretical Computer Science, Springer-Verlag, 1992.
• [24]. Wilke, Т.: An Eilenberg theorem for ∞-languages, in: Automata, Languages and Programming (J. Leach Albert, B. Monien, M. Rodriguez Artalejo, Eds.), number 510 in Lecture Notes in Comp. Sci., Springer-Verlag, 1991.588-599.
• [25]. Wilke, Т.: An algebraic theory for regular languages of finite and infinite words. International Journal of Algebra and Computation, 3(4), 1993, 447-489.