|
Organizers |
On Semigroups of Partial Injective Endomorphisms of Graphs
by
Inna Terekhina
Saratov State University, Saratov, Russia
The purpose of this talk is to state recent results of investigation of the interplay between a graph G and the semigroup PIEnd(G) of all partial injective endomorphisms of G. The main idea of our approach is to study the following concrete characterization problem for these semigroups:
under which conditions for a semigroup S of partial injective transformations of a set X there exists a graph G=(X, E), such that S=PIEnd(G) ?
By analogy with [1], the main tools of these investigations of the semigroups of all partial injective endomorphisms of graphs are canonical relations of semigroups of partial injective transformations, which are defined in these semigroups by formulas of the lower predicate language. This approach makes it possible to study the concrete characterization problem for the semigroups of all partial injective endomorphisms of graphs and to construct a relatively elementary interpretation of the class of graphs in the class of semigroups. Using these methods we obtain the following results:
These results can also be applied to investigation of partial injective automata the state sets and the exit sets of which endowed with algebraic structures of graphs.
REFERENCE
[1] V. A. Molchanov , Concrete characterization of partial endomorphism semigroups of graphs , Acta Sci. Math. 51 (1987) 349-363.
Date received: May 3, 2000
Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caec-15.