Thumbnail
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

   Open content in new tab
Source: ACM Digital Library