Results 1 to 10 of about 34 (34)
CC-circuits and the expressive power of nilpotent algebras [PDF]
Logical Methods in Computer Science, 2022 We show that CC-circuits of bounded depth have the same expressive power as circuits over finite nilpotent algebras from congruence modular varieties. We use this result to phrase and discuss a new algebraic version of Barrington, Straubing and Th\'erien'
Michael Kompatscher
doaj +1 more source
Universal Algebraic Methods for Constraint Satisfaction Problems [PDF]
Logical Methods in Computer Science, 2022 After substantial progress over the last 15 years, the "algebraic CSP-dichotomy conjecture" reduces to the following: every local constraint satisfaction problem (CSP) associated with a finite idempotent algebra is tractable if and only if the algebra ...
Clifford Bergman, William DeMeo
doaj +1 more source
Small Promise CSPs that reduce to large CSPs [PDF]
Logical Methods in Computer Science, 2022 For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A,B) asks whether a given input structure maps homomorphically to A or does not even map to B.
Alexandr Kazda, Peter Mayr, Dmitriy Zhuk
doaj +1 more source
Tractable Combinations of Temporal CSPs [PDF]
Logical Methods in Computer Science, 2022 The constraint satisfaction problem (CSP) of a first-order theory T is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in some model of T.
Manuel Bodirsky +2 more
doaj +1 more source
The Complexity of Combinations of Qualitative Constraint Satisfaction Problems [PDF]
Logical Methods in Computer Science, 2020 The CSP of a first-order theory $T$ is the problem of deciding for a given finite set $S$ of atomic formulas whether $T \cup S$ is satisfiable. Let $T_1$ and $T_2$ be two theories with countably infinite models and disjoint signatures.
Manuel Bodirsky, Johannes Greiner
doaj +1 more source
Pseudo-free families and cryptographic primitives
Journal of Mathematical Cryptology, 2022 In this article, we study the connections between pseudo-free families of computational Ω\Omega -algebras (in appropriate varieties of Ω\Omega -algebras for suitable finite sets Ω\Omega of finitary operation symbols) and certain standard cryptographic ...
Anokhin Mikhail
doaj +1 more source
The Subpower Membership Problem for Finite Algebras with Cube Terms [PDF]
Logical Methods in Computer Science, 2019 The subalgebra membership problem is the problem of deciding if a given element belongs to an algebra given by a set of generators. This is one of the best established computational problems in algebra.
Andrei Bulatov +2 more
doaj +1 more source
Pseudo-free families of computational universal algebras
Journal of Mathematical Cryptology, 2020 Let Ω be a finite set of finitary operation symbols. We initiate the study of (weakly) pseudo-free families of computational Ω-algebras in arbitrary varieties of Ω-algebras.
Anokhin Mikhail
doaj +1 more source
Algebraic generalization of Diffie–Hellman key exchange
Journal of Mathematical Cryptology, 2018 The Diffie–Hellman key exchange scheme is one of the earliest and most widely used public-key primitives. Its underlying algebraic structure is a cyclic group and its security is based on the discrete logarithm problem (DLP).
Partala Juha
doaj +1 more source
CCS with Hennessy's merge has no finite equational axiomatization [PDF]
, 2004 This paper confirms a conjecture of Bergstra and Klop¿s from 1984 by establishing that the process algebra obtained by adding an auxiliary operator proposed by Hennessy in 1981 to the recursion free fragment of Milner¿s Calculus of Communicationg Systems
Fokkink, W.J. (Wan) +7 more
core