Matthew Hayden
2026
Algebraic Classification of Reduplicative Processes
Matthew Hayden
Proceedings of the Society for Computation in Linguistics 2026
Matthew Hayden
Proceedings of the Society for Computation in Linguistics 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.