共查询到20条相似文献,搜索用时 15 毫秒
1.
本文研究图及其强自同态幺半群.首先刻画了图的强自同态幺半群的正则元,然后给出了此幺半群正则的充要条件.这推广了[1]和[2]中关于有限图的强自同态幺半群正则的结果. 相似文献
2.
3.
Endomorphisms of graphs II. Various unretractive graphs 总被引:2,自引:0,他引:2
Ulrich Knauer 《Archiv der Mathematik》1990,55(2):193-203
In this part of the article we investigate graphs for which different endomorphism monoids coincide. We consider endomorphisms, strong endomorphisms and automorphisms. Coincidences are investigated for joins of graphs and some lexicographic products. In an additional section the graphs with the respective properties are listed up to 8 vertices in two cases and up to 5 vertices in the remaining case. 相似文献
4.
Pedro V. Silva 《Monatshefte für Mathematik》2010,144(2):417-447
Cayley graphs of monoids defined through special confluent rewriting systems are known to be hyperbolic metric spaces which
admit a compact completion given by irreducible finite and infinite words. In this paper, we prove that the fixed point submonoids
for endomorphisms of these monoids which are boundary injective (or have bounded length decrease) are rational, with similar
results holding for infinite fixed points. Decidability of these properties is proved, and constructibility is proved for
the case of bounded length decrease. These results are applied to free products of cyclic groups, providing a new generalization
for the case of infinite fixed points. 相似文献
5.
We consider endomorphism monoids of graphs. It is well-known that any monoid can be represented as the endomorphism monoid M of some graph Γ with countably many colors. We give a new proof of this theorem such that the isomorphism between the endomorphism monoid $\mathop{\rm End}\nolimits (\Gamma)We consider endomorphism monoids of graphs. It is well-known that any monoid can be represented as the endomorphism monoid
M of some graph Γ with countably many colors. We give a new proof of this theorem such that the isomorphism between the endomorphism
monoid
and M is absolute, i.e.
holds in any generic extension of the given universe of set theory. This is true if and only if |M|,|Γ| are smaller than the first Erdős cardinal (which is known to be strongly inaccessible). We will encode Shelah’s absolutely
rigid family of trees (Isr. J. Math. 42(3), 177–226, 1982) into Γ. The main result will be used to construct fields with prescribed absolute endomorphism monoids, see G?bel and Pokutta
(Shelah’s absolutely rigid trees and absolutely rigid fields, in preparation).
This work was supported by the project No. I-706-54.6/2001 of the German-Israeli Foundation for Scientific Research & Development
and a fellowship within the Postdoc-Programme of the German Academic Exchange Service (DAAD). 相似文献
6.
Pedro V. Silva 《Monatshefte für Mathematik》2010,161(4):417-447
Cayley graphs of monoids defined through special confluent rewriting systems are known to be hyperbolic metric spaces which admit a compact completion given by irreducible finite and infinite words. In this paper, we prove that the fixed point submonoids for endomorphisms of these monoids which are boundary injective (or have bounded length decrease) are rational, with similar results holding for infinite fixed points. Decidability of these properties is proved, and constructibility is proved for the case of bounded length decrease. These results are applied to free products of cyclic groups, providing a new generalization for the case of infinite fixed points. 相似文献
7.
Let X be a graph, S End X be its strong endomorphism monoid. It is proved that S End X is a regular monoid if and only if the canonical strong factor graph U of X contains no proper subgraph which is isomorphic to U. The result generalizes that of U. Knauer about the regularity of strong endomorphism monoids of graphs. 相似文献
8.
Manuel Bodirsky David Evans Michael Kompatscher Michael Pinsker 《Israel Journal of Mathematics》2018,224(1):57-82
We present an example of two countable ω-categorical structures, one of which has a finite relational language, whose endomorphism monoids are isomorphic as abstract monoids, but not as topological monoids—in other words, no isomorphism between these monoids is a homeomorphism. For the same two structures, the automorphism groups and polymorphism clones are isomorphic, but not topologically isomorphic. In particular, there exists a countable ω-categorical structure in a finite relational language which can neither be reconstructed up to first-order biinterpretations from its automorphism group, nor up to existential positive bi-interpretations from its endomorphism monoid, nor up to primitive positive bi-interpretations from its polymorphism clone. 相似文献
9.
In this paper we investigate under which conditions a monoid R is defined by the endomorphism monoid of an act over R. More
precisely, we ask when an isomorphism between two such endomorphism monoids over monoids R1 and R2 is induced by a semilinear isomorphism. The question is considered also for ordered and for topological monoids. On the way
we characterize monoids over which all projective acts are free. An abstract of this paper appeared in the Proceedings of
the Conference on Semigroups, Szeged 1972. 相似文献
10.
Monoids and acts which may have zero elements are considered. In Section 1 we construct a O-wreath product of monoids. In
2 we prove the theorem that the endomorphism monoid of a free act over a monoid with zero can be represented as a O-wreath
product. Considering monoids with tero we are interested in their annihilator properties. In 3 we give necessary and sufficient
conditions for a O-wreath product of monoids to be a right (left) Baer (Rickart) monoid. In 4 we obtain as a consequence corresponding
conditions for the endomorphism monoid of a free act over a monoid with zero. 相似文献
11.
Sr. Arworn 《Discrete Mathematics》2009,309(1):94-1307
An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. In this paper we provide an algorithm to determine the cardinalities of endomorphism monoids of finite undirected paths. 相似文献
12.
Yurii V. Zhuchok 《Algebra Universalis》2016,76(3):355-366
We describe all endomorphisms of a free trioid of rank 1 and construct a semigroup which is isomorphic to the endomorphism monoid of such free trioid. Also, we give an abstract characteristic for the endomorphism monoid of a free trioid of rank 1 and prove that free trioids are determined by their endomorphism monoids. 相似文献
13.
G. Mashevitzky Boris M. Schein 《Proceedings of the American Mathematical Society》2003,131(6):1655-1660
We determine all isomorphisms between the endomorphism semigroups of free monoids or free semigroups and prove that automorphisms of the endomorphism semigroup of a free monoid or a free semigroup are inner or ``mirror inner". In particular, we answer a question of B. I. Plotkin.
14.
Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M . In this paper we give a construction G(M) for a graph with prescribed endomorphism monoid M . Using this construction we derive bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. For example we show that for every monoid M , | M |=m there is a graph G with End(G)? M and |E(G)|≤(1 + 0(1))m2. This is, up to a factor of 1/2, best possible since there are monoids requiring a graph with \begin{eqnarray*} && \frac{m^{2}}{2}(1 -0(1)) \end{eqnarray*} edges. We state bounds for the class of all monoids as well as for certain subclasses—groups, k‐cancellative monoids, commutative 3‐nilpotent monoids, rectangular groups and completely simple monoids. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 241–262, 2009 相似文献
15.
We prove that if two finite Tarski algebras have isomorphic endomorphism monoids then they are isomorphic. 相似文献
16.
Gábor Czédli 《Algebra Universalis》2017,77(3):251-269
A topological monoid is isomorphic to an endomorphism monoid of a countable structure if and only if it is separable and has a compatible complete ultrametric such that composition from the left is non-expansive. We also give a topological characterisation of those topological monoids that are isomorphic to endomorphism monoids of countable \({\omega}\)-categorical structures. Finally, we present analogous characterisations for polymorphism clones of countable structures and for polymorphism clones of countable \({\omega}\)-categorical structures. 相似文献
17.
It is proved that the fixed point submonoid and the periodic point submonoid of a trace monoid endomorphism are always finitely generated. If the dependence alphabet is a transitive forest, it is proved that the set of regular fixed points of the (Scott) continuous extension of an endomorphism to real traces is Ω-rational for every endomorphism if and only if the monoid is a free product of free commutative monoids. 相似文献
18.
In this article, the Cayley graphs of Brandt semigroups are investigated. The basic structures and properties of this kind of Cayley graphs are given, and a necessary and sufficient condition is given for the components of Cayley graphs of Brandt semigroups to be strongly regular. As an application, the generalized Petersen graph and k-partite graph, which cannot be obtained from the Cayley graphs of groups, can be constructed as a component of the Cayley graphs of Brandt semigroups. 相似文献
19.
Ulrich Knauer 《Semigroup Forum》1976,13(1):143-148
So far Baer monoids have been studied mainly under the viewpoint of lattice theory (see [1] and papers by Blyth, Foulis, Janowitz, Thorne cited there). Here we shall deal with some of the aspects considered for Baer rings in [8], [11], [12], among them the relations between Baer monoids and Baer endomorphism monoids. This question is also discussed for dual monoids.The research leading to this paper was started in cooperation with A. V. Mikhalev during a short visit at the Lomonossov University, Moscow, in 1974, sponsored by the DFG, Bonn-Bad Godesberg. 相似文献
20.
有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法. 相似文献