Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 7,446 papers for “Homomorphism”

A Homomorphism

William Goldbloom Bloch · 2008

Abstract The time has come to return to the first person singular voice. I’ve done my best, up to this chapter, to restrict myself to excavating, extending, enlarging, and explaining mathematical ideas which naturally arise from the story. But now, after scanning critical reviews and interpretations of coded meanings of the story, I find I have another reading to add to the existing constellation: a homomorphism between the structures of two different ideas.

Cited by 0

Homomorphism Extension

Angela Wuu · arXiv (Cornell University) · 2018

We define the Homomorphism Extension (HomExt) problem: given a group $G$, a subgroup $M \leq G$ and a homomorphism $φ: M \to H$, decide whether or not there exists a homomorphism $\widetildeφ: G\to H$ extending $φ$, i.e., $\widetildeφ|_M = φ$. This problem arose in the context of list-decoding homomorphism codes but is also of independent interest, both as a problem in computational group theory and as a new and natural problem in NP of unsettled complexity status. We consider the case $H=S_m$ (the symmetric group of degree $m$), i.e., $φ: G \to H$ is a $G$-action on a set of $m$ elements. We assume $G\le S_n$ is given as a permutation group by a list of generators. We characterize the equivalence classes of extensions in terms of a multidimensional oracle subset-sum problem. From this we infer that for bounded $G$ the HomExt problem can be solved in polynomial time. Our main result concerns the case $G=A_n$ (the alternating group of degree $n$) for variable $n$ under the assumption that the index of $M$ in $G$ is bounded by poly$(n)$. We solve this case in polynomial time for all $m < 2^{n-1}/\sqrt{n}$. This is the case with direct relevance to homomorphism codes (Babai, Black, and Wuu, arXiv 2018); it is used as a component of one of the main algorithms in that paper.

Cited by 0Open access

Homomorphism Preserving . . .

J. A. Bergstra, J. Heering · 1993

Although every computable data type has an initial algebra specification with hidden functions, it may happen that some of the homomorphic images of the data type are not models of the specification. The latter are reducts of algebras that would be models of the specification if all its functions were visible, whereas the homomorphic images of the data type are independent of the specification and need not be compatible with the hidden functions used in it. A hidden function specification that does not exclude any of the homomorphic images of its initial model from its model class will be called homomorphism preserving. It turns out that, unlike unrestricted initial algebra specification, homomorphism preserving initial algebra specification of computable data types requires both hidden sorts and hidden functions.

Cited by 0

When a lattice homomorphism is a Riesz homomorphism

Zafer Ercan, A. W. Wickstead · Mathematische Nachrichten · 2006

Abstract Let E and F be uniformly complete vector lattices with disjoint complete systems ( u i ) i ∈ I and ( v i ) i ∈ I of projection elements of E and F respectively. In this paper we prove that if T is a lattice homomorphism from E into F with T ( λu i ) = λv i for each λ ∈ ℝ and i ∈ I then T is linear. This generalizes the main results of [4] and [5]. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

Cited by 5

Maximal Homomorphism in Fundamental Theorem of Homomorphism Semiring

Riski Ryan Hardiansyah, Khurul Wardati, Muhamad Zaki Riyanto · Proceeding International Conference on Science and Engineering · 2017

Semiring is a generalization of ring. Some concepts in ring can be developed in semiring. The contructions of quotient semiring requires a specific ideal, namely Q-ideal. Different to the ring theory, the fundamental theorems of homomorphism on semiring needs a concept of maximal homomorphism, science the kernel of any maximal homomorphism is always Q-ideal.

Cited by 0Open access

Why Homomorphism Invocked

ATRAJIT SARKAR · OSF Preprints (OSF Preprints) · 2025

Why we invocked homomorphism like structure, why we invoke one one onto functions for making certain mathematical structures equivalent?

Cited by 0

Accumulation Without Homomorphism

Bünz, Benedikt, Mishra, Pratyush, Nguyen, Wilson et al. · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2025

Accumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is based on public-key assumptions. It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions. In this paper, we answer this question affirmatively by constructing an accumulation scheme from non-homomorphic vector commitments which can be realized from solely symmetric-key assumptions (e.g., Merkle trees). We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors. Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps. We show that such bounded-depth accumulation still suffices to construct proof-carrying data (a generalization of IVC). We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency.

Cited by 0Open access

Coercion as homomorphism

Alex Shafarenko · University of Hertfordshire Research Archive (University of Hertfordshire) · 2002

A type system with atomic subtyping and a special form of operator overloading, which we call offset-homomorphism is proposed. A set of operator overloadings is said to be offset-homo-morphic when for each pair of overloadings the coercion function realises a homomorphism of types and at the same time certain conditions on the operator type signature are satisfied. We demonstrate that offset-homomorphic overloading has sufficient power for supporting a comprehensive set of array operations in a declarative language. The problem of inferring the least types in our type system is proven to be equivalent to the shortest path problem for weighted, directed graphs with non-negative cycle weights, which has a computationally efficient solution.

Cited by 4Open access

HOMOMORPHISM ONTO Z

Aleksander Malnič, Norbert Seifter, Boris Zgrablić et al. · 1999

In an in nite digraph D, an edge e 0 is reachable from an edge e if there exists an alternating walk in D whose initial and terminal edges are e and e 0. Reachability is an equivalence relation and if D is 1-arc-transitive, then this relation is either universal or all of its equivalence classes induce isomorphic bipartite digraphs. In [1, Question 1.3], Cameron, Praeger and Wormald asked if there exist highly arctransitive digraphs (apart from directed cycles) for which the reachability relation is not universal and whichdonothaveahomomorphism onto the two-way in nite directed path (a Cayley digraph of Z with respect to one generator). Evans [2] gave an a rmative answer by constructing a locally in nite example. For each oddinteger n 3, a construction of a highly arc-transitive digraph without property Z satisfying the additional properties that its in- and out-degrees are equal to 2 and that the reachability equivalence classes induce alternating cycles of length 2n, is given. Furthermore, using the line digraph operator, digraphs having the above properties but with alternating cycles of length 4 are obtained.

Cited by 0

Graph Homomorphism Convolution

Hoang Nguyen, Hoang Nguyen, 前原 貴憲 et al. · Tokyo Tech Research Repository (Tokyo Institute of Technology) · 2021

In this paper, we study the graph classification problem from the graph homomorphism perspective. We consider the homomorphisms from F to G, where G is a graph of interest (e.g. molecules or social networks) and F belongs to some family of graphs (e.g. paths or non-isomorphic trees). We show that graph homomorphism numbers provide a natural invariant (isomorphism invariant and F-invariant) embedding maps which can be used for graph classification. Viewing the expressive power of a graph classifier by the F-indistinguishable concept, we prove the universality property of graph homomorphism vectors in approximating F-invariant functions. In practice, by choosing F whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.

Cited by 0

Homomorphism of Groups

J. H. M. Wedderburn · Annals of Mathematics · 1941

=, + G2 + * *= En Gp, I H = H1+ H2 + * = ZHP Gp Gq = Ox Hp Hq = O (p 5 iq) where the notation is not to be taken to mean that the sets are denumerable; the elements of a set Gp will be denoted by gp, gp, .. . . Then G is said to be homomorphic to H, G H, if (1) gpgq =gr D HpHq _ Hr. If gg = q,, then 1H1H, H.; but Hr H., = 0 if r $ s; hence r = s, that is, (1) implies (2) GpGq ? Gr. Again, if hahhb = h, let gagb = gd ; then HaHb 5 Hd . But HaHb > he < H,, therefore H, Hd 0 0 so that d = c and, since 9d < Gdi no matter what elements ga and gb are in Ga and Gb, we have hahb = hc D GaGb _ Gc that is, the relation of homomorphism is reflexive. Suppose now that the identity g1 is in G1 ; then gigp = gp = g1yg1 D GGp = Gp = GpG1 for all p, and therefore (3) H1Hp _ Hp I Hp)71 < Hp. If the identity of H lies in Ha, it follows similarly that HaHp = Hp = HpHa and in particular HaHi = H1 = HiHa But from (3) HaHi _ Ha and hence a = 1, so that the identity of H lies in H1. Since G is a group, any gl has an inverse, say gp, such that

Cited by 7