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

• URL: http://arxiv.org/abs/2606.10059v1
• Date: Mon, 08 Jun 2026 18:36:39 GMT
• Title: Compiling Rewrite Rules to Finite-State Transducers with the Worsening Trick
• Abstract summary: This paper presents a compact compilation scheme based on the "worsening trick"<n>It generates all legal rewrite candidates, then filter candidates that are worse than another candidate for the same input.<n>The resulting formulas are short and uniform, and where semantics coincide, they reproduce the same rule transducers as earlier approaches.
• Score: 9.436197391132227
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finite-state transducers (FSTs) are essential for modeling string rewriting in computational linguistics and natural language processing (NLP), particularly for phonological and morphological rewrite rules. Compiling general rewrite rules of the form $A \to B / L \, \_ \, R$, where $A$, $B$, $L$, and $R$ are arbitrary regular languages, is complex due to overlapping matches and context constraints. Traditional methods, such as those by Kaplan and Kay or Karttunen, rely on intricate transducer compositions with auxiliary markers. This paper presents a compact compilation scheme based on the "worsening trick'': generate all legal rewrite candidates, then filter candidates that are worse than another candidate for the same input. Implemented as the built-in rewrite compiler in PyFoma, the construction supports multiple contexts, arbitrary transductions, markup, directed rewriting, weights, and parallel rewriting. The resulting formulas are short and uniform, and where semantics coincide, they reproduce the same rule transducers as earlier approaches while remaining easier to extend. The implementation has been validated against foma on both a substantial collection of rewrite grammars and an automated regression suite covering the major rewrite modalities, with the resulting transducers matching exactly apart from state numbering.

Related papers

• Alternative UX Extensions and Their Trade-offs for Code Completion in Pharo [0.13381749415517016]
  Complishon is Pharo's context-aware code completion engine.<n>This paper presents four extensions that address these limits.<n>For each extension, we describe the implementation, discuss alternative designs, and explain the trade-offs involved.
  arXiv  Detail & Related papers  (2026-07-27T10:42:53Z)
• Weave of Formal Thought [51.56484100374058]
  We introduce Weave of Formal Thought (WoFT), a paradigm uniting rigorous syntactic validation with learned structural representations.<n>We present a latent-variable fine-tuning method training the language model to interleave non-terminal grammar symbols directly into generation.<n>For Python, fine-tuning StarCoder2-3B with our RWS objective reduces per-token cross-entropy by 14.3% relative to a text-only SFT baseline.
  arXiv  Detail & Related papers  (2026-06-24T15:58:11Z)
• Towards Human-Like Interactive Speech Recognition With Agentic Correction and Semantic Evaluation [53.844308305341166]
  We propose textbfAgentic ASR, a closed-loop framework that combines a single-pass ASR front-end with semantic correction, intent routing, and reasoning-based editing.<n> Experiments on multilingual, named-entity-intensive, and code-switching benchmarks show that iterative interaction consistently reduces semantic errors.
  arXiv  Detail & Related papers  (2026-05-28T06:23:31Z)
• Prefix Parsing is Just Parsing [53.010152712125766]
  Prefix parsing asks whether an input prefix can be extended to a complete string generated by a given grammar.<n>We introduce the prefix grammar transformation, an efficient reduction of prefix parsing to ordinary parsing.<n>We also present a strategy-based on algorithmic differentiation-for computing the next-token weight vector.
  arXiv  Detail & Related papers  (2026-04-23T01:20:40Z)
• CASHG: Context-Aware Stylized Online Handwriting Generation [12.580543720353043]
  We propose CASHG, a context-aware stylized online handwriting generator.<n>CASHG explicitly models inter-character connectivity for style-consistent sentence-level trajectory synthesis.<n>We introduce Connectivity and Spacing Metrics (CSM), a boundary-aware evaluation suite that quantifies cursive connectivity and spacing similarity.
  arXiv  Detail & Related papers  (2026-04-02T14:32:31Z)
• RewriteNets: End-to-End Trainable String-Rewriting for Generative Sequence Modeling [0.0]
  We propose RewriteNets, a novel neural architecture built on explicit, parallel string rewriting.<n>We evaluate RewriteNets on algorithmic, compositional, and string manipulation tasks, comparing them against strong LSTM and Transformer baselines.<n>Results show that RewriteNets excel at tasks requiring systematic generalization and are more efficient than Transformers.
  arXiv  Detail & Related papers  (2026-01-10T19:59:37Z)
• Neuro-Symbolic Query Compiler [57.78201019000895]
  This paper presents QCompiler, a neuro-symbolic framework inspired by linguistic grammar rules and compiler design, to bridge this gap.<n>It theoretically designs a minimal yet sufficient Backus-Naur Form (BNF) grammar $G[q]$ to formalize complex queries.<n>The atomicity of the sub-queries in the leaf ensures more precise document retrieval and response generation, significantly improving the RAG system's ability to address complex queries.
  arXiv  Detail & Related papers  (2025-05-17T09:36:03Z)
• Pattern Matching in AI Compilers and its Formalization (Extended Version) [5.025922465392978]
  PyPM is a Python-based domain specific language for building rewrite-based optimization passes on machine learning computation graphs.<n>We present our work on building PyPM, as well as formalizing and distilling and this complexity to an understandable mathematical core.
  arXiv  Detail & Related papers  (2024-12-18T00:29:09Z)
• Adaptive Query Rewriting: Aligning Rewriters through Marginal Probability of Conversational Answers [66.55612528039894]
  AdaQR is a framework for training query rewriting models with limited rewrite annotations from seed datasets and completely no passage label. A novel approach is proposed to assess retriever's preference for these candidates by the probability of answers conditioned on the conversational query.
  arXiv  Detail & Related papers  (2024-06-16T16:09:05Z)
• Hierarchical Context Tagging for Utterance Rewriting [51.251400047377324]
  Methods that tag rather than linearly generate sequences have proven stronger in both in- and out-of-domain rewriting settings. We propose a hierarchical context tagger that mitigates this issue by predicting slotted rules. Experiments on several benchmarks show that HCT can outperform state-of-the-art rewriting systems by 2 BLEU points.
  arXiv  Detail & Related papers  (2022-06-22T17:09:34Z)
• ASSET: A Dataset for Tuning and Evaluation of Sentence Simplification Models with Multiple Rewriting Transformations [97.27005783856285]
  This paper introduces ASSET, a new dataset for assessing sentence simplification in English. We show that simplifications in ASSET are better at capturing characteristics of simplicity when compared to other standard evaluation datasets for the task.
  arXiv  Detail & Related papers  (2020-05-01T16:44:54Z)
• Traduction des Grammaires Cat\'egorielles de Lambek dans les Grammaires Cat\'egorielles Abstraites [0.0]
  This internship report is to demonstrate that every Lambek Grammar can be, not entirely but efficiently, expressed in Abstract Categorial Grammars (ACG) The main idea is to transform the type rewriting system of LGs into that of Context-Free Grammars (CFG) by erasing introduction and elimination rules and generating enough axioms so that the cut rule suffices. Although the underlying algorithm was not fully implemented, this proof provides another argument in favour of the relevance of ACGs in Natural Language Processing.
  arXiv  Detail & Related papers  (2020-01-23T18:23:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.