作者suhorng ( )
站内Prob_Solve
标题[问题] 单纸带图灵机与 o(n log n)
时间Tue Nov 8 23:22:39 2011
课本上有一题是说：任何可以被单纸带图灵机在 o(n log n) 时间内 recognize
的语言皆为 regular，但是没有任何提示，实在想不到该如何下手。
请问能不能提示一下？
在网路上搜寻也没有找到资料，除了找到别人的 homework ...:
http://www.cs.au.dk/~arnsfelt/CT08/homework/homework1.pdf
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.115.144.99
※ 编辑: suhorng 来自: 59.115.144.99 (11/08 23:28)
1F：推 hcsoso:This theorem is proved by Kobayashi, which is not an 11/08 23:56
2F：→ hcsoso:easy result. This may be helpful to you: 11/08 23:56
4F：推 Favonia:某本书收集了很多很难的问题... xD 11/09 08:32
5F：→ suhorng:感谢一楼:) 用至这个当关键字搜寻到神奇的东西: 11/09 21:36
7F：→ suhorng: 2010final_sol.pdf 11/09 21:36
8F：→ suhorng:里面 Problem 5 是这题并有解答... 11/09 21:37
9F：推 Hseuler:老师出这题当期末考的时候全班没人做出来 11/16 22:05