Образец для цитирования:
Молчанов В. А. О распознавании языков произвольных слов конечными полугруппами // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2006. Т. 6, вып. 1. С. 96-108. DOI: https://doi.org/10.18500/1816-9791-2006-6-1-2-96-108
О распознавании языков произвольных слов конечными полугруппами
В настоящей работе на основе методов нестандартного анализа разрабатывается новый подход к теории бесконечных произведений в конечных полугруппах. Основные результаты работы показывают, что бесконечные произведения элементов стандартных последовательностей в конечных полугруппах могут рассматриваться как двухсторонние алгебраические дубликаты конечных произведений специального вида. С помощью этих результатов строится универсальный функтор категории конечных полугрупп в категорию конечных четырехсортных алгебр специального вида и вводится понятие языка произвольных слов, распознаваемого конечными полугруппами. Рассматриваются приложения этих методов к теории распознаваемых языков на конечных полугруппах.
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
