Tractability and Intractability of Controlled Languages for Data Access

Studia Logica 100 (4):787-813 (2012)
  Copy   BIBTEX


In this paper we study the semantic data complexity of several controlled fragments of English designed for natural language front-ends to OWL (Web Ontology Language) and description logic ontology-based systems. Controlled languages are fragments of natural languages, obtained by restricting natural language syntax, vocabulary and semantics with the goal of eliminating ambiguity. Semantic complexity arises from the formal logic modelling of meaning in natural language and fragments thereof. It can be characterized as the computational complexity of the reasoning problems associated to their semantic representations. Data complexity (the complexity of answering a question over an ontology, stated in terms of the data items stored therein), in particular, provides a measure of the scalability of controlled languages to ontologies, since tractable data complexity implies scalability of data access. We present maximal tractable controlled languages and minimal intractable controlled languages



    Upload a copy of this work     Papers currently archived: 93,642

External links

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

Through your library


Added to PP

9 (#449,242)

6 months
38 (#406,104)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Generalized quantifiers and natural language.John Barwise & Robin Cooper - 1981 - Linguistics and Philosophy 4 (2):159--219.
Generalized Quantifiers and Natural Language.Jon Barwise - 1980 - Linguistics and Philosophy 4:159.
Universal grammar.Richard Montague - 1970 - Theoria 36 (3):373--398.
More Fragments of Language.Ian Pratt-Hartmann & Allan Third - 2006 - Notre Dame Journal of Formal Logic 47 (2):151-177.

Add more references