Zobrazeno 1 - 10
of 18
pro vyhledávání: '"Alexandr Kazda"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 18, Issue 3 (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. We are promised that the input satisfies exactly one
Externí odkaz:
https://doaj.org/article/867c0f1f2dbf434fbcb71fd031d83c97
Autor:
Alexandr Kazda
Publikováno v:
Logical Methods in Computer Science, Vol Volume 14, Issue 2 (2018)
We show that if $\mathbb A$ is a core relational structure such that CSP($\mathbb A$) can be solved by a linear Datalog program, and $\mathbb A$ is $n$-permutable for some $n$, then CSP($\mathbb A$) can be solved by a symmetric Datalog program (and t
Externí odkaz:
https://doaj.org/article/38fd184f4ddf43daaf27e8378bae7a3b
Autor:
Matthew Valeriote, Alexandr Kazda
Publikováno v:
The Journal of Symbolic Logic. 85:539-562
In this paper we investigate the computational complexity of deciding if a given finite algebraic structure satisfies a fixed (strong) Maltsev condition $\Sigma$. Our goal in this paper is to show that $\Sigma$-testing can be accomplished in polynomi
Publikováno v:
Canadian Mathematical Bulletin
Canadian mathematical bulletin, 2020, Vol.63(3), pp.577-591 [Peer Reviewed Journal]
Canadian mathematical bulletin, 2020, Vol.63(3), pp.577-591 [Peer Reviewed Journal]
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation $m$ that satisfies the minority equations $m(y,x,x)\approx m(x,y,x)\approx m(x,x,y)\approx y$. We show that a common po
Autor:
Alexandr Kazda, Dmitriy Zhuk
We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1516162b8d4533e6fb918e2466be8a22
Autor:
Libor Barto, Alexandr Kazda
Publikováno v:
International Journal of Algebra and Computation. 26:1033-1060
We characterize absorption in finite idempotent algebras by means of Jónsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of it
Publikováno v:
Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science ISBN: 9783319747712
We prove that every congruence distributive variety has directed Jonsson terms, and every congruence modular variety has directed Gumm terms. The directed terms we construct witness every case of absorption witnessed by the original Jonsson or Gumm t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c7b68edf33b38e611f76a6bd75014081
https://doi.org/10.1007/978-3-319-74772-9_7
https://doi.org/10.1007/978-3-319-74772-9_7
Autor:
Alexandr Kazda, Mark Kambites
Publikováno v:
International Journal of Algebra and Computation. 24:893-907
We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute norma
The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::643a1a7b551917b235a8cc47c9447362
http://arxiv.org/abs/1602.03124
http://arxiv.org/abs/1602.03124
Autor:
Alexandr Kazda
Publikováno v:
European Journal of Combinatorics. 32(3):390-397
We prove that when a digraph $G$ has a Maltsev polymorphism, then $G$ also has a majority polymorphism. We consider the consequences of this result for the structure of Maltsev graphs and the complexity of the Constraint Satisfaction Problem.
Co
Co