Learning Strictly Local Subsequential Functions

Learning Strictly Local Subsequential Functions Jane Chandlee University of Delaware Department of Linguistics and Cognitive Science 125 East Main Street Newark, DE 19716 janemc@udel.edu R´emi Eyraud QARMA team Laboratoire d’Informatique Fondamentale Marseille, France remi.eyraud@ lif.univ-mrs.fr Jeffrey Heinz University of Delaware Department of Linguistics and Cognitive Science 125 East Main Street Newark, DE 19716 heinz@udel.edu Abstract We define two proper subclasses of sub- sequential functions based on the concept of Strict Locality (McNaughton and Papert, 1971; Rogers and Pullum, 2011; Rogers et al., 2013) for formal languages. They are called Input and Output Strictly Local (ISL and OSL). We provide an automata-theoretic characterization of the ISL class and theorems establishing how the classes are related to each other and to Strictly Local languages. We give evidence that local phonological and morpho- logical processes belong to these classes. Fi- nally we provide a learning algorithm which provably identifies the class of ISL functions in the limit from positive data in polynomial time and data. We demonstrate this learning result on appropriately synthesized artificial corpora. We leave a similar learning result for OSL functions for future work and sug- gest future directions for addressing non-local phonological processes. 1 Introduction In this paper we define two proper subclasses of sub- sequential functions based on the properties of the well-studied Strictly Local formal languages (Mc- Naughton and Papert, 1971; Rogers and Pullum, 2011; Rogers et al., 2013). These are languages that can be defined with grammars of substrings of length k (called k-factors), such that a string is in the language only if its own k-factors are a subset of the grammar. These languages have also been char- acterized by Rogers and Pullum (2011) as those that have the property expressed in the following theo- rem (which can be taken as a defining property): Theorem 1 (Suffix Substitution Closure). L is Strictly Local iff for all strings u1, v1, u2, v2, there exists k ∈ N such that for any string x of length k − 1, if u1xv1, u2xv2 ∈ L, then u1xv2 ∈ L. These languages can model natural language phonotactic constraints which pick out contiguous substrings bounded by some length k (Heinz, 2007; Heinz, 2010). We define Input Strictly Local (ISL) and Output Strictly Local (OSL) functions which model phonological processes for which the target and triggering context are a bounded contiguous substring. Here our use of ‘process’ is not specific to rule-based grammatical formalisms (such as SPE (Chomsky and Halle, 1968)). ISL and OSL func- tions model mappings from underlying forms to sur- face forms, which are also the bedrock of constraint- based frameworks like Optimality Theory (Prince and Smolensky, 1993). By showing that local phonological processes can be modeled with ISL (and OSL) functions, we pro- vide the strongest computational characterization of the input-output mappings these processes repre- sent. While it has been shown that phonological mappings describable with rules of the form A → B / C D (where A, B, C, and D are regular languages) are regular …

Content truncated to 500 words