We introduce modular calculi for the logics for nonmonotonic reasoning defined by Kraus, Lehmann, and Magidor, featuring a strengthened form of analyticity. Our calculi are used to determine the computational complexity for the logics C, CL, CM, P (and M), and fragments thereof. The calculi are encoded into SMT solvers, yielding an efficient prover with countermodel generation capabilities. Our work encompasses known results and introduces new findings, including co-NP-completeness and a more effective semantics for C.

We propose a novel knowledge representation method for the Default Logic paradigm by developing a proof calculus that yields arguments and counterarguments in which defaults serve as explicit objects of reasoning. The proposed formalism allows for more transparent default reasoning and the use of explainability methods in formal argumentation. In particular, we provide a sound and complete argumentative characterization of Default Logic, by demonstrating that argumentation frameworks instantiated by the arguments derivable in our calculus yields the same inference relation as that of Default Logic. The modularity of our approach allows for various modifications of Default Logic. We demonstrate this by extending our calculus with a rule that enables disjunctive defeasible reasoning.

Standard epistemic logic is concerned with describing agents’ epistemic attitudes given the current set of alternatives the agents consider possible. While distributed systems can (and often are) discussed without mentioning epistemics, it has been well established that epistemic phenomena lie at the heart of what agents, or processes, can and cannot do. Dynamic epistemic logic (DEL) aims to describe how epistemic attitudes of the agents/processes change based on the new information they receive, e.g., based on their observations of events and actions in a distributed system. In a broader philosophical view, this appeals to an a posteriori kind of reasoning, where agents update the set of alternatives considered possible based on their “experiences.” Until recently, there was little incentive to formalize a priorireasoning, which plays a role in designing and maintaining distributed systems, e.g., in determining which states must be considered possible by agents in order to solve the distributed task at hand, and consequently in updating these states when unforeseen situations arise during runtime. With systems becoming more and more complex and large, the task of fixing design errors “on the fly” is shifted to individual agents, such as in the increasingly popular self-adaptive and self-organizing (SASO) systems. Rather than updating agents’ a posteriori beliefs, this requires modifying their a priori beliefs about the system’s global design and parameters. The goal of this paper is to provide a formalization of such a priori reasoning by using standard epistemic semantic tools, including Kripke models and DEL-style updates, and provide heuristics that would pave the way to streamlining this inherently non-deterministic and ad hoc process for SASO systems.