Transducers from Rewrite Rules with Backreferences

Context sensitive rewrite rules have been widely used in several areas of natural language processing, including syntax, morphology, phonology and speech processing. Kaplan and Kay, Karttunen, and Mohri & Sproat have given various algorithms to compile such rewrite rules into finite-state transducers. The present paper extends this work by allowing a limited form of backreferencing in such rules. The explicit use of backreferencing leads to more elegant and general solutions.

• Publication year

  1999

• Venue

  Conference of the European Chapter of the Association for Computational Linguistics

• Publication date

  1999-04-15

• Fields of study

  Linguistics, Computer Science

• Identifiers
  DOI 10.3115/977035.977053arXiv cs/9904008
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An Extendible Regular Expression Compiler for Finite-State Approaches in Natural Language Processing

  1999cited by this paper
• The Proper Treatment of Optimality in Computational Phonology

  1998cited by this paper
• Mastering Regular Expressions

  1997influential reference
• Mona & Fido: The Logic-Automaton Connection in Practice

  1997cited by this paper
• Finite-State Language Processing

  1997cited by this paper
• Partial parsing via finite-state cascades

  1996cited by this paper
• An Efficient Compiler for Weighted Rewrite Rules

  1996influential reference
• Regular expressions for language engineering

  1996cited by this paper
• 34th Annual Meeting of the Association for Computational Linguistics

  1996influential reference
• An Eecient Compiler for Weighted Rewrite Rules

  1996influential reference
• Directed Replacement

  1996influential reference
• The Replace Operator

  1995cited by this paper
• Regular Models of Phonological Rule Systems

  1994influential reference
• Rapid Incremental Parsing with Repair

  1990cited by this paper
• Formal Aspects of Phonological Description

  1972cited by this paper
• MITSUBISHI ELECTRIC RESEARCH LABORATORIES CAMBRIDGE RESEARCH CENTER Deterministic Part-Of-Speech Tagging with Finite State Transducers

  year unknowncited by this paper

• OCR and post-correction of historical newspapers and journals

  2020cites this paper
• A Brief Survey of Related Work

  2017cites this paper
• Stochastic Contextual Edit Distance and Probabilistic FSTs

  2014cites this paper
• Automatic Detection and Repair of Input Validation and Sanitization Bugs

  2014cites this paper
• A Novel Algorithm Combining Finite State Method and Genetic Algorithm for Solving Crude Oil Scheduling Problem

  2014influential citation
• Using HFST for Creating Computational Linguistic Applications

  2013cites this paper
• This Document is Work in Progress Corrections and Suggestions Are Welcome

  2013cites this paper
• Implementation of Replace Rules Using Preference Operator

  2012cites this paper
• Syllabification of Middle Dutch

  2012cites this paper
• Automatic Verification of String Manipulating

  2010cites this paper
• Automatic verification of string manipulating programs

  2010cites this paper
• AdAPTATION Of LANguAgE RESOuRcES ANd TEcHNOLOgy TO NEW dOmAINS ( AdaptLRTtoNd )

  2009cites this paper
• International Journal INFORMATION THEORIES & APPLICATIONS

  2009cites this paper
• Mix and Match Replacement Rules

  2009cites this paper
• Finite-state Machine Construction Methods and Algorithms for Phonology and Morphology

  2009cites this paper
• Transducers from Parallel Replace Rules and Modes with Generalized Lenient Composition

  2008cites this paper
• Finite-State Methods and Natural Language Processing

  2008cites this paper
• Symbolic String Verification: An Automata-Based Approach

  2008cites this paper
• Applications of Diamonded Double Negation

  2008cites this paper
• A New Method for Compiling Parallel Replacement Rules

  2007cites this paper
• String Analysis

  2007cites this paper
• Efficient dictionary-based text rewriting using subsequential transducers†

  2007cites this paper
• Workshop on Software Evaluating and Integrating Treebank Parsers on a Biomedical Corpus Workshop Program Session 3: Morphology and Language Modeling Texttree Construction for Parser and Treebank Development

  2005cites this paper
• Preference-Driven Bimachine Compilation. An Application to TTS Text Normalisation

  2005cites this paper
• XFST2FSA: Comparing Two Finite-State Toolboxes

  2005cites this paper
• A Bimachine Compiler for Ranked Tagging Rules

  2004cites this paper
• High Performance Part-of-Speech Tagging of Bulgarian

  2004cites this paper
• Computational Implementation of Non-Concatenative Morphology

  2004cites this paper
• Logical specification of finite-state transductions for natural language processing

  2004cites this paper
• Finite state methods in natural language processing

  2003cites this paper
• Finite state methods for hyphenation

  2003cites this paper
• Quadratic Alignment Constraints and Finite State Optimality Theory

  2003cites this paper
• Logical specification of regular relations for NLP

  2003cites this paper
• Special issue: finite state methods in natural language processing

  2003cites this paper
• Some Theoretical and Practical Results in Context-Sensitive and Adaptive Parsing

  2002cites this paper
• Parameter Estimation for Probabilistic Finite-State Transducers

  2002cites this paper
• Some Theoretical and Practical Results in Context-Sensitive and Adaptive Parsing

  2002cites this paper
• Learning Computational Grammars

  2001cites this paper
• Expectation Semirings: Flexible EM for Learning Finite-State Transducers

  2001cites this paper
• Finite State Transducers with Predicates and Identities

  2001cites this paper
• A Finite State and Data-Oriented Method for Grapheme to Phoneme Conversion

  2000cites this paper
• Proceedings of the Fifth Workshop of the ACL Special Interest Group in Computational Phonology

  2000cites this paper
• Approximation and Exactness in Finite State Optimality Theory

  2000cites this paper
• Treatment of epsilon moves in subset construction

  2000cites this paper
• An Extendible Regular Expression Compiler for Finite-State Approaches in Natural Language Processing

  1999cites this paper
• P-model Alternative to the T-model

  1998cites this paper
• One-Letter Automata : How to Reduce k Tapes to One Hristo Ganchev and

  year unknowncites this paper