More fragments of language. (Q867399)

The paper deals with the so-called semantic complexity of fragments of natural language. By semantic complexity the authors understand the `computational complexity of deciding whether a given set of natural-language sentences represents a logically possible situation'. Natural language sentences are translated into first-order predicate logic formulas according to a context-free grammar (plus additional movement rules) defined for a given fragment. A set of sentences \textit{E} is said to entail a sentence \textit{e} if the respective FOL formulas corresponding to \textit{E} entail the formula corresponding to \textit{e}. Likewise, a set of sentences \textit{E} is said to be satisfiable if the respective set of formulas is satisfiable. The presented complexity proofs make use of the duality between entailment and satisfiability notions. Several families of languages are considered, namely the fragment Cop of traditional syllogistic, fragment TV+DTV with transitive and ditransitive verbs, fragment Rel with relative clauses `who' and `which' generated by means of wh-movement rules, and fragments RA and GA dealing with anaphora. The former is a fragment in which anaphoric pronouns refer to the closest allowed antecedent, the latter handles anaphoric ambiguities by co-indexing antecedents to anaphoric pronouns. The main result consists in the complexity proofs of the respective fragments as follows: Cop, Cop+TV+DTV, fragments without relative clauses and anaphora are in PTIME; Cop+Rel is NP-complete; Cop+Rel+TV is EXPTIME-complete; Cop+Rel+DTV, Cop+Rel+TV+RA are NEXPTIME-complete; Cop+Rel+TV+GA and Cop+Rel+TV+DTV+RA are undecidable.