Recursive prosody is not finite-state

Hossep Dolatian, Aniello De Santo, Thomas GrafACL 2021

TL;DR

This paper demonstrates that the prosodic patterns in English coordination, specifically how syntactic structure influences intonation, are more complex than previously assumed. Using a formal linguistic framework, the authors show that these prosodic patterns cannot be generated by simple finite-state machines, suggesting a need for more powerful computational models to understand the syntax-prosody interface.

What Problem Does This Paper Address?

For decades, phonological processes, especially at the word level, have been successfully modeled using finite-state automata (FSAs) and transducers (FSTs), implying they are computationally "regular." This regularity has led to a common hypothesis that prosodic processes at higher levels (phrasal, sentential) should also be regular. While some early work supported this, the current paper challenges this assumption by examining recursive prosody in English coordination, as documented by Wagner (2010). The core problem is to determine the computational complexity of mapping syntactic structures to prosodic representations, particularly when recursion is involved, and to see if this complexity exceeds the regular language class.

Methods

The authors tackle this problem by first analyzing the prosodic mapping as a string-to-string function. They demonstrate that the observed recursive prosody in coordination leads to output string lengths that grow quadratically with input size, a property that cannot be captured by standard finite-state transducers. To overcome this limitation, they shift to a tree-to-tree transduction framework, employing multi bottom-up tree transducers (MBOTs). MBOTs are a more powerful class of transducers that can handle more complex mappings by allowing states to pass multiple output subtrees. They develop a specific MBOT, Mpros, designed to capture Wagner's cyclic analysis of prosodic recursion, which assigns prosodic strength based on the depth and associativity of syntactic coordination. This MBOT is illustrated with rules that incrementally add prosodic boundaries ($) to a tree representation, reflecting the recursive structure.

Datasets

Not discussed in the paper. The paper focuses on formal linguistic analysis and theoretical modeling rather than empirical data collection or training on specific datasets. The "data" used is the linguistic phenomenon of English coordination and its documented prosodic patterns.

Key Insights and Ideas

  • Prosody is not always regular: The paper provides a formal proof that certain prosodic phenomena, specifically recursive prosody in coordination, are computationally more complex than regular languages, directly challenging a long-standing assumption in the field.
  • Recursion is the key: The complexity arises from the potentially unbounded recursion in syntactic structures that maps to recursive prosodic structures, requiring more than finite memory to process.
  • Tree-based models are necessary: String-based finite-state models are insufficient. The authors show that a more expressive model, multi bottom-up tree transducers (MBOTs), is required to capture these complex mappings.
  • Syntax-Prosody Interface is Rich: The work highlights that the interface between syntax and prosody is not a simple one-to-one mapping but can involve intricate computational processes that mirror or even exceed the complexity of syntactic computation itself.
  • Formalizing Linguistic Intuition: The paper translates linguistic observations about prosodic strength and recursion into a formal computational framework, providing a foundation for future theoretical and empirical investigations.

Key Results

  • The string language generated by the recursive prosody of English coordination is shown to be neither regular nor context-free, meaning it cannot be generated by string-based FSAs.
  • The output string length grows at least quadratically ($O(n^2)$) with the input string size, violating the linear growth property of regular functions.
  • A multi bottom-up tree transducer (Mpros) is developed that can formally capture the recursive prosodic patterns observed in coordination, demonstrating that these patterns can be generated by a more powerful, tree-based computational model.
  • The MBOT approach generates output that corresponds to parallel multiple context-free string languages (PMCFLs), a class of languages more powerful than context-free languages.

Limitations and Future Work

  • Finite Bounds: The paper acknowledges that real-world data often involves finite bounds on coordination depth due to processing limitations. The analysis abstracts away from these finite bounds to study the underlying computational capacity.
  • Specific MBOT Subclass: While the MBOT used is powerful, the authors suggest it might belong to a weaker subclass of tree transductions, and further investigation into its precise expressivity is warranted.
  • Other Phenomena: The authors pose an open question about finding other empirical phenomena with similar properties (unbounded syntactic and prosodic recursion, distinct acoustic cues for strength) and suggest investigating English compound prosody as a potential candidate.
  • Phrase Structure Trees: The current work uses dependency trees for simplicity. Future work could extend the MBOT to phrase structure trees, which might be useful for studying the interaction of prosody and movement.
  • PMCFLs: The paper notes that the MBOT approach generates PMCFLs and leaves further exploration of this class of languages in the context of prosody for future work.

Summary updated

BibTeX
@inproceedings{dolatian2021recursive,
  author = {Hossep Dolatian and Aniello De Santo and Thomas Graf},
  title = {{Recursive prosody is not finite-state}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}

Loading related content...

Figure