Paper: String Transformation Learning

ACL ID P97-1057
Title String Transformation Learning
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1997

String transformation systems have been introduced in (Brill, 1995) and have sev- eral applications in natural language pro- cessing. In this work we consider the com- putational problem of automatically learn- ing from a given corpus the set of transfor- mations presenting the best evidence. We introduce an original data structure and efficient algorithms that learn some fam- ilies of transformations that are relevant for part-of-speech tagging and phonologi- cal rule systems. We also show that the same learning problem becomes NP-hard in cases of an unbounded use of don't care symbols in a transformation.