Abstract
We study the computational complexity of determining whether a systems of equations over a fixed finite monoid has a solution. In [6], it was shown that in the restricted case of groups the problem is tractable if the group is Abelian and NP-complete otherwise. We prove that in the case of an arbitrary finite monoid, the problem is in P if the monoid divides the direct product of an Abelian group and a commutative idempotent monoid, and is NP-complete otherwise. In the restricted case where only constants appear on the right-hand side, we show that the problem is in P if the monoid is in the class R 1 ∀ L 1, and is NP-complete otherwise.
Furthermore interesting connections to the well known CONSTARINT SATISFIABILITY PROBLEM are uncovered and exploited.
Research supported by NSERC, FCAR and the Von Humboldt Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. A. M. Barrington and D. Thérien. Finite monoids and the fine structure of NC 1. Journal of the ACM, 35(4):941–952, Oct. 1988.
D. M. Barrington, P. McKenzie, C. Moore, P. Tesson, and D. Thérien. Equation satisfiability and program satisfiability for finite monoids. In MFCS’00, pages 172–181, 2000.
V. Dalmau. Computational Complexity of Problems over Generalized Formula. PhD thesis, Universita Politécnica de Catalunya, 2000.
S. Eilenberg. Automata, Languages and Machines, volume B. Academic Press, 1976.
T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing, 28(1):57–104, 1999.
M. Goldmann and A. Russell. The complexity of solving equations over finite groups. In Proc. 14th Conf. on Computational Complexity, pages 80–86, 1999.
Hertrampf, Lautemann, Schwentick, Vollmer, and Wagner. On the power of polynomial time bit-reductions. In Conf. on Structure in Complexity Theory, 1993.
P. Jeavons, D. Cohen, and M. Gyssens. Closure properties of constraints. J. ACM, 44(4):527–548, 1997.
O. Klima. Private communication, 2001.
J. Pearson and P. Jeavons. A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, University of London, 1997. Available at http://www.dcs.rhbnc.ac.uk/research/.
J.-E. Pin. Varieties of formal languages. North Oxford Academic Publishers Ltd, London, 1986.
J.-F. Raymond, P. Tesson, and D. Thérien. An algebraic approach to communication complexity. Lecture Notes in Computer Science, 1443:29–40, 1998.
T. J. Schaefer. The complexity of satisfiability problems. In Proc. 10 th ACM STOC, pages 216–226, 1978.
M. P. Schützenberger. Sur le produit de concaténation non ambigu. Semigroup Forum, 13:47–75, 1976.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Moore, C., Tesson, P., Thérien, D. (2001). Satisfiability of Systems of Equations over Finite Monoids. In: Sgall, J., Pultr, A., Kolman, P. (eds) Mathematical Foundations of Computer Science 2001. MFCS 2001. Lecture Notes in Computer Science, vol 2136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44683-4_47
Download citation
DOI: https://doi.org/10.1007/3-540-44683-4_47
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42496-3
Online ISBN: 978-3-540-44683-5
eBook Packages: Springer Book Archive