@article{Lohrey:SIAM-JoC: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.},
    Author = {Lohrey, Markus},
    EPrint = {https://doi.org/10.1137/S0097539704445950},
    File = {WORD PROBLEMS AND MEMBERSHIP PROBLEMS ON COMPRESSED WORDS - clf\_compressed.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {5},
    Pages = {1210--1240},
    Title = {Word Problems and Membership Problems on Compressed Words},
    URL = {https://doi.org/10.1137/S0097539704445950},
    Volume = {35},
    Year = {2006},
    bdsk-url-1 = {https://doi.org/10.1137/S0097539704445950},
    date-added = {2023-08-08 16:57:37 +0200},
    date-modified = {2023-08-08 16:57:54 +0200},
    file-2 = {clf\_compressed.ps},
    doi = {10.1137/S0097539704445950}
}

@article{Lohrey:SIAM-JoC: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.}, Author = {Lohrey, Markus}, EPrint = {https://doi.org/10.1137/S0097539704445950}, File = {WORD PROBLEMS AND MEMBERSHIP PROBLEMS ON COMPRESSED WORDS - clf_compressed.pdf}, Journal = {SIAM Journal on Computing}, Number = {5}, Pages = {1210--1240}, Title = {Word Problems and Membership Problems on Compressed Words}, URL = {https://doi.org/10.1137/S0097539704445950}, Volume = {35}, Year = {2006}, bdsk-url-1 = {https://doi.org/10.1137/S0097539704445950}, date-added = {2023-08-08 16:57:37 +0200}, date-modified = {2023-08-08 16:57:54 +0200}, file-2 = {clf_compressed.ps}, doi = {10.1137/S0097539704445950} }