Formal Linguistics and Computational Linguistics

This paper studies the learning of two functions given positive samples of their composition, motivated by an empirical problem in natural language phonology. Empirically relevant conditions under which this is possible are identified and a provably correct algorithm is given that can semi-strongly identify the two functions in polynomial time and data. In order to clearly illustrate the learning problem and related concepts, we focus on a simple subset of input strictly 2-local functions. But we further argue that the general learning procedure we propose can be extended to more general classes of functions.

The simultaneous inference of underlying representations (URs) and a phonological grammar from alternating surface representations (SRs) in a morphological paradigm is a core problem in phonological learning that only recently has seen progress (Tesar, 2014; Cotterell et al., 2015; Rasin et al., 2018). This paper proposes a learning algorithm that infers URs and phonological processes from SRs based on the hypothesis that phonological generalizations belong to restrictive subregular regions in the Chomsky Hierarchy (Heinz, 2018). We give a procedure that, given sequences of morphemes paired with SRs, learns URs and a phonological grammar that is an input strictly local (ISL; Chandlee, 2014; Chandlee & Heinz, 2018) function. ISL functions are exactly those which make changes in the output with respect to the local information in the input. For now, the procedure is restricted to simplex ISL processes; that is, those exhibiting a single change. However, this illustrates that restrictive computational principles, combined with major principles in phonological analysis, allow for significant progress in understanding how phonological grammars and URs are learned. The paper is organized as follows. Section 2 briefly introduces the paradigm of the learning algorithm. Section 3 discusses the computational structure encoded in the learner. Section 4 is a detailed explanation of the algorithm with a simple example as illustration. Section 5 compares this algorithm with other algorithms and presents its advantages. The last section concludes the paper.

In addition to the substance in phonology, a number of researchers have argued that computation also matters in phonology. Using the data in Yavapai (Yuman language), I show that other than an OT analysis focusing mainly on substance, a computational analysis is necessary for explaining the complex syllabification processes and the frequencies of optional surface representations due to different syllabifications. I will use computational complexity encoded in subregular hierarchy as the main technical tool in the computational analysis. Our main hypothesis is that when both SRs are well-formed based on the syllable phonotactics, the one less complex to generate is more frequently attested. The paper shows that the syllabification pattern in Yavapai necessarily requires a computational motivation, which in turn shows that computational property is a crucial factor in phonological transformations.

Disjunction is used to connect multiple options when there is insufficient information to determine which one is true. However, free choice disjunction defies this simple fact – when a disjunction acts as a free choice operator, all options are true. The usage of free choice disjunction is observed to usually co-occur with modals, pluralities, etc. This paper introduces a novel observation of sentences with free choice disjunction in English. Multiple data points are presented to demonstrate the semantic distribution. I propose that free choice reading in disjunctions depends on three factors –the sentence’s genericity, scope of the disjunction and disjuncts being imperfect nominals.