New Compilation Method for Rewrite Rules in Finite-State Transducers
Researchers have proposed a compact compilation scheme for converting phonological and morphological rewrite rules into finite-state transducers (FSTs) using a technique called the 'worsening trick.' The method generates all legal rewrite candidates for a given input and filters out those that are strictly worse than another candidate, avoiding the complex auxiliary marker compositions used in traditional approaches. The work, implemented in the PyFoma toolkit, offers a simpler and more extensible alternative to established methods while producing equivalent results.
Finite-state transducers are widely used in computational linguistics and NLP to model string rewriting, particularly for phonological and morphological rules of the form A → B / L _ R, where all components can be arbitrary regular languages. Compiling such rules is technically challenging due to overlapping matches and context constraints, and prior methods by Kaplan and Kay or Karttunen required elaborate transducer compositions involving auxiliary markers. The new approach, dubbed the 'worsening trick,' sidesteps this complexity by first generating all legal rewrite candidates and then filtering any candidate that is dominated by a better one for the same input. The scheme has been integrated as the built-in rewrite compiler in PyFoma and supports multiple contexts, arbitrary transductions, markup, directed rewriting, weights, and parallel rewriting. Validation against the established foma tool on a large collection of rewrite grammars and an automated regression suite confirmed that the resulting transducers match exactly, differing only in state numbering. The resulting formulas are described as shorter and more uniform than those of earlier approaches, and the authors argue the design is easier to extend. The paper is accepted to the tool track of CIAA 2026.
What's missing
The paper does not discuss computational complexity or runtime performance comparisons between the worsening trick and traditional methods (e.g., Kaplan-Kay or Karttunen) on large-scale grammars, nor does it address potential failure cases or scalability limits for very large or highly ambiguous rule sets.
What different sources said
- arXiv cs.CLCenter
Compiling Rewrite Rules to Finite-State Transducers with the Worsening Trick
Related
Gut Bacteria Enzyme Found to Break Down Heat-Processed Food Compounds, Producing Novel Biogenic Amines
Researchers have discovered that an enzyme in common gut bacteria can degrade N-epsilon-carboxymethyllysine (CML), a compound formed during thermal food processing, producing previously unknown biogenic amines. The enzyme, ornithine decarboxylase SpeC from enterobacteria, acts on CML and related modified lysine derivatives through a low-level 'underground' catalytic activity. This finding suggests a previously unrecognized communication axis between thermally processed dietary compounds and gut microbial physiology, with potential implications for host health.
Full-Length Gene Sequencing Reveals Two Distinct Bacterial Communities in Black-Legged Ticks Expanding Into Canada
Researchers used Oxford Nanopore full-length 16S rRNA gene sequencing to characterize the microbiome of Ixodes scapularis black-legged ticks collected in Nova Scotia, Canada, distinguishing between tick-adapted bacteria and environmentally acquired bacteria. The study comes as I. scapularis — the primary vector of Lyme disease — is rapidly expanding northward into Canada due to climate change. The findings suggest that environmentally derived bacteria in tick microbiomes are not mere contamination, which has implications for how tick microbiome data is collected and interpreted across surveillance studies.
Study Identifies Metabolic Link Between Cell Envelope Stress and Biofilm Formation in Bacteria
Researchers have discovered that the metabolite acetyl-CoA directly inhibits enzymes that degrade the bacterial signaling molecule c-di-GMP, connecting cell envelope biosynthesis stress to biofilm formation in Pseudomonas aeruginosa. The study found that sub-inhibitory concentrations of antibiotics targeting early peptidoglycan biosynthesis — but not other antibiotic classes — elevate c-di-GMP levels by reducing phosphodiesterase activity, with acetyl-CoA competing for the enzyme active site. Because the relevant enzyme domain is broadly conserved across bacterial species, this checkpoint mechanism may be widespread and could have implications for understanding antibiotic-induced biofilm responses.