tag:blogger.com,1999:blog-3722233.post1956215526531749410..comments2024-06-17T03:44:26.901-05:00Comments on Computational Complexity: Counting Descriptions- a ``new'' complexity classLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-72141100702214246072013-03-31T07:54:21.012-05:002013-03-31T07:54:21.012-05:00Look at "Parikh automata".Look at "Parikh automata".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16091818725717920192013-03-30T06:13:43.360-05:002013-03-30T06:13:43.360-05:00The concept of semilinearity is very relevant here...The concept of semilinearity is very relevant here -- so all MCFGs/LCFRSs are all semilinear too (permutation equivalent to a regular language.)<br />You might also look at the use of string kernels to generalise beyond n_a(w) to n_{abc}(w) -- i.e. look st linear constraints on continuous or discontinuous substrings.<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30071524794680425672013-03-28T10:47:40.595-05:002013-03-28T10:47:40.595-05:00sounds somewhat similar to timed automata. maybe s...sounds somewhat similar to <a href="http://en.wikipedia.org/wiki/Timed_automaton" rel="nofollow">timed automata</a>. maybe some natural bridge thms possible?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41518128819308570932013-03-28T09:31:42.799-05:002013-03-28T09:31:42.799-05:00A trivial remark after item 2.(2): Your languages ...A trivial remark after item 2.(2): Your languages are closed under permutation. The class CD may then be compared to other classes closed under permutation. I am not at all a specialist of these things but I suspect such classes have been studied before!Anonymousnoreply@blogger.com