Word Problems and Membership Problems on Compressed Words

Markus Lohrey

SIAM Journal on Computing · 2006 · 65 citations · 45 references

Concepts

Abstract

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. Key words. grammar-based compression, word problems for monoids, context-free languages, complexity AMS subject classifications. 20F10, 68Q17, 68Q42

References

45