tag:blogger.com,1999:blog-3722233.post6052109793999482549..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: A Silly String TheoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-92201871499377012562015-11-26T22:10:55.635-06:002015-11-26T22:10:55.635-06:00this is like euclid's gcd algorithmthis is like euclid's gcd algorithmAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91350039594877236252015-11-20T09:56:59.294-06:002015-11-20T09:56:59.294-06:00And here I was thinking I'd beat Jeffrey Shall...And here I was thinking I'd beat Jeffrey Shallit to pointing out that the result is in his book.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82447445329528675422015-11-19T17:55:49.853-06:002015-11-19T17:55:49.853-06:00Yeah, as anonymous is saying, you're basically...Yeah, as anonymous is saying, you're basically reproving a classic theorem from combinatorics on words known as the Lyndon-Schutzenberger theorem. Once you know this basic result, the proof follows almost immediately. See my book, "A Second Course in Formal Languages and Automata Theory", Theorem 2.3.3.Jeffrey Shallithttps://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73005079390560014002015-11-19T11:05:10.094-06:002015-11-19T11:05:10.094-06:00Lyndon's theorem: If xy = yx then x and y are ...Lyndon's theorem: If xy = yx then x and y are both powers of the same string.<br /><br />If y = s^i = t^k then there is a u such that s = u^m and t = u^n.<br />Anonymousnoreply@blogger.com