The Experts below are selected from a list of 231 Experts worldwide ranked by ideXlab platform
Marcus Bjareland - One of the best experts on this subject based on the ideXlab platform.
-
expressive Reasoning about Action in nondeterministic polynomial time
International Joint Conference on Artificial Intelligence, 1999Co-Authors: Thomas Drakengren, Marcus BjarelandAbstract:The rapid development of efficient heuristics for deciding satisfiability for propositional logic motivates thorough investigations of the usability of NP-complete problems in general. In this paper we introduce a logic of Action and change which is expressive in the sense that it can represent most propositional benchmark examples in the literature, and some new examples involving parallel composition of Actions, and Actions that may or may not be executed. We prove that satisfiability of a scenario in this logic is NP-complete, and that it subsumes an NP-complete logic (which in turn includes a nontrivial polynomial-time fragment) previously introduced by Drakengren and Bjareland.
-
IJCAI - Expressive Reasoning about Action in Nondeterministic Polynomial Time
1999Co-Authors: Thomas Drakengren, Marcus BjarelandAbstract:The rapid development of efficient heuristics for deciding satisfiability for propositional logic motivates thorough investigations of the usability of NP-complete problems in general. In this paper we introduce a logic of Action and change which is expressive in the sense that it can represent most propositional benchmark examples in the literature, and some new examples involving parallel composition of Actions, and Actions that may or may not be executed. We prove that satisfiability of a scenario in this logic is NP-complete, and that it subsumes an NP-complete logic (which in turn includes a nontrivial polynomial-time fragment) previously introduced by Drakengren and Bjareland.
-
Reasoning about Action in polynomial time
International Joint Conference on Artificial Intelligence, 1997Co-Authors: Thomas Drakengren, Marcus BjarelandAbstract:Although many formalisms for Reasoning about Action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this paper are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for Reasoning about Action, and NP-completeness results for the unrestricted problems. Many interesting Reasoning problems can be modelled, involving nondeterminism, concurrency and memory of Actions. The Reasoning process is proved to be sound and complete.
-
IJCAI - Reasoning about Action in polynomial time
1997Co-Authors: Thomas Drakengren, Marcus BjarelandAbstract:Although many formalisms for Reasoning about Action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this paper are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for Reasoning about Action, and NP-completeness results for the unrestricted problems. Many interesting Reasoning problems can be modelled, involving nondeterminism, concurrency and memory of Actions. The Reasoning process is proved to be sound and complete.
Thomas Drakengren - One of the best experts on this subject based on the ideXlab platform.
-
expressive Reasoning about Action in nondeterministic polynomial time
International Joint Conference on Artificial Intelligence, 1999Co-Authors: Thomas Drakengren, Marcus BjarelandAbstract:The rapid development of efficient heuristics for deciding satisfiability for propositional logic motivates thorough investigations of the usability of NP-complete problems in general. In this paper we introduce a logic of Action and change which is expressive in the sense that it can represent most propositional benchmark examples in the literature, and some new examples involving parallel composition of Actions, and Actions that may or may not be executed. We prove that satisfiability of a scenario in this logic is NP-complete, and that it subsumes an NP-complete logic (which in turn includes a nontrivial polynomial-time fragment) previously introduced by Drakengren and Bjareland.
-
IJCAI - Expressive Reasoning about Action in Nondeterministic Polynomial Time
1999Co-Authors: Thomas Drakengren, Marcus BjarelandAbstract:The rapid development of efficient heuristics for deciding satisfiability for propositional logic motivates thorough investigations of the usability of NP-complete problems in general. In this paper we introduce a logic of Action and change which is expressive in the sense that it can represent most propositional benchmark examples in the literature, and some new examples involving parallel composition of Actions, and Actions that may or may not be executed. We prove that satisfiability of a scenario in this logic is NP-complete, and that it subsumes an NP-complete logic (which in turn includes a nontrivial polynomial-time fragment) previously introduced by Drakengren and Bjareland.
-
Reasoning about Action in polynomial time
International Joint Conference on Artificial Intelligence, 1997Co-Authors: Thomas Drakengren, Marcus BjarelandAbstract:Although many formalisms for Reasoning about Action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this paper are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for Reasoning about Action, and NP-completeness results for the unrestricted problems. Many interesting Reasoning problems can be modelled, involving nondeterminism, concurrency and memory of Actions. The Reasoning process is proved to be sound and complete.
-
IJCAI - Reasoning about Action in polynomial time
1997Co-Authors: Thomas Drakengren, Marcus BjarelandAbstract:Although many formalisms for Reasoning about Action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this paper are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for Reasoning about Action, and NP-completeness results for the unrestricted problems. Many interesting Reasoning problems can be modelled, involving nondeterminism, concurrency and memory of Actions. The Reasoning process is proved to be sound and complete.
Dimitris Plexousakis - One of the best experts on this subject based on the ideXlab platform.
-
The ramification problem in temporal databases: a solution implemented in SQL
Applied Intelligence, 2012Co-Authors: Nikos Papadakis, Dimitris Plexousakis, Yannis ChristodolouAbstract:In this paper we elaborate on the handling of the ramification problem in the setting of temporal databases. Starting with the observation that solutions from the literature on Reasoning about Action are inadequate for addressing the ramification problem, in our prior work (Papadakis and Plexousakis in Int. J. Artif. Intel., 12(3):315, 2003 ) we have presented a solution based on an extension of the situation calculus and the work of McCain and Turner. Also, we have dealt with the ramification problem in spatial databases (Papadakis and Christodoulou in Expert Syst. Appl. 37:1374, 2010 ). In this paper, we present a tool that connects the theoretical results to practical considerations, by producing the appropriate SQL commands in order to address the ramification problem. (A preliminary version of this work appears in Papadakis et al., 17th Inter Symposium on Methodologies for Intelligent Systems, pp. 381–388, 2008 )
-
The ramification problem in temporal databases: an approach with conflicting constraints
Journal of Intelligent Information Systems, 2012Co-Authors: Nikos Papadakis, Dimitris Plexousakis, Myron Papadakis, Harris ManifavasAbstract:In this paper we study the ramification problem in the setting of temporal databases. Standard solutions from the literature on Reasoning about Action are inadequate because they rely on the assumption that fluents persist, and because Actions have effects on the next situation only. In this paper we provide a solution to the ramification problem based on an extension of the situation calculus and the work of McCain and Turner. More specifically, we study the case where there are conflicting effects of an Action, a particularly complex problem. Also we present a tool which implements the proposed solution.
-
The Ramification Problem in Temporal Databases: Concurrent Execution with Conflicting Constraints
19th IEEE International Conference on Tools with Artificial Intelligence(ICTAI 2007), 2007Co-Authors: Nikos Papadakis, Grigoris Antoniou, Dimitris PlexousakisAbstract:In this paper we study the ramification problem in the setting of temporal databases. Standard solutions from the literature on Reasoning about Action are inadequate because they rely on the assumptions that fluents persist and Actions have effects on the subsequent situation only. We provide a solution based on an extension of the situation calculus and the work of McCain and Turner. More specifically, we study the case where there are conflicting effects of concurrently executing Actions and we distinguish between hard and soft integrity constraints.
Nikos Papadakis - One of the best experts on this subject based on the ideXlab platform.
-
The ramification problem in temporal databases: a solution implemented in SQL
Applied Intelligence, 2012Co-Authors: Nikos Papadakis, Dimitris Plexousakis, Yannis ChristodolouAbstract:In this paper we elaborate on the handling of the ramification problem in the setting of temporal databases. Starting with the observation that solutions from the literature on Reasoning about Action are inadequate for addressing the ramification problem, in our prior work (Papadakis and Plexousakis in Int. J. Artif. Intel., 12(3):315, 2003 ) we have presented a solution based on an extension of the situation calculus and the work of McCain and Turner. Also, we have dealt with the ramification problem in spatial databases (Papadakis and Christodoulou in Expert Syst. Appl. 37:1374, 2010 ). In this paper, we present a tool that connects the theoretical results to practical considerations, by producing the appropriate SQL commands in order to address the ramification problem. (A preliminary version of this work appears in Papadakis et al., 17th Inter Symposium on Methodologies for Intelligent Systems, pp. 381–388, 2008 )
-
The ramification problem in temporal databases: an approach with conflicting constraints
Journal of Intelligent Information Systems, 2012Co-Authors: Nikos Papadakis, Dimitris Plexousakis, Myron Papadakis, Harris ManifavasAbstract:In this paper we study the ramification problem in the setting of temporal databases. Standard solutions from the literature on Reasoning about Action are inadequate because they rely on the assumption that fluents persist, and because Actions have effects on the next situation only. In this paper we provide a solution to the ramification problem based on an extension of the situation calculus and the work of McCain and Turner. More specifically, we study the case where there are conflicting effects of an Action, a particularly complex problem. Also we present a tool which implements the proposed solution.
-
The Ramification Problem in Temporal Databases: Concurrent Execution with Conflicting Constraints
19th IEEE International Conference on Tools with Artificial Intelligence(ICTAI 2007), 2007Co-Authors: Nikos Papadakis, Grigoris Antoniou, Dimitris PlexousakisAbstract:In this paper we study the ramification problem in the setting of temporal databases. Standard solutions from the literature on Reasoning about Action are inadequate because they rely on the assumptions that fluents persist and Actions have effects on the subsequent situation only. We provide a solution based on an extension of the situation calculus and the work of McCain and Turner. More specifically, we study the case where there are conflicting effects of concurrently executing Actions and we distinguish between hard and soft integrity constraints.
Witold Lukaszewicz - One of the best experts on this subject based on the ideXlab platform.
-
Reasoning about Action and change defeasible observations and Actions with abnormal effects
KI '96 Proceedings of the 20th Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence, 1996Co-Authors: Janusz Jablonowski, Witold Lukaszewicz, Ewa MadalinskabugajAbstract:We provide a very general framework to reason about Action and change. Our approach generalizes existing formalisms aimed at this type of inference in three respects. Firstly, we admit Actions with abnormal effects, i.e. Actions that may behave abnormally with respect to their intended specifications. Secondly, we admit defeasible observations, i.e. observations that are subject to invalidation. Thirdly, we admit arbitrary priorities between abnormalities, what allows us to prefer some Actions and/or observations while resolving conflicts.
-
Reasoning about Action and change Actions with abnormal effects
KI '95 Proceedings of the 19th Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence, 1995Co-Authors: Witold Lukaszewicz, Ewa MadalinskabugajAbstract:Most of the research devoted to Reasoning about Action and change has been based on the assumption that each Action behaves in a fixed way. More specifically, to each Action A there is assigned a unique specification S describing the effects of A in terms of a state in which A is performed.1 For instance, the well-known Action shoot is usually defined as making a gun unloaded and a turkey dead, provided that a gun was loaded. Accordingly, each time the Action is executed in a state in which the gun is loaded, it is taken for granted that the turkey is made dead.
-
Reasoning about Action and change using dijkstra s semantics for programming languages preliminary report
International Joint Conference on Artificial Intelligence, 1995Co-Authors: Witold Lukaszewicz, Ewa MadaliriskabugajAbstract:We apply Dijkstra's semantics for programming languages to formalization of Reasoning about Action and change. The basic idea is to view Actions as formula transformers, i.e. functions from formulae into formulae. The major advantage of our proposal is that it is very simple and more effective than most of other approaches. Yet, it deals with a broad class of Actions, including those with random and indirect effects. Also, both temporal prediction and postdiction Reasoning tasks can be solved without restricting initial nor final states to completely specified.
-
IJCAI - Reasoning about Action and change using Dijkstra's semantics for programming languages: preliminary report
1995Co-Authors: Witold Lukaszewicz, Ewa Madaliriska-bugajAbstract:We apply Dijkstra's semantics for programming languages to formalization of Reasoning about Action and change. The basic idea is to view Actions as formula transformers, i.e. functions from formulae into formulae. The major advantage of our proposal is that it is very simple and more effective than most of other approaches. Yet, it deals with a broad class of Actions, including those with random and indirect effects. Also, both temporal prediction and postdiction Reasoning tasks can be solved without restricting initial nor final states to completely specified.
-
circumscribing features and fluents a fluent logic for Reasoning about Action and change
International Syposium on Methodologies for Intelligent Systems, 1994Co-Authors: Patrick Doherty, Witold LukaszewiczAbstract:Sandewall has recently proposed a systematic approach to the representation of knowledge about dynamical systems that includes a general framework in which to assess the range of applicability of existing and new logics for Action and change. As part of the framework, several logics of preferential entailment are introduced and assessed for particular classes of Action scenario descriptions. The intent of this paper is to provide syntactic characterizations of several of these relations of preferential entailment in terms of circumscription with a standard base logic consisting of FOPC with temporal terms and discrete time. It turns out that occluded circumscription, which covers the broadest class of Action scenarios, and includes many of the most problematic scenarios studied in the literature, is one of the most straightforward logics considered. The class includes scenarios with non-deterministic Actions, Actions with duration, partial specification of any state including the first, and incomplete specification of the timing and order of Actions.
