Complexity of Makanin's algorithmComplexity of Makanin's algorithm

Access Restriction
Subscribed

 Author Kocielski, Antoni ♦ Pacholski, Leszek Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1996 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Diophantine equations ♦ Periodicity ♦ Semantic unification ♦ Semi-groups ♦ Word equations Abstract The exponent of periodicity is an important factor in estimates of complexity of word-unification algorithms. We prove that the exponent of periodicity of a minimal solution of a word equation is of order 21.07d, where $\textit{d}$ is the length of the equation. We also give a lower bound 20.29d so our upper bound is almost optimal and exponentially better than the original bound (6d)22d4+ 2. Consequently, our result implies an exponential improvement of known upper bounds on complexity of word-unification algorithms. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1996-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 43 Issue Number 4 Page Count 15 Starting Page 670 Ending Page 684

Open content in new tab

Source: ACM Digital Library