January 12, 2010

Thread automata, dependency structures for NLP and the project

The abstract :

Several constraints have been proposed that restrict the structures for syntactic parsing such as projectivity, non-projectivity, planarity, well-nestedness, gap and edge degrees. These classes can generally be characterized by the dependency structure characteristics themselves rather by grammar formalism that generate these structures. Thread automata are a powerful but simple automata which are an extension of embedded push-down automata. This automata exhibits a wide range of parsing strategies for the so called mildly context sensitive (MCS) formalism. These formalism are considered to be a little more powerful than context free but less powerful than context sensitive in respect of parsing and semi-linear issues. In this project, we aim to connect the properties of dependency structures with the functionality of thread automata. If such a connection is established, it will increase the expressiveness and reduce the complexity of syntactic parsing of natural languages with free form word order.

Most natural languages seem to be parsed by creating dependencies in the tokens as they are parsed. Hence some constraints have been proposed for these dependency structures. The project deals with contemplating and validating the applicability of these constraints, if any, to thread automata.