The Match-Extend serialization algorithm in Multiprecedence (2021)

Abstract: Raimy (1999; 2000a; 2000b) proposed a graphical formalism for modeling reduplication, originallymostly focused on phonological overapplication in a derivational framework. This framework is now known as Precedence-based phonology or Multiprecedence phonology. Raimy’s idea is that the segments at the input to the phonology are not totally ordered by precedence. This paper tackles a challenge that arose with Raimy’s work, the development of a deterministic serialization algorithm as part of the derivation of surface forms. The Match-Extend algorithm introduced here requires fewer assumptions and sticks tighter to the attested typology. The algorithm also contains no parameter or constraint specific to individual graphs or topologies, unlike previous proposals. Match-Extend requires nothing except knowing the last added set of links.

## introduction this paper provides a general serialization algorithm for all morphological structures in all languages. the challenge of converting non-linear structures of linguistic representation into a format ready to be handled in production is one that matters to both morphosyntax and morphophonology. reduplication is a phenomenon at the frontier of morphology and phonology that has drawn a lot of attention in the last few decades. reduplication's non-concatenative nature and the fact that it manifests long-distance dependencies among segments set it apart from the 'standard' wordformation that most theories are designed to handle. these properties have often pushed theoreticians to propose expansive systems such as copying procedures on top of traditional linear segmental phonology to make the system powerful enough to handle these dependencies. the multiprecedence model expanded upon here builds on properties that are already implicit in all approaches to phonological representation, and actually gets rid of some standard assumptions. it accounts for attested patterns and predicts an unattested reduplication pattern to be impossible. ## multiprecedence the theory of multiprecedence seeks to account for reduplication representationally via loops in a graph. eschewing correspondence statements and copying procedures, multiprecedence treats reduplication as fundamentally a structural property created by the addition of an affix, whose serialization has the effect of pronouncing all or part of the form twice. consider a string like fig. 1a , the standard way of representing the segments that constitute a phonological representation. an alternative way to encode that same information is in the form of a set of immediate precedence statements like fig. 1b . for legibility the set of pairs in fig. 1b can be represented in the form of a graph. adding the convention that of using # and % for the start and end symbols respectively we get the picture in fig. 1c . in general i will refer to this as the graph representation. a.kaet b. { start, k , k,ae , ae,t , t,end } c. # → @xmath0. there is no a priori logical reason in this representation why forms should be linear, with one segment following another in a chain. this is only an assumption that we impose on the structure when assuming strings. this assumption is what multiprecedence abandons. multiprecedence proposes that asymmetry and irreflexivity are not relevant to phonology. a segment can precede or follow multiple segment, two segments can transitively precede each other, and a segment can precede itself. a valid multiprecedence graph is not restricted by topology, a term a will use for the pattern of the graph independent from the content of the nodes. using this view of precedence, affixation is the process of combining the graph representations of different morphemes. a word is a graph consisting of the edges and vertices (precedence relations and segments) of one or more morphemes. an example of the suffixation of the english plural is shown in fig. 2a , and the infixation of the atayal animate focus morpheme is given in fig. 2b . full root reduplication, which expresses the plural of nouns in indonesian is shown in fig. 2c . there are two things to notice in fig. 2c . first, that a precedence arrow is added, without any segmental material: the reduplicative morpheme consists of just that arrow. second, although fig. 2a and fig. 2b each offer two paths from the start to the end of the graph, fig. 2c contains a loop that offers an infinite number of paths from start to end. the representation itself does not enforce how many times the arrow added by the plural morpheme should be traversed. all three of these structures have to be handled by a serialization algorithm in order to be actualized by the phonetic motor system, which selects a path through the graph to be sent to the articulators. a correct serialization algorithm must be able to select the correct of the two paths in fig. 2a and fig. 2b and the path going through the back loop only once in fig. 2c . i will assume here that these forms are constructed by the attachment of an affix morpheme onto a stem as in fig. 3 . english speakers have a graph as a lexical item for the plural as in fig. 3a and a lexical item for cat as in fig. 3b , which combine as in fig. 3c . the moniker "last segment" is an informal way to refer to that part of the affix that is responsible for attaching it to the stem in the right location. this piece of the plural affix will attach onto the last segment, the one preceding the end of the word %, of what it combined with, and onto %, yielding fig 3c . similarly the atayal form in fig. 2 is built from a root #hnup% 'soak' and an infix -mmarking the animate ac-a. tor focus and attaching between the first and the second segment. for details on the mechanics of attachment see raimy (2000a, §3.2), samuels (2009, p.177-87), and papillon (2020, §2.2). it suffices here to say that at vocabulary insertion an affix can target certain segments of the stem for attachment. raimy (2000a) shows how this representation can generate the reduplicative patterns from numerous languages as well as account for such phenomena as over-and under-application of phonological processes in reduplication. a. [last segment] → @xmath1. # → @xmath2. # k ae t % z given the assumption that a non-linear graph cannot be pronounced, phonology requires an algorithm capable of converting graph representations into strings like in fig. 2 . two main families of algorithms have been proposed. @xcite proposed a stack-based algorithm which was expanded upon by @xcite and @xcite . this algorithm traverses the graph from # to % by accessing the stack. this idea suffers the problem of requiring parameters on individual arcs. every morphologically-added precedence link must be parametrized as to its priority determining whether it goes to the top or the bottom of the stack. this is necessary in this system because when a given arc is traversed is not predictable on the basis of when it is encountered in a traversal. this parametrization radically explodes the range of patterns predicted to be possible much beyond what is attested. @xcite proposed a different constraint-base algorithm which globally compares paths through the graph for completeness and economy but suffers the problem of requiring ad hoc constraints targeting individual types of graphs, lacking generality. in the rest of this article i will present a new algorithm which lacks any parameter and whose two operations are generic and not geared towards any specific configuration. ## the match-extend algorithm this section will present the match-extend algorithm and follow up with a demonstration of its operation on various attested multiprecedence topologies. the input to the algorithm is the set of pairs of segments corresponding to the pairs of segments in immediate precedence relation without the affix, e.g. {#k,kae,aet,t%} for the english stem kaet, and the set of pair of segments corresponding to the precedence links added by the affix, e.g. {tz,z%} when the plural is added. intuitively the algorithm starts from the morphologically added links and extends outwards by following the precedence links in the stemset, the set of all precedence links in the stem to which the morpheme is being added. if there is more than one morphologically added link, they all extend in parallel and collapse together if one string ends in one or more segment and the other begins with the same segment or segments. a working version of this algorithm coded in python will be included as supplementary material. ## one limitation of match-extend: overly symmetrical graphs there is a gap in the predictions of fig. 11 : closest attachment predicts that morphologicallyadded edges will attach in the order they are the closest, which relies on an asymmetry in the form such that morphologically-added links are closer in one order than the other. this leaves the problem of symmetrical forms like fig. 19 . the former of there was posited in the analysis of semai continuative reduplication by @xcite for forms like dnoh 'appearance of nodding' to dh-dnoh; the latter would be needed in various languages reduplicating cvc forms with vowel changes such as the takelma aorist described in @xcite ) like t'eu 'play shinny' to t'eut'au. these are the forms which, in the course of match-extend, will come to a point where match is indeterminate because two strings could match equally well in either direction. for example the workspace of the first of these structures will start with ac and ca, which can match either as aca or cac. the former would extend into #acabc% and the latter into #abcac%. match-extend as stated so far is therefore indeterminate with regard to these symmetrical forms. this is not an insurmountable problem for match-extend. to the contrary this is a problem was misidentified by previous authors and is unproblematic for match-extend. alternatively it could be that symmetrical forms lead to both options being constructed and this optionality is resolved in extra-grammatical ways. i will leave this hole in the theory open, as a problem to be resolved through further research. ## conclusion this article presents an invariant serialization algorithm for all morphological patterns in multiprecedence. the multiprecedence research program has been fruitful in bringing various nonconcatenative phenomena other than reduplication within the scope of a derivational item-andarrangement model of morphology, including e.g. subtractive morphology @xcite , semitic templatic morphology @xcite , and vowel harmony, word tone, and allomorphy @xcite . a serialization algorithm capable of handling these structures is crucial for the completeness of the theory. as pointed out by a reviewer, it is crucial to develop a a typology of the possible attested graphical input structures to the algorithm so as to properly characterize and formalize the algorithm needed. in every form discussed here the roots is implicitly assumed to be underlyingly linear and affixes alone add some topological variety to the graphs, as is mostly the case in all the forms from @xcite . elsewhere i have challenged this idea by positing parallel structures both underlyingly and in the output of phonology @xcite . if these structures are allowed in multiprecedence phonology then match-extend will need to be amended or enhanced to handle more varied structures. in this paper i proposed a model that departs from the previous ones in being framed as patching a path from the morphology-added links towards # and % from the inside-out, as opposed to the existing models seeking to give a set of instructions to correctly traverse the graph from # to % from beginning to the end.