Back to Search
Start Over
Existential and Positive Theories of Equations in Graph Products.
- Source :
-
Theory of Computing Systems . Jan/Feb2004, Vol. 37 Issue 1, p133-156. 24p. - Publication Year :
- 2004
-
Abstract
- We prove that the existential theory of equations with normalized rational constraints in a fixed graph product of finite monoids, free monoids, and free groups is PSPACE-complete. Under certain restrictions this result also holds if the graph product is part of the input. As the second main result we prove that the positive theory of equations with recognizable constraints in graph products of finite and free groups is decidable. [ABSTRACT FROM AUTHOR]
- Subjects :
- *EQUATIONS
*MONOIDS
*GRAPHIC methods
*MATHEMATICAL variables
Subjects
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 37
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 11627371
- Full Text :
- https://doi.org/10.1007/s00224-003-1110-x