Geodesic
On recognition of languages of arbitrary words by finite semigroups
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 6 (2006) no. 1, pp. 96-108.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{ISU_2006_6_1_a11,
     author = {V. A. Molchanov},
     title = {On recognition of languages of arbitrary words by finite semigroups},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {96--108},
     publisher = {mathdoc},
     volume = {6},
     number = {1},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2006_6_1_a11/}
}
TY  - JOUR
AU  - V. A. Molchanov
TI  - On recognition of languages of arbitrary words by finite semigroups
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2006
SP  - 96
EP  - 108
VL  - 6
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ISU_2006_6_1_a11/
LA  - ru
ID  - ISU_2006_6_1_a11
ER  - 
%0 Journal Article
%A V. A. Molchanov
%T On recognition of languages of arbitrary words by finite semigroups
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2006
%P 96-108
%V 6
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ISU_2006_6_1_a11/
%G ru
%F ISU_2006_6_1_a11
V. A. Molchanov. On recognition of languages of arbitrary words by finite semigroups. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 6 (2006) no. 1, pp. 96-108. http://geodesic.mathdoc.fr/item/ISU_2006_6_1_a11/

[1] Pin J. E., “Finite semigroups and recognizable languages: an introduction”, Semigroups, Formal Languages and Groups, NATO ASI Series C: Mathematical and Physical Sciences, 466 (1993), 1–32 | MR

[2] Khomskii N., “Sintaksicheskie struktury”, Novoe v lingvistike, 2, Progress, M., 1962, 412–527

[3] Ginzburg S., Matematicheskaya teoriya kontekstno-svobodnykh yazykov, Mir, M., 1970

[4] Eilenberg S., Schützenberger P., “On pseudovarieties”, Advances in Math., 19:3 (1976), 413–418 | DOI | MR | Zbl

[5] Eilenberg S., Automata, Languages and Machines, v. B, Academic Press, N.Y., 1976 | Zbl

[6] Kleene S. C., “Representation of events in nerve nets and finite automata”, Automata Studies, eds. C. E. Shannon, J. McCarthy, Princeton University Press, Princeton, New Jersey, 1956, 3–42 | MR

[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, 466 (1993), 49–72 | MR

[8] Büchi J. R., “On a decision method in restricted second-order arithmetic”, Proc. 1960 Int. Congr. For Logic, Methodology and Philosophy of Science, Stanford Univ. Press, Stanford, 1962, 1–11 | MR

[9] McNaughton R., “Testing and generating infinite sequences by a finite automaton”, Information and Control, 9 (1966), 521–530 | DOI | MR | Zbl

[10] Wilke T., “An algebraic theory for regular languages of finite and infinite words”, Inter. J. of Algebra and Computation, 3 (1993), 447–489 | DOI | MR | Zbl

[11] Ramsey F. D., “On a problem of formal logic”, Proc. London Math. Soc., 30 (1929), 338–384 | MR

[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, 233–244 | MR

[13] Albeverio S., Fenstad I., Kheeg-Kron R., Lindstrem T., Nestandartnye metody v stokhasticheskom analize i matematicheskoi fizike, Mir, M., 1990, 616 pp.

[14] Molchanov V. A., “O estestvennom prodolzhenii teorii ratsionalnykh yazykov na yazyki proizvolnykh slov”, Sb. nauch. tr., Matematika. Mekhanika, 6, Izd-vo Sarat. un-ta, Saratov, 2004, 90–93 | MR

[15] Molchanov V. A., “Nestandartnye skhodimosti v prostranstvakh otobrazhenii”, Sib. mat. zhurn., 33:6 (1992), 141–153 | MR

[16] Lalleman Zh., Polugruppy i kombinatornye prilozheniya, Mir, M., 1985

[17] Kon P., Universalnaya algebra, Mir, M., 1968