Matthew Hayden


2026

This paper offers an updated perspective on the computational complexity of reduplication. Since one-way deterministic transducers cannot model reduplication in a straightforward way, the phenomenon has long been considered the outlier of morphology from a complexity perspective. Drawing on algebraic methods, I show that the vast majority of reduplicative processes belong to a few remarkably simple classes of subregular functions. A detailed study of the RedTyp database (Dolatian and Heinz, 2019) reveals that 100% of the surveyed reduplicative processes correspond to string-to-string functions in the class DA, while over98% are locally testable (LJ1) and over 87% are locally trivial (L1). These results indicate a new upper bound on the complexity of reduplication that is comparable to that of morphological processes in general.

2025