Handbook chapter on Minimalism and computational linguistics

🕑 4 min • 👤 Thomas Graf • 📆 March 30, 2021 in Discussions • 🏷 Minimalist grammars, formal language theory

Aah, the soothing sound of crickets. In case you’ve been wondering about the recent radio silence at this prestigious online soapbox, my todo list finally caught up with me and I had to spend the last few weeks writing up/revising some papers that were way overdue. It was a matter of life and death — the editors were already contemplating Satanic blood sacrifices, and while I enjoy a good Black Mass as much as the next guy, I’d rather not be its subject matter. In this post I’d like to talk a bit about one of those papers, a chapter on Minimalist grammars in an upcoming handbook on Minimalism. Though I have to admit that it’s mostly a ruse to get some of you to give it a read and leave some feedback in the comments section.

Continue reading

Logical transductions: Bats, butterflies, and the paradox of an almighty God

🕑 14 min • 👤 Thomas Graf • 📆 September 21, 2020 in Tutorials • 🏷 formal language theory, transductions, subregular, first-order logic

Since we recently a had a post about Engelfriet’s work on transductions and logic, I figured I’d add a short tutorial that combines the two and talks a bit about logical transductions. I won’t touch on concrete linguistic issues in this post, but I will briefly dive into some implications for how MGs push PF and LF directly into “syntax” (deliberate scare quotes). I also have an upcoming post on representations and features that is directly informed by the logical transduction framework. So if you don’t read anything here unless it engages directly with linguistics, you might still want to make an exception this time, even if today’s post is mostly logic and formulas.

Continue reading

A tribute to Joost Engelfriet

🕑 6 min • 👤 Thomas Graf • 📆 September 02, 2020 in Discussions • 🏷 formal language theory, tree transductions

Ed Stabler sent me a link to the most recent paper by Joost Engelfriet, which concludes with the following message:

That’s all folks! This was my last paper. Thank you, dear reader, and farewell.

That’s bitter-sweet. On the one hand, I admire that he can draw a line in the sand like this. On the other hand, I wish he’d erase that line and keep going for a few more years. Even though Engelfriet isn’t a mathematical linguist — and might not even be aware of the more linguistic side of that field, the one that we serve here at the Outdex Café — he has had a profound influence on the field, including a lot of my own work.

Continue reading

When parsing isn't about parsing

🕑 7 min • 👤 Thomas Graf • 📆 June 18, 2020 in Discussions • 🏷 syntax, morphology, parsing, formal language theory, movement

As a student I didn’t care much for work on syntactic parsing since I figured all the exciting big-picture stuff is in the specification of possible syntactic structures, not how we infer these structures from strings. It’s a pretty conventional attitude, widely shared by syntacticians and a natural corollary of the competence-performance split — or so it seems. But as so often, what seems plausible and obvious at first glance quickly falls apart when you probe deeper. Even if you don’t care one bit about syntactic processing, parsing questions still have merit because they quickly turn into questions about syntactic architecture. This is best illustrated with a concrete example, in that abstract sense of “concrete” that everyone’s so fond of here at the outdex headquarters.

Continue reading

The anti anti missile missile argument argument

🕑 7 min • 👤 Thomas Graf • 📆 June 21, 2019 in Discussions • 🏷 formal language theory, generative capacity, morphology, semantics

Computational linguists overall agree that morphology, with the exception of reduplication, is regular. Here regular is meant in the sense of formal language theory. For any given natural language, the set of well-formed surface forms is a regular string set, which means that it is recognized by a finite-state automaton, definable in monadic second-order logic, a projection of a strictly 2-local string set, has a right congruence relation of finite index, yada yada yada. There’s a million ways to characterize regularity, but the bottom line is that morphology defines string sets of fairly limited complexity. The mapping from underlying representations to surface forms is also very limited as everything (again modulo reduplication) can be handled by non-deterministic finite-state transducers. It’s a pretty nifty picture, though somewhat loose in my subregular eyes that immediately pick up on all the regular things you don’t find in morphology. Still, it’s a valuable result that provides a rough approximation of what morphology is capable of; a decent starting point for further inquiry. However, there is one empirical argument that is inevitably brought up whenever I talk about the regularity of morphology. It’s like an undead abomination that keeps rising from the grave, and today I’m here to hose it down with holy water.

Continue reading

Surprising theorems

🕑 4 min • 👤 Thomas Graf • 📆 June 08, 2019 in Discussions • 🏷 history, literature, formal language theory

Time for a quick break from the on-going feature saga. A recent post on the Computational Complexity blog laments that theorems in complexity theory have become predictable. Even when a hard problem is finally solved after decades of research, the answer usually goes in the expected direction. Gone are the days of results that come completely out of left field. This got me thinking if mathematical linguistics still has surprising theorems to offer.

Continue reading