An Algebraic Characterization of Total Input Strictly Local Functions

Authors: ,


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). doi: