Research project The aim of the project is a detailed analysis of the relationship between the expressivity of the grammar and the computational complexity of the syntactic analysis.
Computer systems that in one way or another have to deal with natural languages, languages such as Swedish or English, are becoming increasingly prevalent. The first step, when a system is supposed to handle a sentence in English is almost always a syntactic analysis, i.e., the system tries to determine which parts of the sentence are the main verb, the subject, the objects, etc. How hard and how time consuming this analysis is depends on how complicated the underlying grammar is. The main tools employed in the project are classical methods from theoretical computer science, such as formal language theory and complexity analysis. Once this analysis is finished, the acquired knowledge will be put to use in the development of new methods for syntactic analysis. Such methods will be implemented and tested within the project.
