Recursive prosody is not finite-state (2021)

Abstract: This paper investigates bounds on the generative capacity of prosodic processes, by focusing on the complexity of recursive prosody in coordination contexts in English (Wagner, 2010). Although all phonological processes and most prosodic processes are computationally regular string languages, we show that recursive prosody is not. The output string language is instead parallel multiple context-free (Seki et al., 1991). We evaluate the complexity of the pattern over strings, and then move on to a characterization over trees that requires the expressivity of multi bottom-up tree transducers. In doing so, we provide a foundation for future mathematically grounded investigations of the syntax-prosody interface.

## introduction at the level of words, all attested processes in phonology form regular string languages and can be generated via finite-state acceptors (fsas) and transducers (fsts) @xcite @xcite . however, not much attention has been given to the generative capacity of prosodic processes at the phrasal or sentential level (but see @xcite . the little work that exists in this respect has shown that many attested intonational processes are finite-state and regular @xcite . it is thus a common hypothesis in the literature that the cross-linguistic typology of prosodic phonology should also be regular. in this paper, we falsify this hypothesis by providing a mathematically grounded characterization of a pattern of recursive prosody in english coordination, as empirically documented by @xcite . specifically, we show that when converting a syntactic representation into a prosodic representation, the string language that is generated by this prosodic process is neither a regular nor context-free language, and thus cannot be generated by string-based fsas. as a tree-totree function, the pattern can be captured by a class of bottom-up tree transducers whose outputs correspond to parallel multiple context-free string languages. this paper is organized as follows. in §2, we provide a literature review of phonology and prosodic phonology, with emphasis on the general tendency for regular computation. in §3, we describe the recursive prosody of coordination structures, and why it cannot be generated with an fst over string inputs. in §4, we show how a multi bottom-up tree transducer can generate the prosodic patterns. we discuss our results in §5, and conclude in §6. at the word level, there is a plethora of work on generating prosodic constituents, all of which require finite-state or regular computation, whether for syllables @xcite @xcite , feet @xcite @xcite , or prosodic words @xcite . 1 in fact, most wordlevel prosody seems to require at most subregular computation @xcite @xcite @xcite . however, there is a dearth of formal results for phrasal or intonational prosody. early work in generative phonology treated the prosodic representations as directly generated from the syntax, with any deviations caused by readjustment rules @xcite . notoriously, syntactic representations are at 1 for syllables and feet, there is a large literature of formalization within declarative phonology @xcite . this work tends to employ formal representations that are similar to context-free grammars @xcite @xcite @xcite @xcite @xcite @xcite . but these representations can be restricted enough to be equivalent to regular languages (see earlier such restrictions in @xcite . when analyzed over string languages, this mismatch between supra-regular syntax and regular prosody was not explored much in the subsequent literature. in fact, it seems that current research on computational prosody uses the premise that prosodic structures are at most regular @xcite . crucially, this premise is confounded by the general lack of explicit mathematical formalizations of prosodic systems. for example, there are algorithms for dutch intonation that capture surface intonational contours and other acoustic cues (t @xcite . these algorithms however do not themselves provide sufficient mathematical detail to show that the prosodic phenomenon in question is a regular string language. instead, one has to deduce that dutch intonation is regular because the algorithm does not utilize counting or unbounded look-ahead (t @xcite . as a reflection of this mismatch, early work in prosodic phonology assumed something known as the strict layer hypothesis (slh; @xcite . the slh assumed that prosodic trees cannot be recursive -i.e. a prosodic phrase cannot dominate another prosodic phrase -thus ensuring that a prosodic tree will have fixed depth. subsequent work in prosodic phonology weakened the slh: prosodic recursion at the phrase or sentence level is now accepted as empirically robust @xcite @xcite @xcite . but empirically, it is difficult to find cases of unbounded prosodic recursion @xcite . consider a language that uses only bounded prosodic recursion -e.g. there can be at most two recursive levels of prosodic phrases. the prosodic tree will have fixed depth; and the computation of the corresponding string language is regular. it is then possible to create a computational network that uses a supra-regular grammar for the syntax which interacts with a finite-state grammar for the prosody @xcite . to summarize, it seems that the implicit consensus in computational prosody is that 1) syntax can be supra-regular, but the corresponding prosody is regular; 2) prosodic recursion is bounded. however, as we elaborate in the next section, coordination data from @xcite is a case where syntactic recursion generates potentially unboundedrecursive prosodic structure. the rest of the paper is then dedicated to exploring the consequences of this construction for the expressivity of sentential prosody. ## prosodic recursion in coordination to our knowledge, @xcite is the clearest case where syntactic recursion gets mapped to recursive prosody, such that the recursion is unboundedly deep for the prosody. in this section, we go over the data and generalizations ( §3.1), we sketch wagner's cyclic analysis ( §3.2), and we discuss issues with finiteness ( §3.3). finally, we show that that this construction does not correspond to a regular string language ( §3.4). ## computing recursive prosody over trees wagner (2010)'s treatment of recursive prosody assumes an algorithm that maps a syntactic tree to a prosodic string. it is thus valuable to understand the complexity of processes at the syntax-prosody interface starting from the tree representation of a sentence. assuming we start from trees, there is one more choice to be made, namely whether the prosodic information (in the output) is present within a string or a tree. notably, every tree-to-string transduction can be regarded as a tree-to-tree transduction plus a string yield mapping. as the tree-to-tree case subsumes the tree-to-string one, it makes sense to consider only the former. for a tree-to-tree mapping, the goal is to obtain a tree representation that already contains the correct prosodic information @xcite . this is the focus of the rest of this paper. ## generating recursive prosody the previous section characterized recursive prosody over trees with a non-linear, deterministic mbot. this is a nice result, as mbots are generally wellunderstood in terms of their algorithmic properties. moreover, this result is in line with past work exploring the connections of mbots, tree languages, and the complexity of movement and copying operations in syntax @xcite . we can now ask what the complexity of this approach is. mbots generate output string languages that are potentially parallel multiple context-free languages (pmcfl; @xcite @xcite @xcite . since this class of string languages is more powerful than context-free, the corresponding tree language is not a regular tree language @xcite . this is not surprising, as mbots can be understood as an extension of synchronous tree substitution grammars @xcite . notably, independently of our specific mbot solution, prosody as defined in this paper generates at least some output string languages that lack the constant growth property -hence, that are pmcfls. consider as input a regular tree language of left-branching coordinationate phrases, where each level is simply of the form and(x, mary). the n-th level of embedding from the top extends the string yield by n+2 symbols. this immediately implies no constant growth, and thus no semi-linearity @xcite . interestingly though, the prosody mbot developed here is fairly limited in its expressivity as the transducer states themselves do almost no work, and most of the transduction rules in m pros rely on the ability to store the prosody strength branch. hence, the specific mbot in this paper might turn out to belong to a relatively weak subclass of tree transductions with copying, perhaps a variant of input strictly local tree transductions (cf. @xcite , or a transducer variant of sensing tree automata (cf. @xcite @xcite @xcite . since all of those have recently been used in the formal study of syntax, they are natural candidates for a computational model of prosody, and their sensitivity to minor representational difference might also illuminate what aspects of syntactic representation affect the complexity of prosodic processes. finally, one might worry that the mathematical complexity is a confound of the representation we use, rather than a genuine property of the phenomenon. however, a representation of prosodic strength is necessary and cannot be reduced further for two reasons. first, strength cannot be reduced to syntactic boundaries because a single prosodic edge ( may correspond to | k for any @xmath0. as discussed in depth by @xcite , one cannot simply convert a syntactic tree into a prosodic tree by replacing the labels of nonterminal nodes. second, strength also cannot be reduced to different categories of prosodic constituents -e.g. assuming that | is a prosodic phrase while || is an intonational phrase. as argued in depth in @xcite , these different constituent types do not map neatly to prosodic strength. instead, these boundaries all encode relative strengths of prosodic phrase boundaries. ## conclusion this paper formalizes the computation of unbounded recursive prosodic structures in coordination. their computation cannot be done by string-based finitestate transducers. they instead need more expressive grammars. to our knowledge, this paper is one of the few (if only) formal results on how prosodic phonology at the sentence-level is computationally more expressive than phonology at the word-level. as discussed above, recent work in prosodic phonology relies on the assumption that prosodic structure can be recursive. however, because such work usually uses bounded-recursion, such phenomena are computationally regular. departing from this stance, this paper focused on the prosodic phenomena reported in @xcite as a core case study, because of the following fundamental properties: in this paper, we focused on explicitly generating the prosodic strengths at each recursive prosodic levels, putting aside the mathematically simpler task of converting a recursive syntactic tree into a recursive prosodic tree @xcite -which is a process essentially analogous to a relabeling of the nonterminal nodes of the syntactic tree, without care for the prosodic strength. the mapping studied in this paper has been conjectured in the past to be computationally more expressive than regular languages or functions @xcite . here, we formally verified that hypothesis. an open question then is to find other empirical phenomena which also have the above properties. one potential area of investigation is the assignment of relative prominence relations in english compound prosody @xcite ). however, english compound prosody is a highly controversial area. it is unclear what is the current consensus on an exact algorithm for these compounds, especially one that utilizes recursion and is not based on impressionistic judgments @xcite . in this sense, the mathematical results in this paper highlight the importance of representational commitments and of explicit assumptions in the study of prosodic expressivity. our paper might then help identify crucial issues in future theoretical and empirical investigations of the syntax-prosody interface.