Parsing Minimalist Languages with Interpreted Regular Tree Grammars

Meaghan Fowlie and Alexander Koller

In Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13), Umea, 2017.

Minimalist Grammars (MGs) are a formalisation of Chomsky's minimalist program, which currently dominates much of mainstream syntax. MGs are simple and intuitive to work with, and are mildly context sensitive, putting them in the right general class for human language. Minimalist Grammars are known to be more succinct than their Multiple Context-Free equivalents, to have regular derivation tree languages, and to be recognisable in polynomial time with a bottom-up CKY-like parser. However, the polynomial is large, $\mathcal{O}(n^{4k+4})$ where $k$ is a grammar constant. By approaching minimalist grammars from the perspective of Interpreted Regular Tree Grammars, we show that standard chart-based parsing is substantially computationally cheaper than previously thought at $\mathcal{O}(n^{2k+3})$. Further, we show how Kobele et al.'s (2007) separation of a minimalist derivation into the derivation trees and their interpretations in algebras of derived structures can be easily applied to such phenomena as covert movement, adjunction, and multilingual synchronous grammars when viewed through the lens of IRTGs.

Download: Download

BibTeX Entry
@InProceedings{minimalist-irtg-17,
	author = {Meaghan Fowlie and Alexander Koller},
	title = {Parsing Minimalist Languages with Interpreted Regular Tree Grammars},
	booktitle = {Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13)},
	year = 2017,
	address = {Umea}
}

Back: Publications