Paper

An Algebraic Characterization of Total Input Strictly Local Functions

---

Abstract

This paper provides an algebraic characteriza- tion of the total input strictly local functions. Simultaneous, noniterative rules of the form A→B/C D, common in phonology, are defin- able as functions in this class whenever CAD represents a finite set of strings. The algebraic characterization highlights a fundamental con- nection between input strictly local functions and the simple class of definite string languages, as well as connections to string functions stud- ied in the computer science literature, the def- inite functions and local functions. No effec- tive decision procedure for the input strictly local maps was previously available, but one arises directly from this characterization. This work also shows that, unlike the full class, a restricted subclass is closed under composition. Additionally, some products are defined which may yield new factorization methods.

Keywords: algebra, input strictly local, definite, locality, transduction

How to Cite:

Lambert, D. & Heinz, J., (2023) “An Algebraic Characterization of Total Input Strictly Local Functions”, Society for Computation in Linguistics 6(1), 25-34. doi: https://doi.org/10.7275/Q54B-MG07