COMPUTERLINGUISTIK

Herzlich Willkommen

auf den Seiten der Computerlinguistik. Wir sind neben Linguistik und Informationswissenschaft eine Abteilung des Instituts für Sprache und Information und an der Philosophischen Fakultät der Heinrich-Heine-Universität Düsseldorf angesiedelt. Die Abteilung hat einen Lehrstuhl für Computerlinguistik, der seit 2011 von Prof. Dr. Laura Kallmeyer besetzt ist. Daneben hat Dr. Wiebke Petersen eine Junior-Professur für Mathematische Linguistik und es gibt etwa 15 weitere wissenschaftliche Mitarbeiter in Forschung und Lehre. In der Lehre bedienen wir die Bachelor- und Masterstudiengänge Linguistik sowie Informationswissenschaft und Sprachtechnologie. Promotion ist ebenfalls möglich. In der Forschung sind wir mit 4 Projekten in den SFB 991 eingebunden und haben daneben noch 4 weitere Projekte. Unser thematischer Schwerpunkt in Forschung und Lehre umfasst schwach kontextsensitive Grammatikformalismen, Finite-State-Techniken, statistische maschinelle Übersetzung und Wissensrepräsentation auf Basis von Frames.

Aktuelles

Vortragsankündigung

Christian Wurm (HHU)
17.07.2014, 14.30 Uhr in Raum 23.21.02.52

Permutation Closure and Regular Language Models: On some open problems in formal language theory and mathematical logic

In this talk, I want to present solutions to two rather longstanding open problems with high relevance for computational linguistics, which in turn allow us to answer some other less prominent open questions. Apart from the presentation of these results, this talk is intended to be a tutorial for tools and techniques in formal language theory, which are introduced as I outline the main proofs. 
 
Problem 1 is the following: what is the smallest class of languages, such that for each language L in the class CFL/TAL/MCFL, it contains in addition to L itself the language of all permutations of all words in L? I prove (among other) the following: any permutation language of an MCFL is still an MCFL; actually, this result can still be strenghtened in various ways. This vastly generalizes previous results on the MIX-language (Salvati, 2011), and gives a fully satisfying and very surprising answer to a problem which is as old as MCFG themselves (Seki et al.1991). 
 
Problem 2 is regular language completeness of the Lambek calculus with product (Lambek 1955; we can even add additive disjunction). Ever since Pentus (1995) proved completeness of its language-theoretic semantics (which itself had been a prominent open problem for 40 years), it has been the most natural and important question regarding the semantics of Lambek's calculus whether this completeness result can be strengthened to also hold for interpretations into the regular languages only. I prove the conjecture to be correct, by the way providing a simpler proof for Pentus' theorem. This in turn allows us to positively answer some open decision problems for regular languages.

Video-Interview mit Laura Kallmeyer

Videoplayer