Weakly deterministic transformations are subregular

Andrew Lamont, Charlie O’Hara, Caitlin SmithACL 2019

TL;DR

This paper argues that phonological transformations in natural language are "subregular," meaning they can be modeled by a restricted class of computational systems. By demonstrating that certain regular functions are not weakly deterministic, the authors provide evidence against more complex computational models and support the hypothesis that phonological processes are inherently simpler.

What Problem Does This Paper Address?

In computational phonology, a central question is understanding the complexity of transformations that map underlying linguistic representations to their surface forms. These transformations are known to be "regular" (computable by finite automata), but researchers have been trying to pinpoint a more restrictive class. The "subregular hypothesis" suggests that all phonological transformations are even more restricted, falling into classes like "subsequential" or "weakly deterministic."

The challenge lies in defining these classes precisely and determining if they accurately capture all attested phonological processes. Specifically, the paper investigates "weakly deterministic" transformations, which can be decomposed into a left-to-right and a right-to-left subsequential process. The authors aim to determine if this class is a proper subset of regular functions, meaning there are regular functions that are not weakly deterministic. If such functions exist and are not found in natural language, it would strengthen the subregular hypothesis.

Methods

The core of the paper's method involves constructing specific computational functions (modeled as finite-state transducers or FSTs) that are regular but not weakly deterministic. They achieve this by:

  • Defining "Weakly Deterministic": The authors adhere to the definition by Heinz and Lai (2013), where a transformation is weakly deterministic if it can be decomposed into a left-subsequential FST and a right-subsequential FST.
  • Constructing Counterexamples: They introduce two hypothetical phonological processes, "first-last UTP" and "double-edged spread," which are designed to be regular but violate the conditions for weak determinism. These are inspired by attested phonological phenomena.
  • Analyzing Markup Strategies: A key technique for demonstrating weak determinism is the "markup strategy," where one FST encodes information in an intermediate representation that a second FST uses to complete the transformation. The paper shows why this strategy fails for their counterexamples.
  • Formalizing Ambiguous Contexts: The authors formally define "ambiguous contexts" – situations where a subsequential FST cannot determine the correct output based on its limited lookahead/lookback. They then analyze conditions under which these ambiguities can or cannot be resolved by markup.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructs and hypothetical phonological processes rather than empirical data analysis from existing corpora.

Key Insights and Ideas

  • Weak Determinism is Not Universal: The paper provides concrete examples of regular functions that cannot be modeled as weakly deterministic. This is a crucial finding for computational phonology, as it shows that the class of weakly deterministic functions is indeed a proper subset of regular functions.
  • The Importance of Word Boundaries: The failure of the markup strategy for the counterexamples is often linked to the necessity of referencing both word edges simultaneously. This suggests that processes requiring information from both the beginning and end of a word simultaneously are less likely to be weakly deterministic.
  • Subregular Hypothesis Strengthened: By demonstrating that some regular functions are not weakly deterministic, and by arguing that attested phonological processes are weakly deterministic, the paper provides strong support for the subregular hypothesis. It suggests that natural language phonology operates within these more constrained computational classes.
  • Characterizing Unbounded Circumambient Mappings: The paper offers a characterization of when unbounded circumambient mappings (those dependent on information from both sides of a target, with no bound on distance) are weakly deterministic, linking it to the presence of banned substrings and the role of word boundaries.

Key Results

The paper demonstrates that "first-last UTP" and "double-edged spread" are regular functions that are not weakly deterministic. This is shown by proving that the standard markup strategy, which relies on decomposing the process into two subsequential FSTs, fails for these hypothetical mappings. The failure is attributed to the inability of subsequential FSTs to unambiguously encode information about both word edges simultaneously, which is required by these processes.

Limitations and Future Work

  • Hypothetical Mappings: The paper uses hypothetical phonological processes ("first-last UTP," "double-edged spread") as counterexamples. While inspired by attested phenomena, their direct linguistic reality is not the primary focus. The authors acknowledge this by stating they are "variations of attested transformations."
  • Attested Processes are Weakly Deterministic: The paper relies on the claim that all attested phonological processes studied so far are weakly deterministic. While they cite numerous examples (e.g., UTP, vowel harmony, tone spreading), the universality of this claim could be further explored.
  • Future Work: The authors suggest that the characterization of weakly deterministic unbounded circumambient mappings is an initial step. Future work could involve further exploring the hierarchy of subregular classes (as depicted in Figure 5) and investigating whether all attested phonological transformations indeed fall into the "bi-weakly deterministic" category. They also note that the definition of weak determinism used differs from a revised definition proposed by McCollum et al. (2018), suggesting further investigation into these definitions and their implications.

Summary updated

BibTeX
@inproceedings{lamont2019weakly,
  author = {Andrew Lamont and Charlie O’Hara and Caitlin Smith},
  title = {{Weakly deterministic transformations are subregular}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
}
Figure