Search results for "Isomorphism"

Padding and the expressive power of existential second-order logics

1998

Padding techniques are well-known from Computational Complexity Theory. Here, an analogous concept is considered in the context of existential second-order logics. Informally, a graph H is a padded version of a graph G, if H consists of an isomorphic copy of G and some isolated vertices. A set A of graphs is called weakly expressible by a formula ϕ in the presence of padding, if ϕ is able to distinguish between (sufficiently) padded versions of graphs from A and padded versions of graphs that are not in A.

Varieties and Covarieties of Languages (Extended Abstract)

2013

AbstractBecause of the isomorphism (X×A)→X≅X→(A→X), the transition structure of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. This algebra-coalgebra duality goes back to Arbib and Manes, who formulated it as a duality between reachability and observability, and is ultimately based on Kalmanʼs duality in systems theory between controllability and observability. Recently, it was used to give a new proof of Brzozowskiʼs minimization algorithm for deterministic automata. Here we will use the algebra-coalgebra duality of automata as a common perspective for the study of both varieties and covarieties, which are …

Homomorphisms and composition operators on algebras of analytic functions of bounded type

2005

Abstract Let U and V be convex and balanced open subsets of the Banach spaces X and Y, respectively. In this paper we study the following question: given two Frechet algebras of holomorphic functions of bounded type on U and V, respectively, that are algebra isomorphic, can we deduce that X and Y (or X * and Y * ) are isomorphic? We prove that if X * or Y * has the approximation property and H wu ( U ) and H wu ( V ) are topologically algebra isomorphic, then X * and Y * are isomorphic (the converse being true when U and V are the whole space). We get analogous results for H b ( U ) and H b ( V ) , giving conditions under which an algebra isomorphism between H b ( X ) and H b ( Y ) is equiv…

On the structure of positive homomorphisms on algebras of real-valued continuous functions

2004

In this paper we study the structure of positive homomorphisms on real function algebras. We prove that every positive homomorphism is completely characterized by a family of sets and when the algebra is inverse-closed, by an ultrafilter of zero-sets of functions of the algebra. We show that the known sufficient conditions for every homomorphism of a real function algebra to be countably evaluating or a point evaluation are not necessary. Our results enable us to characterize the countably evaluating algebras as well as the Lindelof spaces as the spaces in which for every algebra, each countably evaluating homomorphism is a point evaluation.

Periodicity vectors for labelled trees

2003

AbstractThe concept of a periodicity vector is introduced in the context of labelled trees, and some new periodicity theorems are obtained. These results constitute generalizations of the classical periodicity theorem of Fine and Wilf for words. The concept of a tree congruence is also generalized and the isomorphism between the lattice of tree congruences and the lattice of unlabelled trees (prefix codes) is established.

A Polynomial Quantum Query Lower Bound for the Set Equality Problem

2004

The set equality problem is to tell whether two sets A and B are equal or disjoint under the promise that one of these is the case. This problem is related to the Graph Isomorphism problem. It was an open problem to find any ω(1) query lower bound when sets A and B are given by quantum oracles. We will show that any error-bounded quantum query algorithm that solves the set equality problem must evaluate oracles \(\Omega(\sqrt[5]{\frac{n}{\ln n}})\) times, where n=|A|=|B|.

A theorem of insertion and extension of functions for normal spaces

1993

Symmetry-assisted adversaries for quantum state generation

2011

We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the $backslash$sc Graph Isomorphism problem. We show that for the related problem of $backslash$sc Index Erasure our method leads to a lower bound of $backslash Omega(backslash sqrt N)$ which matches an upper bound obtained via reduction to quantum search on $N$ elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is …

The cup product of Hilbert schemes for K3 surfaces

2003

To any graded Frobenius algebra A we associate a sequence of graded Frobenius algebras A [n] so that there is canonical isomorphism of rings (H *(X;ℚ)[2]) [n] ≅H *(X [n] ;ℚ)[2n] for the Hilbert scheme X [n] of generalised n-tuples of any smooth projective surface X with numerically trivial canonical bundle.

About Graph Mappings

2019

Summary In this articles adjacency-preserving mappings from a graph to another are formalized in the Mizar system [7], [2]. The generality of the approach seems to be largely unpreceeded in the literature to the best of the author’s knowledge. However, the most important property defined in the article is that of two graphs being isomorphic, which has been extensively studied. Another graph decorator is introduced as well.