Satisfiability of equations in free groups is in PSPACE

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Satisfiability of equations in free groups is in PSPACE

Full text

Pdf (712 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 21 - 27

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Claudio Gutiérrez

Computer Science Group, Dept. Mathematics, Wesleyan University and Departamento de Ingeniería Matemática, Universidad de Chile, Chile

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 18, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335308 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	V. Diekert, Personal communication, 8 Oct. 1999.
	2	Valery Durnev, Studying Algorithmic Problems for Free Semi-groups and Groups, Proceedings of the 4th International Symposium on Logical Foundations of Computer Science, p.88-101, July 06-12, 1997
	3	Claudio Gutiérrez, Satisfiability of Word Equations with Constants is in Exponential Space, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.112, November 08-11, 1998
	4	Claudio Gutiérrez, Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.387-396, April 10-14, 2000
	5	Y.I. Kmelevskii, Equations in a free semigroup, Trudy Mat. Inst. Steklov 107(1971); English trans. Proc. Steklov Inst. Math. 107(1971).
	6	Y.I. Kmelevskii, Systems of equations in a free group I, Izv. Akad. Nauk. SSSR Ser. Mat. 35(1971), 1237-1268; English trans, in Math USSR Izv. 5(1971).
	7	Y.I. Kmelevskii, Systems of equations in a free group II, Izv. Akad. Nauk. SSSR Set. Mat. 36(1972), 110-179; English trans, in Math USSR Izv. 6(1972).
	8	Antoni Kościelski , Leszek Pacholski, Complexity of Makanin's algorithm, Journal of the ACM (JACM), v.43 n.4, p.670-684, July 1996 [doi>10.1145/234533.234543]
	9	Antoni Kościelski , Leszek Pacholski, Makanin's algorithm is not primitive recursive, Theoretical Computer Science, v.191 n.1-2, p.145-156, Jan. 30, 1998 [doi>10.1016/S0304-3975(96)00321-0 ]
	10	A.A. Lorents, Representation of solution sets of systems of equations with one unknown in free groups, Dokl. Akad. Nauk SSSR 178(1968), 290-292; English trans, in Soviet Math. Dokl. 9 (1968).
	11	Lothaire, M. Combinatorics on Words, Cambridge Mathematical Texts, reprinted 1998.
	12	R.C. Lyndon, Equations in free groups, Trans. Amer. Math. Soc. 96(1960), 445-457.
	13	G.S. Makanin, The problem of solvability of equations in a free semigroup, Mat. Sbornik 103, 147-236 (in Russian). English translation in Math. USSR Sbornik 32, 129-198.
	14	G.S. Makanin. Equations in a free group, Izvestiya NA SSSR 46(1982), 1199-1273; English translation in Math USSR Izvestiya, 21 (1983), 483-546.
	15	G.S. Makanin. Decidability of the universal and positive theories of a free group, Izvestiya NA SSSR 48(1984), 735-749; English translation in Math USSR Izvestiya, 25 (1985), 75-88.
	16	Wojciech Plandowski , Wojciech Rytter, Application of Lempel-Ziv Encodings to the Solution of Words Equations, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.731-742, July 13-17, 1998
	17	Wojciech Plandowski, Satisfiability of word equations with constants is in NEXPTIME, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.721-725, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301443]
	18	Wojciech Plandowski, Satisfiability of Word Equations with Constants is in PSPACE, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.495, October 17-18, 1999
	19	A.A. Razborov, On systems of equations in a free group, Izvestiya AN SSSR 48 (1984) 779-832 (in Russian). English translation in Math. USSR Izvestiya 25 (1985) 115- 162.

CITED BY 2

	Claudio Gutiérrez, Equations in free semigroups with involution and their relation to equations in free groups, Theoretical Computer Science, v.297 n.1-3, p.271-280, 17 March 2003
	Volker Diekert , Claudio Gutierrez , Christian Hagenah, The existential theory of equations with rational constraints in free groups is PSPACE-complete, Information and Computation, v.202 n.2, p.105-140, 1 November, 2005