Article | 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 | Constraint Grammar as a SAT problem
Göm menyn

Title:
Constraint Grammar as a SAT problem
Author:
Inari Listenmaa: Chalmers University of Technology, Gothenburg, Sweden Koen Clæssen: Chalmers University of Technology, Gothenburg, Sweden
Download:
Full text (pdf)
Year:
2015
Conference:
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
Issue:
113
Article no.:
004
Pages:
23-27
No. of pages:
5
Publication type:
Abstract and Fulltext
Published:
2015-06-17
ISBN:
978-91-7519-037-2
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Series:
NEALT Proceedings Series
Publisher:
Linköping University Electronic Press, Linköpings universitet


Export in BibTex, RIS or text

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.

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

Author:
Inari Listenmaa, Koen Clæssen
Title:
Constraint Grammar as a SAT problem
References:

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.

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

Author:
Inari Listenmaa, Koen Clæssen
Title:
Constraint Grammar as a SAT problem
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment


Responsible for this page: Peter Berkesand
Last updated: 2017-02-21