Abstract
The main result of the paper is the reduction of the problem of satisfiability of equations in free groups to the satisfiability of equations in free semigroups with anti-involution (SGA), by a non-deterministic polynomial time transformation.
A free SGA is essentially the set of words over a given alphabet plus an operator which reverses words. We study equations in free SGA, generalizing several results known for equations in free semigroups, among them that the exponent of periodicity of a minimal solution of an equation E in free SGA is bounded by \(2^{{\cal O}(\vert E\vert)}\).
This is a preview of subscription content, log in via an institution to check access.
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
Diekert, V.: Makanin’s Algorithm for Solving Word Equations with Regular Constraints. In: Lothaire, M. (ed.) Algebraic Combinatorics on Words. Report Nr. 1998/02, Fakultät Informatik, Universität Stuttgart (in forthcoming)
Diekert, V.: Personal communication (October 8 1999)
Gutiérrez, C.: Satisfiability of Word Equations with Constants is in Exponential Space. In: Proc. FOCS (1998)
Gutiérrez, C.: Solving Equations in Strings: On Makanin’s Algorithm. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 358–373. Springer, Heidelberg (1998)
Hmelevskii, J.I.: Equations in a free semigroup. Trudy Mat. Inst. Steklov 107 (1971); English translation: Proc. Steklov Inst. Math. 107 (1971)
Jaffar, J.: Minimal and Complete Word Unification. Journal of the ACM 37(1), 47–85 (1990)
Kościelski, A., Pacholski, L.: Complexity of Makanin’s algorithm. J. Assoc. Comput. Mach. 43, 670–684 (1996)
Kościelski, A., Pacholski, L.: Makanin’s algorithm is not primitive recursive. Theoretical Computer Science 191, 145–156 (1998)
Lothaire, M.: Combinatorics on Words. Cambridge Mathematical Texts (1998) (reprinted)
Makanin, G.S.: The problem of satisfiability of equations in a free semigroup. Mat. Sbornik 103, 147–236 (in Russian); English translation in Math. USSR Sbornik 32, 129-198
Makanin, G.S.: Equations in a free group. Izvestiya NA SSSR 46, 1199–1273 (1982) (in Russian); English translation in Math USSR Izvestiya 21(3) (1983)
Rytter, W., Plandowski, W.: Applications of Lempel-Ziv encodings to the solution of word equations. In: Proceedings of the 25th. ICALP (1998)
Plandowski, W.: Satisfiability of word equations with constants is in NEXPTIME. In: Proc. STOC 1999 (1999)
Plandowski, W., Satisfiability of word equations with constants is in PSPACE. In: Proc. FOCS 1999 (1999)
Razborov, A.A.: On systems of equations in a free group. Izvestiya AN SSSR 48, 779–832 (1984) (in Russian); English translation in Math. USSR Izvestiya 25, 115-162 (1985)
Schulz, K.: Word Unification and Transformation of Generalized Equations. Journal of Automated Reasoning 11, 149–184 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gutiérrez, C. (2000). Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups. In: Gonnet, G.H., Viola, A. (eds) LATIN 2000: Theoretical Informatics. LATIN 2000. Lecture Notes in Computer Science, vol 1776. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10719839_38
Download citation
DOI: https://doi.org/10.1007/10719839_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67306-4
Online ISBN: 978-3-540-46415-0
eBook Packages: Springer Book Archive