Knowledge Representation and Reasoning Research Publications

2022

Hamilton J, Park J, Bailey A, Meyer T. An Investigation into the Scalability of Defeasible Reasoning Algorithms. In: Second Southern African Conference for Artificial Intelligence. Online: SACAIR 2021 Organising Committee; 2022. https://protect-za.mimecast.com/s/OFYSCpgo02fL1l9gtDHUkY.

Knowledge representation and reasoning (KRR) is an approach to artificial intelligence (AI) in which a system has some information about the world represented formally (a knowledge base), and is able to reason about this information. Defeasible reasoning is a non-classical form of reasoning that enables systems to reason about knowledge bases which contain seemingly contradictory information, thus allowing for exceptions to assertions. Currently, systems which support defeasible entailment for propositional logic are ad hoc, and few and far between, and little to no work has been done on improving the scalability of defeasible reasoning algorithms. We investigate the scalability of defeasible entailment algorithms, and propose optimised versions thereof, as well as present a tool to perform defeasible entailment checks using these algorithms. We also present a knowledge base generation tool which can be used for testing implementations of these algorithms.

@{428,
  author = {Joel Hamilton and Joonsoo Park and Aidan Bailey and Thomas Meyer},
  title = {An Investigation into the Scalability of Defeasible Reasoning Algorithms},
  abstract = {Knowledge representation and reasoning (KRR) is an approach to artificial intelligence (AI) in which a system has some information about the world represented formally (a knowledge base), and is able to reason about this information. Defeasible reasoning is a non-classical form of reasoning that enables systems to reason about knowledge bases which contain seemingly contradictory information, thus allowing for exceptions to assertions. Currently, systems which support defeasible entailment for propositional logic are ad hoc, and few and far between, and little to no work has been done on improving the scalability of defeasible reasoning algorithms. We investigate the scalability of defeasible entailment algorithms, and propose optimised versions thereof, as well as present a tool to perform defeasible entailment checks using these algorithms. We also present a knowledge base generation tool which can be used for testing implementations of these algorithms.},
  year = {2022},
  journal = {Second Southern African Conference for Artificial Intelligence},
  pages = {235-251},
  month = {06/12-10/12},
  publisher = {SACAIR 2021 Organising Committee},
  address = {Online},
  isbn = {978-0-620-94410-6},
  url = {https://protect-za.mimecast.com/s/OFYSCpgo02fL1l9gtDHUkY},
}
Baker CK, Meyer T. Belief Change in Human Reasoning: An Empirical Investigation on MTurk. In: Second Southern African Conference for AI Research (SACAIR 2022). Online: SACAIR 2021 Organising Committee; 2022. https://protect-za.mimecast.com/s/OFYSCpgo02fL1l9gtDHUkY.

Belief revision and belief update are approaches to represent and reason with knowledge in artificial intelligence. Previous empirical studies have shown that human reasoning is consistent with non-monotonic logic and postulates of defeasible reasoning, belief revision and belief update. We extended previous work, which tested natural language translations of the postulates of defeasible reasoning, belief revision and belief update with human reasoners via surveys, in three respects. Firstly, we only tested postulates of belief revision and belief update, taking the position that belief change aligns more with human reasoning than non-monotonic defeasible reasoning. Secondly, we decomposed the postulates of revision and update into material implication statements of the form “If x is the case, then y is the case”, each containing a premise and a conclusion, and then translated the premises and conclusions into natural language. Thirdly, we asked human participants to judge each component of the postulate for plausibility. In our analysis, we measured the strength of the association between the premises and the conclusion of each postulate. We used Possibility theory to determine whether the postulates hold with our participants in general. Our results showed that our participants’ reasoning is consistent with postulates of belief revision and belief update when judging the premises and conclusion of the postulate separately.

@{427,
  author = {Clayton Baker and Tommie Meyer},
  title = {Belief Change in Human Reasoning: An Empirical Investigation on MTurk},
  abstract = {Belief revision and belief update are approaches to represent and reason with knowledge in artificial intelligence. Previous empirical studies have shown that human reasoning is consistent with non-monotonic logic and postulates of defeasible reasoning, belief revision and belief update. We extended previous work, which tested natural language translations of the postulates of defeasible reasoning, belief revision and belief update with human reasoners via surveys, in three respects.
Firstly, we only tested postulates of belief revision and belief update, taking the position that belief change aligns more with human reasoning than non-monotonic defeasible reasoning. Secondly, we decomposed the postulates of revision and update into material implication statements of the form “If x is the case, then y is the case”, each containing a premise
and a conclusion, and then translated the premises and conclusions into natural language. Thirdly, we asked human participants to judge each component of the postulate for plausibility. In our analysis, we measured the strength of the association between the premises and the conclusion of each postulate. We used Possibility theory to determine whether the postulates hold with our participants in general. Our results showed that our participants’ reasoning is consistent with postulates of belief
revision and belief update when judging the premises and conclusion of the postulate separately.},
  year = {2022},
  journal = {Second Southern African Conference for AI Research (SACAIR 2022)},
  pages = {218-234},
  month = {06/12/2021-10/12/2021},
  publisher = {SACAIR 2021 Organising Committee},
  address = {Online},
  isbn = {978-0-620-94410-6},
  url = {https://protect-za.mimecast.com/s/OFYSCpgo02fL1l9gtDHUkY},
}
Everett L, Morris E, Meyer T. Explanation for KLM-Style Defeasible Reasoning. In: Artificial Intelligence Research. SACAIR 2021. 1551st ed. Cham: Springer; 2022. doi:10.1007/978-3-030-95070-5_13.

Explanation services are a crucial aspect of symbolic reasoning systems but they have not been explored in detail for defeasible formalisms such as KLM. We evaluate prior work on the topic with a focus on KLM propositional logic and find that a form of defeasible explanation initially described for Rational Closure which we term weak justification can be adapted to Relevant and Lexicographic Closure as well as described in terms of intuitive properties derived from the KLM postulates. We also consider how a more general definition of defeasible explanation known as strong explanation applies to KLM and propose an algorithm that enumerates these justifications for Rational Closure.

@inbook{426,
  author = {Lloyd Everett and Emily Morris and Tommie Meyer},
  title = {Explanation for KLM-Style Defeasible Reasoning},
  abstract = {Explanation services are a crucial aspect of symbolic reasoning systems but they have not been explored in detail for defeasible formalisms such as KLM. We evaluate prior work on the topic with a focus on KLM propositional logic and find that a form of defeasible explanation initially described for Rational Closure which we term weak justification can be adapted to Relevant and Lexicographic Closure as well as described in terms of intuitive properties derived from the KLM postulates. We also consider how a more general definition of defeasible explanation known as strong explanation applies to KLM and propose an algorithm that enumerates these justifications for Rational Closure.},
  year = {2022},
  journal = {Artificial Intelligence Research. SACAIR 2021.},
  edition = {1551},
  publisher = {Springer},
  address = {Cham},
  isbn = {978-3-030-95069-9},
  url = {https://link.springer.com/book/10.1007/978-3-030-95070-5},
  doi = {10.1007/978-3-030-95070-5_13},
}

2021

Casini G, Meyer T, Varzinczak I. Contextual Conditional Reasoning. In: 35th AAAI Conference on Artificial Intelligence. Online: AAAI Press; 2021.

We extend the expressivity of classical conditional reasoning by introducing context as a new parameter. The enriched conditional logic generalises the defeasible conditional setting in the style of Kraus, Lehmann, and Magidor, and allows for a refined semantics that is able to distinguish, for example, between expectations and counterfactuals. In this paper we introduce the language for the enriched logic and define an appropriate semantic framework for it. We analyse which properties generally associated with conditional reasoning are still satisfied by the new semantic framework, provide a suitable representation result, and define an entailment relation based on Lehmann and Magidor’s generally-accepted notion of Rational Closure.

@{430,
  author = {Giovanni Casini and Tommie Meyer and Ivan Varzinczak},
  title = {Contextual Conditional Reasoning},
  abstract = {We extend the expressivity of classical conditional reasoning by introducing context as a new parameter. The enriched
conditional logic generalises the defeasible conditional setting in the style of Kraus, Lehmann, and Magidor, and allows for a refined semantics that is able to distinguish, for example, between expectations and counterfactuals. In this paper we introduce the language for the enriched logic and define an appropriate semantic framework for it. We analyse which properties generally associated with conditional reasoning are still satisfied by the new semantic framework, provide a suitable representation result, and define an entailment relation based on Lehmann and Magidor’s generally-accepted notion of Rational Closure.},
  year = {2021},
  journal = {35th AAAI Conference on Artificial Intelligence},
  pages = {6254-6261},
  month = {02/02/2021-09/02/2021},
  publisher = {AAAI Press},
  address = {Online},
}
Casini G, Meyer T, Paterson-Jones G. KLM-Style Defeasibility for Restricted First-Order Logic. In: 19th International Workshop on Non-Monotonic Reasoning. Online; 2021. https://drive.google.com/open?id=1WSIl3TOrXBhaWhckWN4NLXoD9AVFKp5R.

We extend the KLM approach to defeasible reasoning to be applicable to a restricted version of first-order logic. We describe defeasibility for this logic using a set of rationality postulates, provide an appropriate semantics for it, and present a representation result that characterises the semantic description of defeasibility in terms of the rationality postulates. Based on this theoretical core, we then propose a version of defeasible entailment that is inspired by Rational Closure as it is defined for defeasible propositional logic and defeasible description logics. We show that this form of defeasible entailment is rational in the sense that it adheres to our rationality postulates. The work in this paper is the first step towards our ultimate goal of introducing KLM-style defeasible reasoning into the family of Datalog+/- ontology languages.

@{429,
  author = {Giovanni Casini and Tommie Meyer and Guy Paterson-Jones},
  title = {KLM-Style Defeasibility for Restricted First-Order Logic},
  abstract = {We extend the KLM approach to defeasible reasoning to be applicable to a restricted version of first-order logic. We describe defeasibility for this logic using a set of rationality postulates, provide an appropriate semantics for it, and present a representation result that characterises the semantic description of defeasibility in terms of the rationality postulates. Based on this theoretical core, we then propose a version of defeasible entailment that is inspired by Rational Closure as it is defined for defeasible propositional logic and defeasible description logics. We show that this form of defeasible entailment is rational in the sense that it adheres to our rationality postulates. The work in this paper is the first step towards our ultimate goal of introducing KLM-style defeasible reasoning into the family of Datalog+/- ontology languages.},
  year = {2021},
  journal = {19th International Workshop on Non-Monotonic Reasoning},
  pages = {184-193},
  month = {03/11/2021-05/11/2021},
  address = {Online},
  url = {https://drive.google.com/open?id=1WSIl3TOrXBhaWhckWN4NLXoD9AVFKp5R},
}
Heyninck J, Thimm M, Kern-Isberner G, Rienstra T, Skiba K. On the Relation between Possibilistic Logic and Abstract Dialectical Frameworks. 2021. https://sites.google.com/view/nmr2021/home?authuser=0).

Abstract dialectical frameworks (in short, ADFs) are one of the most general and unifying approaches to formal argumentation. As the semantics of ADFs are based on three-valued interpretations, the question poses itself as to whether some and which monotonic three-valued logic underlies ADFs, in the sense that it allows to capture the main semantic concepts underlying ADFs. As an entry-point for such an investigation, we take the concept of model of an ADF, which was originally formulated on the basis of Kleene’s three-valued logic. We show that an optimal concept of a model arises when instead of Kleene’s three-valued logic, possibilistic logic is used. We then show that in fact, possibilistic logic is the most conservative three-valued logic that fulfils this property, and that possibilistic logic can faithfully encode all other semantical concepts for ADFs. Based on this result, we also make some observations on strong equivalence and introduce possibilistic ADFs.

@misc{422,
  author = {Jesse Heyninck and Matthias Thimm and Gabriele Kern-Isberner and Tjitze Rienstra and Kenneth Skiba},
  title = {On the Relation between Possibilistic Logic and Abstract Dialectical Frameworks},
  abstract = {Abstract dialectical frameworks (in short, ADFs) are one of the most general and unifying approaches to formal argumentation. As the semantics of ADFs are based on three-valued interpretations, the question poses itself as to whether some and which monotonic three-valued logic underlies ADFs, in the sense that it allows to capture the main semantic concepts underlying ADFs. As an entry-point for such an investigation, we take the concept of model of an ADF, which was originally formulated on the basis of Kleene’s three-valued logic. We show that an optimal concept of a model arises when instead of Kleene’s three-valued logic, possibilistic logic is used. We then show that in fact, possibilistic logic is the most conservative three-valued logic that fulfils this property, and that possibilistic logic can faithfully encode all other semantical concepts for ADFs. Based on this result, we also make some observations on strong equivalence and introduce possibilistic ADFs.},
  year = {2021},
  url = {https://sites.google.com/view/nmr2021/home?authuser=0)},
}
Heyninck J, Thimm M, Kern-Isberner G, Rienstra T, Skiba K. Arguing about Complex Formulas: Generalizing Abstract Dialectical Frameworks. 2021. https://sites.google.com/view/nmr2021/home?authuser=0.

Abstract dialectical frameworks (in short, ADFs) are a unifying model of formal argumentation, where argumentative relations between arguments are represented by assigning acceptance conditions to atomic arguments. This idea is generalized by letting acceptance conditions being assigned to complex formulas, resulting in conditional abstract dialectical frameworks (in short, cADFs). We define the semantics of cADFs in terms of a non-truth-functional four-valued logic, and study the semantics in-depth, by showing existence results and proving that all semantics are generalizations of the corresponding semantics for ADFs.

@misc{421,
  author = {Jesse Heyninck and Matthias Thimm and Gabriele Kern-Isberner and Tjitze Rienstra and Kenneth Skiba},
  title = {Arguing about Complex Formulas: Generalizing Abstract Dialectical Frameworks},
  abstract = {Abstract dialectical frameworks (in short, ADFs) are a unifying model of formal argumentation, where argumentative relations between arguments are represented by assigning acceptance conditions to atomic arguments. This idea is generalized by letting acceptance conditions being assigned to complex formulas, resulting in conditional abstract dialectical frameworks (in short, cADFs). We define the semantics of cADFs in terms of a non-truth-functional four-valued
logic, and study the semantics in-depth, by showing existence results and proving that all semantics are generalizations of the corresponding semantics for ADFs.},
  year = {2021},
  url = {https://sites.google.com/view/nmr2021/home?authuser=0},
}
Heyninck J, Arieli O. Approximation Fixpoint Theory for Non-Deterministic Operators and Its Application in Disjunctive Logic Programming. In: 18th International Conference on Principles of Knowledge Representation and Reasoning. Online: IJCAI Organization; 2021. doi:10.24963/kr.2021/32.

Approximation fixpoint theory (AFT) constitutes an abstract and general algebraic framework for studying the semantics of nonmonotonic logics. It provides a unifying study of the semantics of different formalisms for nonmonotonic reasoning, such as logic programming, default logic and autoepistemic logic. In this paper we extend AFT to non-deterministic constructs such as disjunctive information. This is done by generalizing the main constructions and corresponding results to non-deterministic operators, whose ranges are sets of elements rather than single elements. The applicability and usefulness of this generalization is illustrated in the context of disjunctive logic programming.

@{420,
  author = {Jesse Heyninck and Ofer Arieli},
  title = {Approximation Fixpoint Theory for Non-Deterministic Operators and Its Application in Disjunctive Logic Programming},
  abstract = {Approximation fixpoint theory (AFT) constitutes an abstract and general algebraic framework for studying the semantics of nonmonotonic logics. It provides a unifying study of the semantics of different formalisms for nonmonotonic reasoning, such as logic programming, default logic and autoepistemic logic. In this paper we extend AFT to non-deterministic constructs such as disjunctive information. This is done by generalizing the main constructions and corresponding results to non-deterministic operators, whose ranges are sets of elements rather than single elements. The applicability and usefulness of this generalization is illustrated in the context of disjunctive logic programming.},
  year = {2021},
  journal = {18th International Conference on Principles of Knowledge Representation and Reasoning},
  pages = {334-344},
  month = {03/11-12/11},
  publisher = {IJCAI Organization},
  address = {Online},
  isbn = {978-1-956792-99-7},
  url = {https://proceedings.kr.org/2021/32/},
  doi = {10.24963/kr.2021/32},
}
Heyninck J, Kern-Isberner G, Rienstra T, Skiba K, Thimm M. Revision and Conditional Inference for Abstract Dialectical Frameworks. In: 18th International Conference on Principles of Knowledge Representation and Reasoning. Online: IJCAI Organization; 2021. doi:10.24963/kr.2021/33.

For propositional beliefs, there are well-established connections between belief revision, defeasible conditionals and nonmonotonic inference. In argumentative contexts, such connections have not yet been investigated. On the one hand, the exact relationship between formal argumentation and nonmonotonic inference relations is a research topic that keeps on eluding researchers despite recently intensified efforts, whereas argumentative revision has been studied in numerous works during recent years. In this paper, we show that similar relationships between belief revision, defeasible conditionals and nonmonotonic inference hold in argumentative contexts as well. We first define revision operators for abstract dialectical frameworks, and use such revision operators to define dynamic conditionals by means of the Ramsey test. We show that such conditionals can be equivalently defined using a total preorder over three-valued interpretations, and study the inferential behaviour of the resulting conditional inference relations.

@{418,
  author = {Jesse Heyninck and Gabriele Kern-Isberner and Tjitze Rienstra and Kenneth Skiba and Matthias Thimm},
  title = {Revision and Conditional Inference for Abstract Dialectical Frameworks},
  abstract = {For propositional beliefs, there are well-established connections between belief revision, defeasible conditionals and
nonmonotonic inference. In argumentative contexts, such connections have not yet been investigated. On the one hand, the exact relationship between formal argumentation and nonmonotonic inference relations is a research topic that keeps on eluding researchers despite recently intensified efforts, whereas argumentative revision has been studied in numerous works during recent years. In this paper, we show that similar relationships between belief revision, defeasible conditionals and nonmonotonic inference hold in argumentative contexts as well. We first define revision operators for abstract dialectical frameworks, and use such revision operators to define dynamic conditionals by means of the Ramsey test. We show that such conditionals can be equivalently defined using a total preorder over three-valued interpretations, and study the inferential behaviour of the resulting conditional inference relations.},
  year = {2021},
  journal = {18th International Conference on Principles of Knowledge Representation and Reasoning},
  pages = {345-355},
  month = {03/11-12/11},
  publisher = {IJCAI Organization},
  address = {Online},
  isbn = {978-1-956792-99-7},
  url = {https://proceedings.kr.org/2021/33/},
  doi = {10.24963/kr.2021/33},
}

2020

Britz K, Casini G, Meyer T, Moodley K, Sattler U, Varzinczak I. Principles of KLM-style Defeasible Description Logics. Transactions on Computational Logic. 2020;22 (1). doi:10.1145/3420258.

The past 25 years have seen many attempts to introduce defeasible-reasoning capabilities into a description logic setting. Many, if not most, of these attempts are based on preferential extensions of description logics, with a significant number of these, in turn, following the so-called KLM approach to defeasible reasoning initially advocated for propositional logic by Kraus, Lehmann, and Magidor. Each of these attempts has its own aim of investigating particular constructions and variants of the (KLM-style) preferential approach. Here our aim is to provide a comprehensive study of the formal foundations of preferential defeasible reasoning for description logics in the KLM tradition. We start by investigating a notion of defeasible subsumption in the spirit of defeasible conditionals as studied by Kraus, Lehmann, and Magidor in the propositional case. In particular, we consider a natural and intuitive semantics for defeasible subsumption, and we investigate KLM-style syntactic properties for both preferential and rational subsumption. Our contribution includes two representation results linking our semantic constructions to the set of preferential and rational properties considered. Besides showing that our semantics is appropriate, these results pave the way for more effective decision procedures for defeasible reasoning in description logics. Indeed, we also analyse the problem of non-monotonic reasoning in description logics at the level of entailment and present an algorithm for the computation of rational closure of a defeasible knowledge base. Importantly, our algorithm relies completely on classical entailment and shows that the computational complexity of reasoning over defeasible knowledge bases is no worse than that of reasoning in the underlying classical DL ALC.

@article{433,
  author = {Katarina Britz and Giovanni Casini and Tommie Meyer and Kody Moodley and Uli Sattler and Ivan Varzinczak},
  title = {Principles of KLM-style Defeasible Description Logics},
  abstract = {The past 25 years have seen many attempts to introduce defeasible-reasoning capabilities into a description logic setting. Many, if not most, of these attempts are based on preferential extensions of description logics, with a significant number of these, in turn, following the so-called KLM approach to defeasible reasoning initially advocated for propositional logic by Kraus, Lehmann, and Magidor. Each of these attempts has its own aim of investigating particular constructions and variants of the (KLM-style) preferential approach. Here our aim is to provide a comprehensive study of the formal foundations of preferential defeasible reasoning for description logics in the KLM tradition. We start by investigating a notion of defeasible subsumption in the spirit of defeasible conditionals as studied by Kraus, Lehmann, and Magidor in the propositional case. In particular, we consider a natural and intuitive semantics for defeasible subsumption, and we investigate KLM-style syntactic properties for both preferential and rational subsumption. Our contribution includes two representation results linking our semantic
constructions to the set of preferential and rational properties considered. Besides showing that our semantics is appropriate, these results pave the way for more effective decision procedures for defeasible reasoning in description logics. Indeed, we also analyse the problem of non-monotonic reasoning in description logics at the level of entailment and present an algorithm for the computation of rational closure of a defeasible knowledge base. Importantly, our algorithm relies completely on classical entailment and shows that the computational complexity of reasoning over defeasible knowledge bases is no worse than that of reasoning in the underlying classical DL ALC.},
  year = {2020},
  journal = {Transactions on Computational Logic},
  volume = {22 (1)},
  pages = {1-46},
  publisher = {ACM},
  url = {https://dl-acm-org.ezproxy.uct.ac.za/doi/abs/10.1145/3420258},
  doi = {10.1145/3420258},
}
Botha L, Meyer T, Penaloza R. The Probabilistic Description Logic BALC. Theory and Practice of Logic Programming. 2020. doi:10.1017/S1471068420000460.

Description logics (DLs) are well-known knowledge representation formalisms focused on the representation of terminological knowledge. Due to their first-order semantics, these languages (in their classical form) are not suitable for representing and handling uncertainty. A probabilistic extension of a light-weight DL was recently proposed for dealing with certain knowledge occurring in uncertain contexts. In this paper, we continue that line of research by introducing the Bayesian extension BALC of the propositionally closed DL ALC. We present a tableau-based procedure for deciding consistency and adapt it to solve other probabilistic, contextual, and general inferences in this logic. We also show that all these problems remain ExpTime-complete, the same as reasoning in the underlying classical ALC.

@article{432,
  author = {Leonard Botha and Tommie Meyer and Rafael Penaloza},
  title = {The Probabilistic Description Logic BALC},
  abstract = {Description logics (DLs) are well-known knowledge representation formalisms focused on the representation of terminological knowledge. Due to their first-order semantics, these languages (in their classical form) are not suitable for representing and handling uncertainty. A probabilistic extension of a light-weight DL was recently proposed for dealing with certain knowledge occurring in uncertain contexts. In this paper, we continue that line of research by introducing the Bayesian extension BALC of the propositionally closed DL ALC. We present a tableau-based procedure for deciding consistency and adapt it to solve other probabilistic, contextual, and general inferences in this logic. We also show that all these problems remain ExpTime-complete,
the same as reasoning in the underlying classical ALC.},
  year = {2020},
  journal = {Theory and Practice of Logic Programming},
  pages = {1-24},
  publisher = {Cambridge University Press},
  doi = {10.1017/S1471068420000460},
}
Borgwardt S, Meyer T. Proceedings of the 33rd International Workshop on Description Logics (DL 2020). In: 33rd International Workshop on Description Logics (DL 2020). Online; 2020. http://ceur-ws.org/Vol-2663/.

Not applicable.

@{431,
  author = {Stefan Borgwardt and Tommie Meyer},
  title = {Proceedings of the 33rd International Workshop on Description Logics (DL 2020)},
  abstract = {Not applicable.},
  year = {2020},
  journal = {33rd International Workshop on Description Logics (DL 2020)},
  month = {12/09/2020-14/09/2020},
  address = {Online},
  url = {http://ceur-ws.org/Vol-2663/},
}
Kaliski A, Meyer T. Quo Vadis KLM-style Defeasible Reasoning? In: First Southern African Conference for Artificial Intelligence Research. Virtual: SACAIR2020; 2020. https://2020.sacair.org.za/wp-content/uploads/2021/02/SACAIR_Proceedings-MainBook_Finv4_compressed.pdf?_ga=2.116601743.849395099.1621802506-572599210.1621419278.

The field of defeasible reasoning has a variety of frameworks, all of which are constructed with the view of codifying the patterns of common-sense reasoning inherent to human reasoning. One of these frameworks was first described by Kraus, Lehmann and Magidor, and is accordingly referred to as the KLM framework. Initially defined in propositional logic, it has since been imported into description and modal logics, and implemented into many defeasible reasoning engines. However, there are many ways in which this framework may be advanced theoretically, and many opportunities for it to be applied. This paper covers some of the most prominent areas of future work and possible applications of this framework, with the intention that anyone who has recently familiarized themselves with this approach may then have an understanding of the kind of work in which they could engage.

@{414,
  author = {Adam Kaliski and Tommie Meyer},
  title = {Quo Vadis KLM-style Defeasible Reasoning?},
  abstract = {The field of defeasible reasoning has a variety of frameworks, all of which are constructed with the view of codifying the patterns of common-sense reasoning inherent to human reasoning. One of these frameworks was first described by Kraus, Lehmann and Magidor, and is accordingly referred to as the KLM framework. Initially defined in propositional logic, it has since been imported into description and modal logics, and implemented into many defeasible reasoning engines. However, there are many ways in which this framework may be advanced theoretically, and many opportunities for it to be applied. This paper covers some of the most prominent areas of future work and possible applications of this framework, with the intention that anyone who has recently familiarized themselves with this approach may then have an understanding of the kind of work in which they could engage.},
  year = {2020},
  journal = {First Southern African Conference for Artificial Intelligence Research},
  pages = {231-246},
  month = {22/02/2021},
  publisher = {SACAIR2020},
  address = {Virtual},
  isbn = {978-0-620-89373-2},
  url = {https://2020.sacair.org.za/wp-content/uploads/2021/02/SACAIR_Proceedings-MainBook_Finv4_compressed.pdf?_ga=2.116601743.849395099.1621802506-572599210.1621419278},
}
Paterson-Jones G, Meyer T. A Boolean Extension of KLM-style Conditional Reasoning. In: First Southern African Conference for AI Research (SACAIR 2020). Muldersdrift, South Africa: Springer; 2020. doi:10.1007/978-3-030-66151-9_15.

Propositional KLM-style defeasible reasoning involves extending propositional logic with a new logical connective that can express defeasible (or conditional) implications, with semantics given by ordered structures known as ranked interpretations. KLM-style defeasible entailment is referred to as rational whenever the defeasible entailment relation under consideration generates a set of defeasible implications all satisfying a set of rationality postulates known as the KLM postulates. In a recent paper Booth et al. proposed PTL, a logic that is more expressive than the core KLM logic. They proved an impossibility result, showing that defeasible entailment for PTL fails to satisfy a set of rationality postulates similar in spirit to the KLM postulates. Their interpretation of the impossibility result is that defeasible entailment for PTL need not be unique. In this paper we continue the line of research in which the expressivity of the core KLM logic is extended. We present the logic Boolean KLM (BKLM) in which we allow for disjunctions, conjunctions, and negations, but not nesting, of defeasible implications. Our contribution is twofold. Firstly, we show (perhaps surprisingly) that BKLM is more expressive than PTL. Our proof is based on the fact that BKLM can characterise all single ranked interpretations, whereas PTL cannot. Secondly, given that the PTL impossibility result also applies to BKLM, we adapt the different forms of PTL entailment proposed by Booth et al. to apply to BKLM.

@{413,
  author = {Guy Paterson-Jones and Tommie Meyer},
  title = {A Boolean Extension of KLM-style Conditional Reasoning},
  abstract = {Propositional KLM-style defeasible reasoning involves extending propositional logic with a new logical connective that can express defeasible (or conditional) implications, with semantics given by ordered structures known as ranked interpretations. KLM-style defeasible entailment is referred to as rational whenever the defeasible entailment relation under consideration generates a set of defeasible implications all satisfying a set of rationality postulates known as the KLM postulates. In a recent paper Booth et al. proposed PTL, a logic that is more expressive than the core KLM logic. They proved an impossibility result, showing that defeasible entailment for PTL fails to satisfy a set of rationality postulates similar in spirit to the KLM postulates. Their interpretation of the impossibility result is that defeasible entailment for PTL need not be unique. In this paper we continue the line of research in which the expressivity of the core KLM logic is extended. We present the logic Boolean KLM (BKLM) in which we allow for disjunctions, conjunctions, and negations, but not nesting, of defeasible implications. Our contribution is twofold. Firstly, we show (perhaps surprisingly) that BKLM is more expressive than PTL. Our proof is based on the fact that BKLM can characterise all single ranked interpretations, whereas PTL cannot. Secondly, given that the PTL impossibility result also applies to BKLM, we adapt the different forms of PTL entailment proposed by Booth et al. to apply to BKLM.},
  year = {2020},
  journal = {First Southern African Conference for AI Research (SACAIR 2020)},
  pages = {236-252},
  month = {22/02/2021-26/02/2021},
  publisher = {Springer},
  address = {Muldersdrift, South Africa},
  isbn = {978-3-030-66151-9},
  url = {https://link.springer.com/book/10.1007/978-3-030-66151-9},
  doi = {10.1007/978-3-030-66151-9_15},
}
Baker CK, Denny C, Freund P, Meyer T. Cognitive Defeasible Reasoning: the Extent to which Forms of Defeasible Reasoning Correspond with Human Reasoning. In: First Southern African Conference for AI Research (SACAIR 2020). Muldersdrift, South Africa: Springer; 2020. doi:10.1007/978-3-030-66151-9_13.

Classical logic forms the basis of knowledge representation and reasoning in AI. In the real world, however, classical logic alone is insufficient to describe the reasoning behaviour of human beings. It lacks the flexibility so characteristically required of reasoning under uncertainty, reasoning under incomplete information and reasoning with new information, as humans must. In response, non-classical extensions to propositional logic have been formulated, to provide non-monotonicity. It has been shown in previous studies that human reasoning exhibits non-monotonicity. This work is the product of merging three independent studies, each one focusing on a different formalism for non-monotonic reasoning: KLM defeasible reasoning, AGM belief revision and KM belief update. We investigate, for each of the postulates propounded to characterise these logic forms, the extent to which they have correspondence with human reasoners. We do this via three respective experiments and present each of the postulates in concrete and abstract form. We discuss related work, our experiment design, testing and evaluation, and report on the results from our experiments. We find evidence to believe that 1 out of 5 KLM defeasible reasoning postulates, 3 out of 8 AGM belief revision postulates and 4 out of 8 KM belief update postulates conform in both the concrete and abstract case. For each experiment, we performed an additional investigation. In the experiments of KLM defeasible reasoning and AGM belief revision, we analyse the explanations given by participants to determine whether the postulates have a normative or descriptive relationship with human reasoning. We find evidence that suggests, overall, KLM defeasible reasoning has a normative relationship with human reasoning while AGM belief revision has a descriptive relationship with human reasoning. In the experiment of KM belief update, we discuss counter-examples to the KM postulates.

@{412,
  author = {Clayton Baker and Claire Denny and Paul Freund and Tommie Meyer},
  title = {Cognitive Defeasible Reasoning: the Extent to which Forms of Defeasible Reasoning Correspond with Human Reasoning},
  abstract = {Classical logic forms the basis of knowledge representation and reasoning in AI. In the real world, however, classical logic alone is insufficient to describe the reasoning behaviour of human beings. It lacks the flexibility so characteristically required of reasoning under uncertainty, reasoning under incomplete information and reasoning with new information, as humans must. In response, non-classical extensions to propositional logic have been formulated, to provide non-monotonicity. It has been shown in previous studies that human reasoning exhibits non-monotonicity. This work is the product of merging three independent studies, each one focusing on a different formalism for non-monotonic reasoning: KLM defeasible reasoning, AGM belief revision and KM belief update. We investigate, for each of the postulates propounded to characterise these logic forms, the extent to which they have correspondence with human reasoners. We do this via three respective experiments and present each of the postulates in concrete and abstract form. We discuss related work, our experiment design, testing and evaluation, and report on the results from our experiments. We find evidence to believe that 1 out of 5 KLM defeasible reasoning postulates, 3 out of 8 AGM belief revision postulates and 4 out of 8 KM belief update postulates conform in both the concrete and abstract case. For each experiment, we performed an additional investigation. In the experiments of KLM defeasible reasoning and AGM belief revision, we analyse the explanations given by participants to determine whether the postulates have a normative or descriptive relationship with human reasoning. We find evidence that suggests, overall, KLM defeasible reasoning has a normative relationship with human reasoning while AGM belief revision has a descriptive relationship with human reasoning. In the experiment of KM belief update, we discuss counter-examples to the KM postulates.},
  year = {2020},
  journal = {First Southern African Conference for AI Research (SACAIR 2020)},
  pages = {199-219},
  month = {22/02/2021-26/02/2021},
  publisher = {Springer},
  address = {Muldersdrift, South Africa},
  isbn = {978-3-030-66151-9},
  url = {https://link.springer.com/book/10.1007/978-3-030-66151-9},
  doi = {10.1007/978-3-030-66151-9_13},
}
  • CSIR
  • DSI
  • Covid-19