Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

For citation:

Molchanov V. A. On Recognition of Languages of Arbitrary words by Finite Semigroups. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2006, vol. 6, iss. 1, pp. 96-108. DOI: 10.18500/1816-9791-2006-6-1-2-96-108, EDN: STBLAW

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
18.10.2006
Full text:
download
(downloads: 156)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.4
DOI: 
10.18500/1816-9791-2006-6-1-2-96-108
EDN: 
STBLAW

On Recognition of Languages of Arbitrary words by Finite Semigroups

Autors: 
Molchanov Vladimir Aleksandrovich, Saratov State University
Abstract: 

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.

Key words: 
semigroup
References: 
  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
Received: 
12.04.2006
Accepted: 
02.09.2006
Published: 
18.10.2006
  • 950 reads