Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Equation Satisfiability and Program Satisfiability for Finite Monoids
| |
|
Equation Satisfiability and Program Satisfiability for Finite Monoids
David Mix Barrington6, Pierre McKenzie7, Cris Moore8, Pascal Tesson9 and Denis Thérien9
| (6) |
Dept. of Computer Science, University of Massachussets, USA |
| (7) |
Dept. d’Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Canada |
| (8) |
Dept. of Computer Science, University of New Mexico, USA |
| (9) |
School of Computer Science, McGill University, USA |
Abstract
We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed
finite monoid. We partially answer an open problem of [4] by exhibiting quasi-polynomial time algorithms for a subclass of solvable non-nilpotent groups and relate this question
to a natural circuit complexity conjecture. In the special case when M is aperiodic, we show that PROGRAM SATISFIABILITY is in P when the monoid belongs to the variety DA and is NP-complete otherwise. In contrast, we give an example of an aperiodic outside DA for which EQUATION SATISFIABILITY is computable in polynomial time and discuss the relative complexity of the two problems.
We also study the closure properties of classes for which these problems belong to P and the extent to which these fail to
form algebraic varieties.
P. McKenzie, P. Tesson and D. Thérien are supported by NSERC and FCAR grants. A part of the work was completed during workshops
held respectively by DIMACS-DIMATIA (June 99) and McGill University (February 00). The authors wish to thank the organizers
of both events.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|