[Author Login]
[Home]
ROA:1138
Title:On the complexity of the problem of the acquisition of phonotactics in Optimality Theory
Authors:Giorgio Magri
Comment:
Length:25
Abstract:The problem of the acquisition of phonotactics in Optimality Theory is formulated as the problem of learning a ranking consistent with a finite set of data that furthermore corresponds to a smallest (w.r.t. set inclusion) language. Following Heinz, Kobele and Riggle (2008), the paper focuses on the ''universal'' formulation of the problem, whereby generating function and constraint set vary arbitrarily as inputs of the problem. It is shown that the universal problem of the acquisition of phonotactics in OT is not-solvable (NP-complete), even when we take the time to list all candidates. This result motivates a ''non-universalistic'' approach to the problem of the acquisition of phonotactics, whereby the problem is restricted to specific families of generating functions and constraint sets and solution algorithms are allowed to take advantage of the peculiar properties of these families.
Type:Paper/tech report
Area/Keywords:Learnability,Phonology
Article:Version 1