Back to Search
Start Over
WORD PROBLEMS AND MEMBERSHIP PROBLEMS ON COMPRESSED WORDS.
- Source :
-
SIAM Journal on Computing . 2006, Vol. 35 Issue 5, p1210-1240. 31p. 1 Illustration, 2 Diagrams. - Publication Year :
- 2006
-
Abstract
- We consider a compressed form of the word problem for finitely presented monoids, where the input consists of two compressed representations of words over the generators of a monoid M, and we ask whether these two words represent the same monoid element of M. Words are compressed using straight-line programs, i.e., context-free grammars that generate exactly one word. For several classes of finitely presented monoids we obtain completeness results for complexity classes in the range from P to EXPSPACE. As a by-product of our results on compressed word problems we obtain a fixed deterministic context-free language with a PSPACE-complete compressed membership problem. The existence of such a language was open so far. Finally, we will investigate the complexity of the compressed membership problem for various circuit complexity classes. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 35
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 22745443
- Full Text :
- https://doi.org/10.1137/S0097539704445950