TY - GEN
T1 - Querying the fragments of english
AU - Thorne, Camilo
PY - 2011
Y1 - 2011
N2 - Controlled languages are fragments of natural languages stripped clean of lexical, structural and semantic ambiguity. They have been proposed as a means for providing natural language front-ends to access structured knowledge sources, given that they compositionally and deterministically translate into the (logic-based) formalisms such back-end systems support. An important issue that arises in this context is the semantic data complexity of accessing such information (i.e., the computational complexity of querying measured w.r.t. the number of instances declared in the back-end knowledge base or database). In this paper we study the semantic data complexity of a distinguished family of context-free controlled fragments, viz., Pratt and Third's fragments of English. In doing so, we pinpoint those fragments for which the reasoning problems are tractable (in PTime) or intractable (NP-hard or coNP-hard).
AB - Controlled languages are fragments of natural languages stripped clean of lexical, structural and semantic ambiguity. They have been proposed as a means for providing natural language front-ends to access structured knowledge sources, given that they compositionally and deterministically translate into the (logic-based) formalisms such back-end systems support. An important issue that arises in this context is the semantic data complexity of accessing such information (i.e., the computational complexity of querying measured w.r.t. the number of instances declared in the back-end knowledge base or database). In this paper we study the semantic data complexity of a distinguished family of context-free controlled fragments, viz., Pratt and Third's fragments of English. In doing so, we pinpoint those fragments for which the reasoning problems are tractable (in PTime) or intractable (NP-hard or coNP-hard).
KW - computational semantics
KW - Controlled language interfaces
KW - knowledge base query answering and satisfiability
KW - resolution proof procedures
KW - semantic data complexity
UR - http://www.scopus.com/inward/record.url?scp=85037735972&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-20920-8_25
DO - 10.1007/978-3-642-20920-8_25
M3 - Contribución a la conferencia
AN - SCOPUS:85037735972
SN - 9783642209192
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 257
EP - 271
BT - Logic, Language, Information and Computation - 18th International Workshop, WoLLIC 2011, Proceedings
PB - Springer Verlag
ER -