Paper

Compiling Search & Change Rules into Subsequential Finite-State Transducers

---

Abstract

Search & Change (S&C) is a procedural model of phonological rule application that is conceptually clear and linguistically motivated, but whose computational properties have not been fully characterized. This paper provides a formal specification of S&C within the framework of Logical Phonology, presents a linear-time algorithm for rule application with a proof of correctness, and gives a compilation procedure mapping S&C rules to a single transition structure that is subsequential in one scan orientation and reverse-subsequential in the other, situating S&C within a well-understood subclass of regular string-to-string functions with known learnability guarantees and algebraic characterizations, implying that S&C-definable mappings are learnable from positive input/output pairs and amenable to algebraic classification.

Keywords: computational phonology, finite-state phonology, finite-state transduction, formal language theory, subsequential functions, Logical Phonology, Search and Change

How to Cite:

Azadegan, M., (2026) “Compiling Search & Change Rules into Subsequential Finite-State Transducers”, Society for Computation in Linguistics 9(1). doi: https://doi.org/10.7275/scil.4009