Querying linguistic treebanks with monadic second-order logic in linear time

Journal of Logic, Language and Information 13 (4):457-470 (2004)
  Copy   BIBTEX


In recent years large amounts of electronic texts have become available. While the first of these corpora had only a low level of annotation, the more recent ones are annotated with refined syntactic information. To make these rich annotations accessible for linguists, the development of query systems has become an important goal. One of the main difficulties in this task consists in the choice of the right query language, a language which at the same time should be powerful enough to let users formulate the queries they want and which should be efficiently evaluable to keep query response times short. There is a widespread belief that such a query language does not exist. It is therefore the aim of this paper to show that there is indeed a powerful query language that can be efficiently evaluated. We propose the use of monadic second-order logic as a query language. We show that a query in this language can be evaluated in linear time in the size of a tree in the corpus. We also provide examples of complicated linguistic queries expressed in monadic second-order logic thereby demonstrating the high expressive power of the language.



    Upload a copy of this work     Papers currently archived: 92,075

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
Rabin's uniformization problem.Yuri Gurevich & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (4):1105-1119.
Linguistic applications of first order intuitionistic linear logic.Richard Moot & Mario Piazza - 2001 - Journal of Logic, Language and Information 10 (2):211-232.
Adding a temporal dimension to a logic system.Marcelo Finger & Dov M. Gabbay - 1992 - Journal of Logic, Language and Information 1 (3):203-233.
Querying linguistic trees.Catherine Lai & Steven Bird - 2010 - Journal of Logic, Language and Information 19 (1):53-73.


Added to PP

40 (#399,111)

6 months
8 (#364,101)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations