Efficient learning of Output Tier-based Strictly 2-Local functions

Abstract

This paper characterizes the Output Tier-based Strictly k-Local (OTSL k ) class of string-tostring functions, which are relevant for modeling long-distance phonological processes as input-output maps. After showing that any OTSL k function can be learned when k and the tier are given, we present a new algorithm that induces the tier itself when k = 2 and provably learns any total OTSL 2 function in polynomial time and data-the first such learner for any class of tier-based functions.