Squeezing theory into practice: automata in natural language processing
- Speaker(s)
- Aleksander Zabłocki
- Affiliation
- Uniwersytet Warszawski
- Date
- June 19, 2013, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
I will sketch some aspects of using automata in natural language
processing: more precisely, in efficient applying a set of
search-replace rules for richly annotated text. Although this might seem
trivial (build-determinize-compose-run), our practical applications require considering how to:
- avoid explosion of states,
- determinize at all,
- deal with ambiguity in the input, and
- more generally, choose between word and tree automata (as our input lies somehow between the two).
Our motivation is practical: we do not fight for decidability and even not much for asymptotics, but rather for good constants, under some particular assumptions.
- avoid explosion of states,
- determinize at all,
- deal with ambiguity in the input, and
- more generally, choose between word and tree automata (as our input lies somehow between the two).
Our motivation is practical: we do not fight for decidability and even not much for asymptotics, but rather for good constants, under some particular assumptions.