Publication

Qualitative Spatial and Temporal Reasoning with Answer Set Programming

Jingshi Li
2012
Conference Papers

Abstract

Representing and reasoning spatial and temporal information is a key research issue in Computer Science and Artificial Intelligence. In this paper, we introduce tools that produce three novel encodings which translate problems in qualitative spatial and temporal reasoning into logic programs for answer set programming solvers. Each encoding reflects a different type of modeling abstraction. We evaluate our approach with two of the most well known qualitative spatial and temporal reasoning formalisms, the Interval Algebra and Region Connection Calculus. Our results show some surprising findings, including the strong performance of the solver for disjunctive logic programs over the non-disjunctive ones on our benchmark problems.

Official source

https://infoscience.epfl.ch/entities/publication/a04c9544-3311-4347-bbcd-b62e9c7176b7

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Jingshi Li
2012
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/a04c9544-3311-4347-bbcd-b62e9c7176b7

About this result

Related concepts (32)

Logic programming

Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, answer set programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses: H :- B1, ..., Bn. and are read declaratively as logical implications: H if B1 and ... and Bn. H is called the head of the rule and B1, .

Answer set programming

Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop).

Stable model semantics

The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program completion and the well-founded semantics. The stable model semantics is the basis of answer set programming.

Related publications (32)

Qualitative Spatial and Temporal Reasoning with Answer Set Programming

Chat with Graph Search

Generative AI-Enabled Conversational Interaction to Support Self-Directed Learning Experiences in Transversal Computational Thinking

Proving and Disproving Equivalence of Functional Programming Assignments

OrthoPlanes: A Novel Representation for Better 3D-Awareness of GANs