Omer has a recent post on listedness. I have a post coming up that expands on my comments there, but it isn’t really fit for consumption without prior knowledge of subregular complexity and how it intersects with the linguistic concept of locality. So I figured I’d first lead in with a series of posts as a primer on some of the core concepts from subregular complexity. I’ll start with phonology — for historical reasons, and because the ideas are much easier to grok there (sorry phonologists, but it’s a playground compared to syntax). That will be followed by some posts on how subregular complexity carries over from phonology to syntax, and then we’ll finally be in a position to expand on Omer’s post. Getting through all of this will take quite a while, but I think it provides an interesting perspective on locality. In particular, we’ll see that the common idea of “strict locality < relativized locality < non-local” is too simplistic.
With all that said, let’s put on our computational hats and get going, starting with phonology. Or to be more specific: phonotactics.