Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Молчанов В. А. О распознавании языков произвольных слов конечными полугруппами // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2006. Т. 6, вып. 1. С. 96-108. DOI: 10.18500/1816-9791-2006-6-1-2-96-108, EDN: STBLAW

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
18.10.2006
Полный текст:
(downloads: 170)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.4
EDN: 
STBLAW

О распознавании языков произвольных слов конечными полугруппами

Авторы: 
Молчанов Владимир Александрович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

В настоящей работе на основе методов нестандартного анализа разрабатывается новый подход к теории бесконечных произведений в конечных полугруппах. Основные результаты работы показывают, что бесконечные произведения элементов стандартных последовательностей в конечных полугруппах могут рассматриваться как двухсторонние алгебраические дубликаты конечных произведений специального вида. С помощью этих результатов строится универсальный функтор категории конечных полугрупп в категорию конечных четырехсортных алгебр специального вида и вводится понятие языка произвольных слов, распознаваемого конечными полугруппами. Рассматриваются приложения этих методов к теории распознаваемых языков на конечных полугруппах. 

Ключевые слова: 
Список источников: 
  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
Поступила в редакцию: 
12.04.2006
Принята к публикации: 
02.09.2006
Опубликована: 
18.10.2006