Paper

Automata for subregular syntax: Syntax with strings attached

---

Abstract

Building on recent work in subregular syntax, we argue that syntactic constraints are best understood as operating not over trees, but rather strings that track structural relations such as dominance and c-command. Even constraints that seem intrinsically tied to trees (e.g. constraints on tree tiers) can be reduced to such strings. We define serial constraints as an abstraction that decomposes string constraints into a context function (which associates nodes with strings) and a requirement function (which enforces constraints on these strings). We provide a general procedure for implementing serial constraints as deterministic tree automata. The construction reveals that the many types of constraints found in subregular syntax are variants of the same computational template. Our findings open up a string-based perspective on syntactic constraints and provide a new, very general approach to the automata-theoretic study of subregular complexity.

Keywords: syntax, subregular complexity, string representations, tree automata, Minimalist grammars

How to Cite:

Graf, T. & Hanson, K., (2025) “Automata for subregular syntax: Syntax with strings attached”, Society for Computation in Linguistics 8(1): 23. doi: https://doi.org/10.7275/scil.3184