David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Logic, Language and Information 13 (4):457-470 (2004)
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.
|Keywords||Complexity theory monadic second-order logic query treebank|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
[author unknown] (1972). Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic. Journal of Symbolic Logic 37 (3):619-620.
[author unknown] (1972). Tree Acceptors and Some of Their Applications. Journal of Symbolic Logic 37 (3):619-619.
Citations of this work BETA
No citations found.
Similar books and articles
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer
Marcelo Finger & Dov M. Gabbay (1992). Adding a Temporal Dimension to a Logic System. Journal of Logic, Language and Information 1 (3):203-233.
Richard Moot & Mario Piazza (2001). Linguistic Applications of First Order Intuitionistic Linear Logic. Journal of Logic, Language and Information 10 (2):211-232.
Yuri Gurevich & Saharon Shelah (1983). Rabin's Uniformization Problem. Journal of Symbolic Logic 48 (4):1105-1119.
Shmuel Lifsches & Saharon Shelah (1997). Peano Arithmetic May Not Be Interpretable in the Monadic Theory of Linear Orders. Journal of Symbolic Logic 62 (3):848-872.
Michael Benedikt & H. Jerome Keisler (2003). Definability with a Predicate for a Semi-Linear Set. Journal of Symbolic Logic 68 (1):319-351.
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Lauri Hella (1996). Logical Hierarchies in PTIME. Information And Computation 129 (1):1--19.
Catherine Lai & Steven Bird (2010). Querying Linguistic Trees. Journal of Logic, Language and Information 19 (1):53-73.
Added to index2009-01-28
Total downloads8 ( #266,862 of 1,725,051 )
Recent downloads (6 months)7 ( #93,209 of 1,725,051 )
How can I increase my downloads?