1996/06/23 by Lauri Karttunen, Karttunen, Lauri · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Computation and Language (cs.CL) #DNA and Biological Computing #FOS: Computer and information sciences #Natural Language Processing Techniques #cmp-lg #cs.CL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cmp-lg/9606029
To appear in the Proceedings of ACL-96
arxiv created 1996/06/23 · openalex publication_date 1996/06/23 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper introduces to the finite-state calculus a family of directed replace operators. In contrast to the simple replace expression, UPPER -> LOWER, defined in Karttunen (ACL-95), the new directed version, UPPER @-> LOWER, yields an unambiguous transducer if the lower language consists of a single string. It transduces the input string from left to right, making only the longest possible replacement at each point. A new type of replacement expression, UPPER @-> PREFIX ... SUFFIX, yields a transducer that inserts text around strings that are instances of UPPER. The symbol ... denotes the matching part of the input which itself remains unchanged. PREFIX and SUFFIX are regular expressions describing the insertions. Expressions of the type UPPER @-> PREFIX ... SUFFIX may be used to compose a deterministic parser for a ``local grammar'' in the sense of Gross (1989). Other useful applications of directed replacement include tokenization and filtering of text streams.