tag:blogger.com,1999:blog-5275657281509261156.post9136626149130216816..comments2024-03-28T04:04:55.806-07:00Comments on Faculty of Language: The Merge Conspiracy [Part 2]Norberthttp://www.blogger.com/profile/15701059232144474269noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-5275657281509261156.post-53644271344848272882013-10-12T00:41:07.203-07:002013-10-12T00:41:07.203-07:00As for the relevance to type-theory, that's no...As for the relevance to type-theory, that's not really my area of expertise, but there are definitely interesting connections between types and tree languages, that's what Abstract Categorial Grammar is all about. Maybe you can find something helpful in this <a href="http://www.loria.fr/equipes/calligramme/acg/" rel="nofollow">lovely collection of papers</a>.Anonymoushttps://www.blogger.com/profile/07629445838597321588noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-61859226991268064242013-10-12T00:28:47.161-07:002013-10-12T00:28:47.161-07:00The conversion from MSO to tree automata goes back...The conversion from MSO to tree automata goes back to Rabin69 and Thatcher&Wright68. Thatcher67 describes how tree automata can be compiled into context-free grammars. Unless you are already well-versed in formal language theory, though, I would recommend that you start with <a href="http://thomasgraf.net/doc/papers/PhDThesis_RollingRelease.pdf" rel="nofollow">my thesis</a> instead (seriously, this isn't <b>just</b> lame self-promotion). It slowly introduces MSO and tree automata and uses many examples. The only thing missing is the actual conversion step from MSO to automata, but this is explained fairly well in <a href="http://www.amazon.com/Two-Step-Approaches-Language-Formalism-Generative/dp/3110178214/ref=sr_1_1?ie=UTF8&qid=1381562357&sr=8-1&keywords=two+step+approaches+morawietz" rel="nofollow">Morawietz's "Two Step Approaches to Natural Language Formalisms"</a>, p64--72. If your library doesn't have it, PM me.Anonymoushttps://www.blogger.com/profile/07629445838597321588noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-9724174781586529882013-10-11T11:30:06.722-07:002013-10-11T11:30:06.722-07:00Also I should add, this seems like it might be hig...Also I should add, this seems like it might be highly relevant to type theoretic concerns about refinement types. Ghani, Atkey, and Johann have a paper (https://personal.cis.strath.ac.uk/neil.ghani/papers/ghani-fossacs11.pdf) about when a refinment type (basically a subset type) is inductive. They give an answer that is basically, "whenever the constraint is recursively computable", but it's only a directional implication. This post suggests that there is an identity between tree constraints and some kind of recursive computation, which is a very big deal for type theory if it's correct.Darryl McAdamshttps://www.blogger.com/profile/17446496860034614969noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-61357243530781564292013-10-11T11:13:21.895-07:002013-10-11T11:13:21.895-07:00Actually what's a good chain of papers to read...Actually what's a good chain of papers to read to see the rough shape of the mentioned hoops?Darryl McAdamshttps://www.blogger.com/profile/17446496860034614969noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-38411422822720486112013-10-11T11:11:32.777-07:002013-10-11T11:11:32.777-07:00Where can I read about
> a strategy for compil...Where can I read about<br /><br />> a strategy for compiling tree automata directly into grammars.<br /><br />hopefully with examples of the whole chain down from constraints.Darryl McAdamshttps://www.blogger.com/profile/17446496860034614969noreply@blogger.com