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 \(\mathcal M\), and we ask whether these two words represent the same monoid element of \(\mathcal M\). For compression we use straight-line programs. For several classes of 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 membership problem. The existence of such a language was open so far. Finally, we investigate the complexity of the compressed membership problem for various circuit complexity classes.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38, 150–164 (1989)
Barrington, D.A.M., Lu, C.-J., Miltersen, P.B., Skyum, S.: Searching constant width mazes captures the AC0 hierarchy. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 73–83. Springer, Heidelberg (1998)
Bauer, G., Otto, F.: Finite complete rewriting systems and the complexity of the word problem. Acta Inf. 21, 521–540 (1984)
Beaudry, M., Holzer, M., Niemann, G., Otto, F.: McNaughton families of languages. Theor. Comput. Sci. 290(3), 1581–1628 (2003)
Beaudry, M., McKenzie, P., Péladeau, P., Thérien, D.: Finite monoids: From word to circuit evaluation. SIAM J. Comput. 26(1), 138–152 (1997)
Book, R.V.: Homogeneous Thue systems and the Church–Rosser property. Discrete Math. 48, 137–145 (1984)
Book, R.V., Jantzen, M., Monien, B., Ó’Dúnlaing, C.P., Wrathall, C.: On the complexity of word problems in certain Thue systems. In: Gruska, J., Chytil, M.P. (eds.) MFCS 1981. LNCS, vol. 118, pp. 216–223. Springer, Heidelberg (1981)
Book, R.V., Otto, F.: String–Rewriting Systems. Springer, Heidelberg (1993)
Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 392–403. Springer, Heidelberg (1996) (extended abstract)
Holzer, M., Lange, K.-J.: On the complexities of linear LL(1) and LR(1) grammars. In: Ésik, Z. (ed.) FCT 1993. LNCS, vol. 710, pp. 299–308. Springer, Heidelberg (1993)
Krentel, M.W.: The complexity of optimization problems. J. Comput. Syst. Sci. 36(3), 490–509 (1988)
Lengauer, T., Wanke, E.: The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems. J. Comput. Syst. Sci. 44, 63–93 (1992)
Lewis II, P.M., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: Proc. Sixth Annual IEEE Symp. on Switching Circuit Theory and Logic Design, pp. 191–202 (1965)
Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. J. Assoc. Comput. Mach. 24(3), 522–526 (1977)
Lohrey, M.: Word problems and confluence problems for restricted semi-Thue systems. In: Bachmair, L. (ed.) RTA 2000. LNCS, vol. 1833, pp. 172–186. Springer, Heidelberg (2000)
Lohrey, M.: Word problems for 2-homogeneous monoids and symmetric logspace. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 500–511. Springer, Heidelberg (2001)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)
Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 460–470. Springer, Heidelberg (1994)
Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 262–272. Springer, Heidelberg (1999)
Robinson, D.: Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego (1993)
Rytter, W.: Compressed and fully compressed pattern matching in one and two dimensions. Proc. IEEE 88(11), 1769–1778 (2000)
Sipser, M.: Borel sets and circuit complexity. In: Proc. STOC 1983, pp. 61–69. ACM Press, New York (1983)
Stillwell, J.: The word problem and the isomorphism problem for groups. Bull. Am. Math. Soc., New Ser. 6(1), 33–56 (1982)
Sudborough, I.H.: On the tape complexity of deterministic context–free languages. J. Assoc. Comput. Mach. 25(3), 405–414 (1978)
Veith, H.: Succinct representation, leaf languages, and projection reductions. Inf. Control 142(2), 207–236 (1998)
Wagner, K.W.: The complexity of combinatorial problems with succinct input representation. Acta Inf. 23(3), 325–356 (1986)
Zhang, Y., Gupta, R.: Path matching in compressed control flow traces. In: Proc. DCC 2002, pp. 132–141. IEEE Computer Society Press, Los Alamitos (2002)
Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. on Inf. Theory 23(3), 337–343 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lohrey, M. (2004). Word Problems on Compressed Words. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_76
Download citation
DOI: https://doi.org/10.1007/978-3-540-27836-8_76
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22849-3
Online ISBN: 978-3-540-27836-8
eBook Packages: Springer Book Archive