The Data Complexity of the Syllogistic Fragments of English

Abstract

The syllogistic fragments of English (syllogistic FOEs) express syllogistic reasoning. We want to know how suitable they would be as front-end languages for ontology-based data access systems (OBDASs), front-ends that have been proposed to rely on controlled fragments of natural language. In particular, we want to know how well syllogistic FOE-based data management tasks for OBDASs scale to data. This, we argue, can be achieved by studying the semantic complexity of the syllogistic FOEs and by considering those computational properties that depend on the size of the data alone.