Zobrazeno 1 - 10
of 60
pro vyhledávání: '"Matthew Valeriote"'
Autor:
Emil Kiss, Matthew Valeriote
Publikováno v:
Logical Methods in Computer Science, Vol Volume 3, Issue 2 (2007)
Constraint languages that arise from finite algebras have recently been the object of study, especially in connection with the Dichotomy Conjecture of Feder and Vardi. An important class of algebras are those that generate congruence distributive var
Externí odkaz:
https://doaj.org/article/eb4e1915556b43c0a4235e1ea1510093
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
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d7606c532aa68a41f52496955aef8df1
https://doi.org/10.1017/jsl.2019.73
https://doi.org/10.1017/jsl.2019.73
Publikováno v:
SIAM Journal on Computing. 48:1022-1045
For each finite relational structure $A$, let $CSP(A)$ denote the CSP instances whose constraint relations are taken from $A$. The resulting family of problems $CSP(A)$ has been considered heavily in a variety of computational contexts. In this artic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::02b7d06552e03af4e4e4267bc58e744c
https://doi.org/10.1137/18m121085x
https://doi.org/10.1137/18m121085x
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
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a8eac792f78d971c1b04f94d849f3601
We consider the following practical question: given a finite algebra [Formula: see text] in a finite language, can we efficiently decide whether the variety generated by [Formula: see text] has a difference term? We answer this question (positively)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d16e999393625b1e51cdf71ba21c344a
Publikováno v:
Order. 36:65-76
This paper investigates the computational complexity of deciding if a given finite algebra is an expansion of a semilattice. In general this problem is known to be EXP-TIME complete, and we show that even for idempotent algebras, this problem remains
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::74b9b48dfb5e9273b983161129a7efde
https://doi.org/10.1007/s11083-018-9455-6
https://doi.org/10.1007/s11083-018-9455-6
Publikováno v:
Algebra universalis. 76:293-300
We show that the Maltsev product of two idempotent varieties of algebras that have n-ary and m-ary near unanimity terms, respectively, will have a near unanimity term of arity n + m − 1 We also show that in general no lower arity near unanimity ter
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9a1344d28d8f871fc2b728fed7f2cfd0
https://doi.org/10.1007/s00012-016-0393-0
https://doi.org/10.1007/s00012-016-0393-0
Autor:
Matthew Valeriote, Ross Willard
Publikováno v:
Bulletin of the London Mathematical Society. 46:870-880
One of the important classes of varieties identified in tame congruence theory is the class of varieties which are n-permutable for some n .I n this paper, we prove two results: (1) for every n> 1, there is a polynomial-time algorithm that, given a f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d679dc8d2a99fd15787e5c2a2fdb4f96
https://doi.org/10.1112/blms/bdu044
https://doi.org/10.1112/blms/bdu044
Autor:
Matthew Valeriote
Publikováno v:
Bull. Symbolic Logic 19, iss. 1 (2013), 127-134
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ac8a73fa107b6e868949fcfcc2d9d7b1
https://doi.org/10.2178/bsl.1901080
https://doi.org/10.2178/bsl.1901080
Publikováno v:
FOCS
For a finite relational structure A, let CSP(A) denote the CSP instances whose constraint relations are taken from A. The resulting family of problems CSP(A) has been considered heavily in a variety of computational contexts. In this article, we cons
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c4d0a4e46d1718f2d61f372390f8db79
https://doi.org/10.1109/focs.2016.63
https://doi.org/10.1109/focs.2016.63