Automata for Subregular Syntax: Syntax with Strings Attached

Graf, Thomas, and Kenneth Hanson

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.

Files [pdf]

@InProceedings{GrafHanson25SCiL,
  author    = {Graf, Thomas and Hanson, Kenneth},
  author+an = {2=sbu},
  title     = {Automata for Subregular Syntax: Syntax With Strings Attached},
  year      = {2025},
  booktitle = {Proceedings of the {Society} for {Computation} in
               {Linguistics} ({SCiL}) 2025},
  article   = {23},
  doi       = {10.7275/scil.3184},
  openaccess = {gold},
}

More Output

Sensing Tree Automata as a Model of Syntactic Dependencies

Tue 01 January 2019 | in Papers |
| Minimalist Grammars | syntax | movement | derivation trees | subregular | automata |

Graf, Thomas, and Aniello De Santo

Abstract Various aspects of syntax have recently been characterized in subregular terms. However, these characterizations operate over very different representations, including string encodings of c-command relations as well as tiers projected from derivation trees. We present a way to …
read more
Sensing Tree Automata as a Model of Syntactic Dependencies

Tue 01 January 2019 | in Presentations |
| Minimalist Grammars | syntax | movement | derivation trees | subregular | automata |

Graf, Thomas, and Aniello De Santo

Abstract Various aspects of syntax have recently been characterized in subregular terms. However, these characterizations operate over very different representations, including string encodings of c-command relations as well as tiers projected from derivation trees. We present a way to …
read more
Beyond the Apparent: Cognitive Parallels Between Syntax and Phonology

Wed 01 January 2014 | in Papers |
| phonology | syntax | subregular hierarchy | formal language theory | cognitive architecture | automata |

Graf, Thomas

Abstract One of the central changes in 20th century linguistics was the reconceptualization of language as a cognitive ability rather than merely an abstract relational system of signs —- in the terminology of Chomsky (1986), the move from E-language to I-language. This shift entails …
read more

More Output

links

contact