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.
|