Search

In this paper, we show that a two-sided quantale is coherent iff it is isomorphic to the quantale of ideals of a distributive two-sided *-semilattice. Thus quantale representations of distributive two-sided *-semilattices are obtained. We also show that the free two-sided quantale generated by a set exists. And then the category TQuant of two-sided quantales is an algebraic category. [ABSTRACT FROM AUTHOR]

With the applications of topological upgrading [1], some problems of upgrading mathematical structure to its power set have caused wide concerns. This paper studies the upgrading from group structure to its power set and gives the definition, examples and ways of construction of power groups, then shows the relationship between power groups and common groups and characterized power groups by common groups, and obtains a series of constructive conclusions and achieves many breakthroughs of upgrading a group to its power set. [ABSTRACT FROM AUTHOR]

Residue systems present a well-known way to reduce computation cost for symbolic computation. However most residue systems are implemented for integers or polynomials. This work combines two known results in a novel manner. Firstly, it lifts an integral residue system to fractions. Secondly, it generalises a single-residue system to a multiple-residue one. Combined, a rational multi-residue system emerges. Due to the independent manner of single ˵parts″ of the system, this work enables progress in parallel computing. We present a complete implementation of the arithmetic in the parallel extension e.g.. The parallelisation utilises algorithmic skeletons. A non-trivial example computation is also supplied. [ABSTRACT FROM AUTHOR]

We consider the deduction problem in the existential conjunctive fragment of first-order logic with atomic negation. This problem can be recast in terms of other database and artificial intelligence problems, namely query containment, clause entailment and boolean query answering. We refine an algorithm scheme that was proposed for query containment, which itself improves other known algorithms in databases. To study it experimentally, we build a random generator and analyze the influence of several parameters on the problem instance difficulty. Using this methodology, we experimentally compare several heuristics. [ABSTRACT FROM AUTHOR]

The universal composability (UC) for commitment is a very strong security notion. It guarantees that commitment schemes remain secure even if they are composed with arbitrary protocols and polynomially many copies of the schemes are run concurrently. Several UC commitment schemes in the common reference string (CRS) model have been proposed, but, they are either interactive commitment or bit-commitment (not string-commitment) schemes. We propose new non-interactive string-commitment schemes that achieve UC security in the CRS model assuming the difficulty of the decisional Diffie-Hellman problem or the decisional composite residuosity problem, but our schemes are not reusable. The main building blocks of our constructions are all-but-one trapdoor functions (ABO-TDFs) introduced by Peikert and Waters in STOC 2008 to construct secure public-key encryption schemes. Our main idea is to use the homomorphic properties of the function indices of the all-but-one trapdoor functions and to extend the functions to probabilistic ones by using re-randomization of ciphertexts. This is a new application of ABO-TDFs. [ABSTRACT FROM AUTHOR]

In this paper, we present a new method for sharing images between two parties exploiting homomorphic property of public key cryptosystem. With our method, we show that it is possible to multiply two encrypted images, to decrypt the resulted image and after to extract and reconstruct one of the two original images if the second original image is available. Indeed, extraction and reconstruction of original image at the receiving end is done with the help of carrier image. Experimental results and security analysis show the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

In this paper, The concepts of fuzzy relation mapping and inverse fuzzy relation mapping are firstly introduced and their properties are studied. Then, the notions of homomorphisms of information systems based on fuzzy relations are proposed, and it is proved that attribute reductions in the original system and image system are equivalent to each other under the condition of homomorphism. [ABSTRACT FROM AUTHOR]

This paper describes a new Chinese speech synthesis method apply in Chinese poetry teaching and learning, which focus on the prosody of syllables and words in Chinese poetry. As the word is a key semantic unit for Chinese poetry, we concentrate on Chinese word prosody and propose a speech synthesis method, which consider the appearance with the essence of human voice, use the homomorphism analysis over the time domain analysis to make the synthesized speech between syllables in a Chinese word sounds more natural. The prosody model of the method, however comply with the reading rules of Chinese poetry, make the user to learn Chinese poetry more convenient from the acoustic perception level. [ABSTRACT FROM AUTHOR]

For a fixed digraph H, the minimum cost homomorphism problem, MinHOM(H), asks whether an input digraph G, with given costs ci(u), u ϵ V(G), i ϵ V(H), and an integer k, admits a homomorphism to H of total cost not exceeding k. Minimum cost homomorphism problems encompass many well studied optimization problems such as list homomorphism problems, retraction and precolouring extension problems, chromatic partition optimization, and applied problems in repair analysis. For undirected graphs the complexity of the problem, as a function of the parameter H, is well understood; for digraphs, the situation appears to be more complex, and only partial results are known. We focus on the minimum cost homomorphism problem for reflexive digraphs H. It is known that MinHOM(H) is polynomial if H has a Min-Max ordering. We prove that for any other reflexive digraph H, the problem MinHOM(H) is NP-complete. (This was earlier conjectured by Gutin and Kim.) Apart from undirected graphs, this is the first general class of digraphs for which such a dichotomy has been proved. Our proof involves a forbidden induced subgraph characterization of reflexive digraphs with a Min-Max ordering, and implies a polynomial test for the existence of a Min-Max ordering in a reflexive digraph H. [ABSTRACT FROM AUTHOR]

We first consider a variant of the Schmidt-Samoa–Takagi encryption scheme without losing additively homomorphic properties. We show that this variant is secure in the sense of IND-CPA under the decisional composite residuosity assumption, and of OW-CPA under the assumption on the hardness of factoring n = p2q. Second, we introduce new cryptographic properties ˵affine″ and ˵pre-image restriction″, which are closely related to homomorphism. Intuitively, ˵affine″ is a tuple of functions which have a special homomorphic property, and ˵pre-image restriction″ is a function which can restrict the receiver to having information on the encrypted message. Then, we propose an encryption scheme with primitive power roots of unity in ]> . We show that our scheme has the above cryptographic properties. [ABSTRACT FROM AUTHOR]