SIAM Journal on Computing · 2006 · 65 citations · 45 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationCircuit ComplexityComplexity TheoryComputational ComplexityComputational Complexity ClassesContext-free LanguagesStructural ComplexityCompletenessCompleteness ResultsComplexity ClassesContext-free GrammarsDeterministic Context-free LanguagesMembership ProblemMonoid TheoryWord Complexity
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
45
Larry J. Stockmeyer · Theoretical Computer Science · 1976 · 1.3K citations
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer · Journal of the ACM · 1981 · 1.2K citations · Full text