tag:blogger.com,1999:blog-3722233.post4478424031861564777..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: Sizes of DFAs, NFAs, DPDAs, UCFG, CFGs, CSLs.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-28537051954978687932015-05-05T15:40:55.679-05:002015-05-05T15:40:55.679-05:00Nice post! We also studied the Turing degrees of n...Nice post! We also studied the Turing degrees of non-recursive trade-offs between different types of automata a while ago. There we gave another proof of Item 7. See Theorem 7 in the following paper: <br /><br />Hermann Gruber, Markus Holzer, and Martin Kutrib. On Measuring Non-Recursive Trade-Offs. In: Jürgen Dassow, Giovanni Pighizzini, and Bianca Truthe, editors, 11th Workshop on Descriptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany, volume 3 of Electronic Proceedings in Theoretical Computer Science, pages 141-150, July 2009. Hermann Gruberhttp://hermann-gruber.com/noreply@blogger.com