Switch to: References

Add citations

You must login to add citations.
  1. On the computational complexity of the numerically definite syllogistic and related logics.Ian Pratt-Hartmann - 2008 - Bulletin of Symbolic Logic 14 (1):1-28.
    The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Fragments of language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.
    By a fragment of a natural language we mean a subset of thatlanguage equipped with semantics which translate its sentences intosome formal system such as first-order logic. The familiar conceptsof satisfiability and entailment can be defined for anysuch fragment in a natural way. The question therefore arises, for anygiven fragment of a natural language, as to the computational complexityof determining satisfiability and entailment within that fragment. Wepresent a series of fragments of English for which the satisfiabilityproblem is polynomial, NP-complete, EXPTIME-complete,NEXPTIME-complete (...)
    Download  
     
    Export citation  
     
    Bookmark   18 citations  
  • More Fragments of Language.Ian Pratt-Hartmann & Allan Third - 2006 - Notre Dame Journal of Formal Logic 47 (2):151-177.
    By a fragment of a natural language, we understand a collection of sentences forming a naturally delineated subset of that language and equipped with a semantics commanding the general assent of its native speakers. By the semantic complexity of such a fragment, we understand the computational complexity of deciding whether any given set of sentences in that fragment represents a logically possible situation. In earlier papers by the first author, the semantic complexity of various fragments of English involving at most (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations