资源论文Classification Transfer for Qualitative Reasoning Problems

Classification Transfer for Qualitative Reasoning Problems

2019-11-05 | |  51 |   40 |   0
Abstract We study formalisms for temporal and spatial reasoning in the modern, algebraic and modeltheoretic, context of infinite-domain Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses can be solved using existing results via the powerful use of primitive positive (pp) interpretations and pphomotopy. We demonstrate the methodology by giving a full complexity classification of all constraint languages that are first-order definable in Allen’s Interval Algebra and contain the basic relations (s) and (f). In the case of the Rectangle Algebra we answer in the affirmative the old open question as to whether ORD-Horn is a maximally tractable subset among the (disjunctive, binary) relations. We then generalise our results for the Rectangle Algebra to the r-dimensional Block Algebra.

上一篇:On the Satisfiability Threshold of Random Community-Structured SAT Dina Barak-Pelleg1 and Daniel Berend2?

下一篇:Descriptive Clustering: ILP and CP Formulations with Applications

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...