Other formats:
BibTeX
LaTeX
RIS
@article{727750,
author = {Klíma, Ondřej and Therien, Denis and Tesson, Pascal},
article_location = {New York},
article_number = {3},
keywords = {finite semigroups; dichotomies in complexity theory; systems of equations},
language = {eng},
issn = {1432-4350},
journal = {Theory of Computing Systems},
title = {Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups},
url = {http://www.springerlink.com/content/f60241072760q086/},
volume = {40},
year = {2007}
}
TY - JOUR
ID - 727750
AU - Klíma, Ondřej - Therien, Denis - Tesson, Pascal
PY - 2007
TI - Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups
JF - Theory of Computing Systems
VL - 40
IS - 3
SP - 263-297
EP - 263-297
PB - Springer
SN - 14324350
KW - finite semigroups
KW - dichotomies in complexity theory
KW - systems of equations
UR - http://www.springerlink.com/content/f60241072760q086/
N2 - We consider the problem of testing whether a given system of equation over a fixed finite semigroup S has a solution. For the case where S is a monoid, we prove that the problem is computable in polynomial time when S is commutative and is the union of its subgoups but is NP-complete otherwise. When S is a monoid ar regular semigroup, we obtain similar dichotomies for the restricted version of the problem where no variable occurs on the right-hand side of each equation. We stress conections between these problems and constraint satisfaction problems. In particular, for any finite domain D and any finite set of relations T over D, we construct a finite semigroup S(T) such that CSP(T) is polynomial-time equivalent to the equation satisfiability problem over S(T).
ER -
KLÍMA, Ondřej, Denis THERIEN and Pascal TESSON. Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups. \textit{Theory of Computing Systems}. New York: Springer, 2007, vol.~40, No~3, p.~263-297. ISSN~1432-4350.
|
