Cite this article as:
Molchanov V. A. On Recognition of Languages of Arbitrary words by Finite Semigroups. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2006, vol. 6, iss. 1, pp. 96-108. DOI: https://doi.org/10.18500/1816-9791-2006-6-1-2-96-108
On Recognition of Languages of Arbitrary words by Finite Semigroups
Based on methods of nonstandard analysis we elaborate in this paper a new approach to the theory of infinite products in finite semigroups. The main theorems of the paper show that infinite products of elements of standard sequences in finite semigroups can be viewed as a two-sided algebraic counterpart of finite products of a special kind. Using these results we construct a universal functor of the category of finite semigroups to the category of finite four-sorted algebras of a special kind and introduce a notion of a language of arbitrary words recognized by finite semigroups. Applications of these methods to the theory of recognizable languages on finite semigroups are considered.
1. Pin J.E. Finite semigroups and recognizable languages: an introduction // Semigroups, Formal Languages and Groups, NATO ASI Series C: Mathematical and Physical Sciences, 1993. Vol. 466. P. 1–32.
2. Хомский Н. Синтаксические структуры: Новое в лингвистике. М.: Прогресс, 1962. Вып. 2. С. 412–527.
3. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970.
4. Eilenberg S., Schützenberger P. On pseudovarieties// Advances in Math. 1976. Vol. 19, № 3. P. 413–418.
5. Eilenberg S. Automata, Languages and Machines. Academic Press. N.Y., 1976. Vol. B.
6. Kleene S.C. Representation of events in nerve nets and finite automata, in “Automata Studies” / Eds C. E. Shannon, J. McCarthy. Princeton University Press. Princeton; New Jersey, 1956. P. 3–42.
7. Perrin D., Pin J.E. Semigroups and automata on infinite words // Semigroups, Formal Languages and Groups, NATO ASI Series C: Mathematical and Physical Sciences, 1993. Vol. 466. P. 49–72.
8. Büchi J.R. On a decision method in restricted second-order arithmetic, in Proc. 1960 Int. Congr. For Logic, Methodology and Philosophy of Science, Stanford Univ. Press. Stanford, 1962. P. 1–11.
9. McNaughton R. Testing and generating infinite sequences by a finite automaton// Information and Control. 1966. Vol. 9. P. 521–530.
10. Wilke T. An algebraic theory for regular languages of finite and infinite words// Inter. J. of Algebra and Computation. 1993. Vol. 3. P. 447–489.
11. Ramsey F.D. On a problem of formal logic// Proc. London Math. Soc. 1929. Vol.30. P. 338–384.
12. Molchanov V.A. Nonstandard approach to general rational languages // Contributions to General Algebra 13, Proceedings of the Dresden Conference 2000 (AAA60) and the Summer School 1999, Verlag Johannes Heyn, Klagenfurt. 2001. P. 233–244.
13. Альбеверио С., Фенстад Й., Хеэг-Крон Р., Линдстрем Т. Нестандартные методы в стохастическом анализе и математической физике. М.: Мир, 1990. 616 с.
14. Молчанов В.А. О естественном продолжении теории рациональных языков на языки произвольных слов // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2004. Вып. 6. С. 90–93.
15. Молчанов В.А. Нестандартные сходимости в пространствах отображений // Сиб. мат. журн. 1992. Т. 33, № 6. С. 141–153.
16. Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985.
17. Кон П. Универсальная алгебра. М.: Мир, 1968
