Inari Listenmaa
Chalmers University of Technology, Gothenburg, Sweden
Koen Clæssen
Chalmers University of Technology, Gothenburg, Sweden
Download article
Published in: Proceedings of the Workshop on “Constraint Grammar - methods, tools and applications” at NODALIDA 2015, May 11-13, 2015, Institute of the Lithuanian Language, Vilnius, Lithuania
Linköping Electronic Conference Proceedings 113:4, p. 23-27
NEALT Proceedings Series 24:4, p. 23-27
Published: 2015-06-17
ISBN: 978-91-7519-037-2
ISSN: 1650-3686 (print), 1650-3740 (online)
We represent Constraint Grammar (CG) as a Boolean satisfiability (SAT) problem. Encoding CG in logic brings some new features to the grammars. The rules are interpreted in a more declarative way, which makes it possible to abstract away from details such as cautious context and ordering. A rule is allowed to affect its context words, which makes the number of the rules in a grammar potentially smaller. Ordering can be preserved or discarded; in the latter case, we solve eventual rule conflicts by finding a solution that discards the least number of rule applications. We test our implementation by parsing texts in the order of 10,000s–100,000s words, using grammars with hundreds of rules.
Eckhard Bick. 2013. ML-Tuned Constraint Grammars. In Proceedings of the 27th Pacific Asia Conference on Language, Information and Computation.
Niklas E´en and Niklas S¨orensson. 2004. An Extensible SAT-solver. In Enrico Giunchiglia and Armando Tacchella, editors, Theory and Applications of Satisfiability Testing, volume 2919 of Lecture Notes in Computer Science. Springer Berlin Heidelberg.
Martin Eineborg and Nikolaj Lindberg. 1998. Induction of constraint grammar-rules using progol. In David Page, editor, Inductive Logic Programming, volume 1446 of Lecture Notes in Computer Science. Springer Berlin Heidelberg.
Fred Karlsson, Atro Voutilainen, Juha Heikkil¨a, and Arto Anttila. 1995. Constraint Grammar: a language-independent system for parsing unrestricted text, volume 4. Walter de Gruyter.
Kimmo Koskenniemi. 1990. Finite-state parsing and disambiguation. In Proceedings of the 13th Conference on Computational Linguistics - Volume 2, COLING ’90. Association for Computational Linguistics.
Torbjörn Lager and Joakim Nivre. 2001. Part of speech tagging from a logical point of view. In Logical Aspects of Computational Linguistics, 4th International Conference, LACL 2001, Le Croisic, France, June 27-29, 2001, Proceedings.
Torbjörn Lager. 1998. Logic for part of speech tagging and shallow parsing. In Proceedings of the 11th Nordic Conference on Computational Linguistics.
João Marques-Silva. 2010. Boolean Satisfiability Solving: Past, Present & Future. Presentation given at the Microsoft Research International Workshop on Tractability, Cambridge, UK, July 5–6.
Andrei Sfrent. 2014. Machine Learning of Rules for Part of Speech Tagging. Master’s thesis, Imperial College London, United Kingdom.
