Для цитирования:
Молчанов В. А. О распознавании языков произвольных слов конечными полугруппами // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2006. Т. 6, вып. 1. С. 96-108. DOI: 10.18500/1816-9791-2006-6-1-2-96-108, EDN: STBLAW
О распознавании языков произвольных слов конечными полугруппами
В настоящей работе на основе методов нестандартного анализа разрабатывается новый подход к теории бесконечных произведений в конечных полугруппах. Основные результаты работы показывают, что бесконечные произведения элементов стандартных последовательностей в конечных полугруппах могут рассматриваться как двухсторонние алгебраические дубликаты конечных произведений специального вида. С помощью этих результатов строится универсальный функтор категории конечных полугрупп в категорию конечных четырехсортных алгебр специального вида и вводится понятие языка произвольных слов, распознаваемого конечными полугруппами. Рассматриваются приложения этих методов к теории распознаваемых языков на конечных полугруппах.
- 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
- Хомский Н. Синтаксические структуры: Новое в лингвистике. М.: Прогресс, 1962. Вып. 2. С. 412–527
- Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970
- Eilenberg S., Schützenberger P. On pseudovarieties // Advances in Math. 1976. Vol. 19, № 3. P. 413–418
- Eilenberg S. Automata, Languages and Machines. Academic Press. N.Y., 1976. Vol. B
- 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
- 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
- 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
- McNaughton R. Testing and generating infinite sequences by a finite automaton // Information and Control. 1966. Vol. 9. P. 521–530
- 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
- Ramsey F.D. On a problem of formal logic// Proc. London Math. Soc. 1929. Vol.30. P. 338–384
- 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
- Альбеверио С., Фенстад Й., Хеэг-Крон Р., Линдстрем Т. Нестандартные методы в стохастическом анализе и математической физике. М.: Мир, 1990. 616 с.
- Молчанов В.А. О естественном продолжении теории рациональных языков на языки произвольных слов // Математика. Механика: Сб. науч. тр. Саратов: Изд-во Сарат. ун-та, 2004. Вып. 6. С. 90–93
- Молчанов В.А. Нестандартные сходимости в пространствах отображений // Сиб. мат. журн. 1992. Т. 33, № 6. С. 141–153
- Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985
- Кон П. Универсальная алгебра. М.: Мир, 1968
- 1268 просмотров