💬 NLP

Compiling Rewrite Rules to Finite-State Transducers with the Worsening Trick

This paper introduces a compact and uniform compilation scheme for finite-state transducers based on the "worsening trick," which generates all legal rewrite candidates and filters suboptimal ones, thereby simplifying the implementation of complex rewrite rules in the PyFoma tool while maintaining exact equivalence with established methods.

Original authors: Mans Hulden, Michael Ginn

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mans Hulden, Michael Ginn

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Fixing Text with a "Worsening" Filter

Imagine you are a strict editor trying to fix typos in a book. You have a rule: "If you see the letter b between two a's, change it to a p."

In the world of computers (specifically in linguistics), this is called a rewrite rule. The challenge is that computers are literal. If you have a long string like abababa, the computer gets confused:

Should it change the first b?
Should it change the second b?
Should it change both?
What if changing one b creates a new pattern that looks like it needs changing too?

The authors, Mans Hulden and Michael Ginn, present a new, simpler way to teach computers how to apply these rules without getting stuck in a loop or missing the best solution. They call their method the "Worsening Trick."

The Old Way: The "Marker" Maze

Previously, computer scientists tried to solve this by building a complex maze. They would insert invisible "markers" (like little flags) into the text to say, "Hey, this spot is a candidate for changing." Then they would build a giant machine to check if those flags were in the right place, make the changes, and then try to remove the flags.

The authors say this old method is like trying to build a house by first painting every brick a different color, checking the paint, and then sanding it all off. It works, but it's messy, complicated, and hard to update.

The New Way: The "Worsening" Filter

The authors propose a much cleaner three-step process. Think of it like a talent show audition where the judges are very strict.

Step 1: Generate All Possibilities (The "Open Mic")

First, the computer generates every single possible way the text could be changed. It doesn't worry about rules yet.

Analogy: Imagine a room full of people. Everyone is holding a sign that says, "I think I should change this word." Some people are holding signs for the first word, some for the second, some for both. It's a chaotic room with every possible combination of changes.

Step 2: Check the Context (The "Venue Rules")

Next, the computer checks if those changes are actually allowed by the rules (the "context").

Analogy: The venue manager walks in and says, "You can only change a word if it's sitting between two 'a's." Anyone holding a sign for a word that isn't between two 'a's is asked to leave.
Now, the room only has people with legal change ideas. But there might still be too many people. Maybe one person wants to change just the first word, and another wants to change both.

Step 3: The "Worsening" Trick (The "Strict Judge")

This is the paper's secret sauce. The computer asks: "Is there a way to make this change idea worse?"

The Logic: If you have a candidate that changes nothing, that is "worse" than a candidate that changes something (if the rule says you must change it). If you have a candidate that changes the first word only, but you could have changed the first and second word, the "first only" candidate is "worse."
The Trick: The computer builds a special filter (a "worsener") that takes a "good" candidate and turns it into a "bad" one by removing a change.
- Analogy: Imagine the Strict Judge has a magic eraser. If a person in the room is holding a sign for a change, the Judge tries to erase it.
- If the Judge can erase a sign and the person still looks like a valid candidate, then the original person was "suboptimal" (they missed an opportunity to change something). They are kicked out.
- The only people who stay are the ones who cannot be made worse. These are the people who changed everything they were supposed to, in the best possible way.

Why This is a Big Deal

It's Short and Sweet: The mathematical formulas the authors use are much shorter and cleaner than the old "marker" methods. It's like writing a recipe with 3 clear steps instead of 20 confusing paragraphs.
It's Flexible: This same "Worsening Trick" works for all kinds of complicated rules:
- Multiple Rules: Changing b to p AND d to t at the same time.
- Preferences: "Change the first one you see" (Leftmost) or "Change the longest stretch you see" (Longest).
- Weights: If some changes cost more "energy" than others, this method handles that too.
It Works: The authors tested their new method against the old, established method (called foma). They found that the results were identical. The computers produced the exact same output, just with different internal numbering.

The "Spreading" Surprise

The paper also mentions a cool side effect regarding "spreading" rules (like how a vowel sound in a word can influence the vowels in a suffix).

Usually, rules check the input (what you typed).
But sometimes, you need to check the output (what you just created).
The authors show that by simply swapping the order of their steps, the "Worsening Trick" can handle this "spreading" behavior naturally, which is very useful for things like Finnish vowel harmony.

Summary

The paper introduces a new, elegant way to teach computers how to edit text. Instead of building a complex maze of markers, they generate all possibilities, filter out the illegal ones, and then use a "Worsening Trick" to eliminate any option that isn't the absolute best. It's a simpler, more powerful way to solve the same problems linguists have been facing for decades.

Technical Summary: Compiling Rewrite Rules to Finite-State Transducers with the Worsening Trick

Problem Statement
Finite-state transducers (FSTs) are fundamental for modeling string rewriting in computational linguistics, particularly for phonological and morphological rules of the form $A \to B / L \_ R$ . Here, strings from a regular language $A$ are replaced by $B$ within the context of regular languages $L$ and $R$ . Compiling such general rules into FSTs is computationally complex due to overlapping matches, multiple contexts, and the need to handle various preferences (e.g., leftmost, longest, or shortest matches). Traditional compilation methods, such as those by Kaplan and Kay or Karttunen, rely on intricate compositions involving auxiliary markers to constrain rewrite sites. These approaches often result in complex, non-uniform formulas that are difficult to extend to advanced features like parallel rewriting, arbitrary transductions, or weighted rules.

Methodology
The authors propose a compilation scheme based on the "worsening trick," a strategy previously applied to regular sets and transductions. The method operates in three transparent stages to compile a rule $A \to B / L \_ R$ :

Candidate Generation ( $T_{base}$ ): The system generates all possible rewrite candidates by bracketing potential transduction sites. This is achieved by constructing a base transducer that allows symbols from the input alphabet $\Sigma$ to pass through unchanged or to be replaced by strings from $B$ within brackets $< \dots >$ representing the transduction $A:B$ . Word boundaries are explicitly marked with # to treat edge contexts uniformly.
Context Restriction ( $L_{context}$ ): Candidates containing rewrite sites in illicit contexts are filtered out. Instead of using exponential formulas for multiple contexts, the authors employ a "dotted-position" technique (Yli-Jyrä and Koskenniemi). An auxiliary symbol · is used to mark a single rewrite site, and a language $K$ is constructed to represent strings where this marked position is surrounded by valid contexts ( $L$ and $R$ ). The intersection of valid contexts with the candidate set yields the set of legal, optional rewrites.
Preference Filtering (Worsening): To enforce obligatory rewriting and specific preferences (e.g., leftmost, longest), the system defines a "worsening" transducer ( $W$ ). This transducer maps a "better" candidate to a "worse" one by removing or shifting rewrite brackets (e.g., undoing a rewrite or shortening a span). The final transducer is constructed by filtering out any candidate that can be made strictly worse by applying $W$ . Mathematically, for a set of candidates $C$ and a worsener $W$ , the optimal set is $C \cap \neg \text{range}(C \circ W)$ .

This framework is implemented in PyFoma and supports:

Multiple Contexts: Handled via union in the dotted-position language.
Directed Rewriting: Preferences like leftmost, longest, or shortest are encoded by specific worsening transducers ( $W_{left}$ , $W_{long}$ , $W_{short}$ ).
Arbitrary Transductions: The input $T$ need not be a simple cross-product; it can be any FST.
Parallel Rewriting: Multiple rules are handled using indexed brackets, with context restriction and worsening applied per index.
Weights: The construction works within the tropical semiring, as worseners filter candidates without altering their assigned weights.
Epsilon Handling: A specific filter prevents consecutive empty bracket pairs to restrict epsilon insertions to single sites per boundary.

Key Contributions

Uniformity and Compactness: The paper presents a formulation where the compilation logic is expressed with substantially shorter and more uniform formulas compared to classical marker-heavy or multitape approaches.
Extensibility: The construction naturally extends to complex modalities (parallel rules, weights, markup, output-side context checking) without requiring new rule types or auxiliary machinery.
Implementation and Validation: The authors implemented the compiler in PyFoma. Validation was performed against the established C-based foma compiler using a collection of 31 grammars (427 rules) and an automated regression suite of 2,217 cases.
Equivalence: In all tested cases where the semantics coincide, the resulting transducers are structurally identical to those produced by foma (differing only in state numbering), confirming the correctness of the worsening-based approach.

Significance and Claims
The paper claims that the worsening trick provides a robust, algebraic alternative to procedural selection tasks in finite-state phonology. By generating a regular set of candidates and filtering them via a worsening relation, complex preference orders can be encoded declaratively within the regular calculus. The authors assert that this approach not only reproduces the established semantics of classical compilers but also simplifies the theoretical and practical extension of rewrite systems. The technique is presented not merely as a compilation tool but as a general finite-state design pattern for extracting preferred subsets of regular languages and relations (e.g., minimal or maximal representatives). The work reinforces the utility of the worsening trick beyond its previous applications in finite-state Optimality Theory, demonstrating its efficacy in handling the full spectrum of classical rewrite rule modalities.