Search

Default logic and formal argumentation are paradigmatic methods in the study of nonmonotonic inference. Defeasible information often comes in different strengths stemming from different degrees of reliability in epistemic applications or from varying strengths of authorities issuing norms in deontic applications. In both paradigms methods have been developed to deal with prioritized knowledge bases and normative systems. Questions of comparability of these methods therefore naturally arise. Argumentation theory has been developed with a strong emphasis on unification. It is therefore a desideratum to obtain natural representations of various approaches to (prioritized) default logic within frameworks of structured argumentation, such as ASPIC. Important steps in this direction have been presented in Liao et al. (2016, 2018). In this work we identify and address some problems in earlier translations, we broaden the focus from total to modular orderings of defaults, and we consider non-normal defaults.

Default logic and formal argumentation are paradigmatic methods in the study of nonmonotonic inference. Defeasible information often comes in different strengths stemming from different degrees of reliability in epistemic applications or from varying strengths of authorities issuing norms in deontic applications. In both paradigms methods have been developed to deal with prioritized knowledge bases and normative systems. Questions of comparability of these methods therefore naturally arise. Argumentation theory has been developed with a strong emphasis on unification. It is therefore a desideratum to obtain natural representations of various approaches to (prioritized) default logic within frameworks of structured argumentation, such as ASPIC. Important steps in this direction have been presented in Liao et al. (2016, 2018). In this work we identify and address some problems in earlier translations, we broaden the focus from total to modular orderings of defaults, and we consider non-normal defaults.

This work aims to study the processing differences that occur between deductive logic and default logic. Since the entailments are based on deductive logic and generalised conversational implicatures (GCI) are built from the default logic, two questionnaires were proposed to collect the processing efficiency expressed as the number of hits per minute. The data collected shows that there is a significant difference in the processing of entailments and ICGs: entailments are processed more efficiently than ICGs and, therefore, it is concluded that the default logic requires greater cognitive effort., Este trabajo tiene como objetivo estudiar las diferencias de procesamiento que se producen al aplicar una lógica de tipo deductivo frente a una lógica por defecto. Como los entrañamientos se fundamentan en la lógica deductiva, mientras que las implicaturas conversacionales generalizadas (ICG) se construyen a partir de la lógica por defecto, se propusieron dos cuestionarios destinados a registrar la eficacia de procesamiento entendida como el número de aciertos por minuto. Los datos recogidos muestran que existe una diferencia significativa en el procesamiento de los entrañamientos y de las ICG: los entrañamientos se procesan de forma más eficaz que las ICG y, por tanto, se concluye que la lógica por defecto exige un mayor esfuerzo cognitivo.

Parameterized complexity is a branch of a computational complexity. The pioneers of this new and promising research field are Downey and Fellows. They suggest to examine the structural properties of a given problem and restrict the instance by a parameter. In this thesis we investigate the parameterized complexity of various problems in default logic and in temporal logics. In the first section of Chapter 3 we introduce a dynamic programming algorithm which decides whether a given default theory has a consistent stable extension in fpt-time and enumerates all generating defaults that lead to a stable extension with a pre-computation step that is linear in the input theory and triple exponential in the tree-width followed by a linear delay to output solutions. In the second part of this chapter we lift the notion of backdoors to the field of default logics. We consider two problems, first we are interested to detect a backdoor and then to evaluate it for the target formulae classes HORN, KROM, POSITIVE-UNITand MONOTONE. In Chapter 4, we investigate the parameterized complexity of problems in various tem- poral logics. In the first section we introduce several graph-like structures for formula representation and the corresponding notion of tree-width and path-width. To obtain the fixed parameter tractability of different fragments, we generalize the prominent Courcelle’s Theorem to work for infinite signatures. In this section, we also consider Boolean operator fragments in the sense of Post’s lattice. In the second part of Chapter 4 we introduce the notion of backdoors for the glob- ally fragment of linear temporal logic. Again, our problems of interest are to detect a backdoor and to evaluate it, this time, for the target formulae classes HORN and KROM.

We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld et al. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XP nu), unless P = NP.

Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen's system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds for LK. On the other hand, we show an exponential lower bound to the proof size in Bonatti and Olivetti's enhanced calculus for skeptical default reasoning.

In this paper, we propose a new nonmonotonic logic called general default logic. On the one hand, it generalizes Reiter's default logic by adding to it rule-like operators used in logic programming. On the other hand, it extends logic programming by allowing arbitrary propositional formulas. We show that with this new logic, one can formalize naturally rule constraints, generalized closed world assumptions, and conditional defaults. We show that under a notion of strong equivalence, sentences of this new logic can be converted to a normal form. We also investigate the computational complexity of various reasoning tasks in the logic, and relate it to some other nonmonotonic formalisms such as Lin and Shoham's logic of GK and Moore's autoepistemic logic.

In this paper, we propose a new nonmonotonic logic called general default logic. On the one hand, it generalizes Reiter's default logic by adding to it rule-like operators used in logic programming. On the other hand, it extends logic programming by allowing arbitrary propositional formulas. We show that with this new logic, one can formalize naturally rule constraints, generalized closed world assumptions, and conditional defaults. We show that under a notion of strong equivalence, sentences of this new logic can be converted to a normal form. We also investigate the computational complexity of various reasoning tasks in the logic, and relate it to some other nonmonotonic formalisms such as Lin and Shoham's logic of GK and Moore's autoepistemic logic.

In this paper, we propose a new nonmonotonic logic called general default logic. On the one hand, it generalizes Reiter's default logic by adding to it rule-like operators used in logic programming. On the other hand, it extends logic programming by allowing arbitrary propositional formulas. We show that with this new logic, one can formalize naturally rule constraints, generalized closed world assumptions, and conditional defaults. We show that under a notion of strong equivalence, sentences of this new logic can be converted to a normal form. We also investigate the computational complexity of various reasoning tasks in the logic, and relate it to some other nonmonotonic formalisms such as Lin and Shoham's logic of GK and Moore's autoepistemic logic.

In this paper, we deal with regulations that may exist in multi-agent systems in order to regulate agent behaviour and we discuss two properties of regulations, that is consistency and completeness. After defining what consistency and completeness mean, we propose a way to consistently complete incomplete regulations. In this contribution, we extend previous works and we consider that regulations are expressed in a first order modal deontic logic.

This paper considers the problem of checking whether an organization conforms to a body of regulation. Conformance is cast as a trace checking question - the regulation is represented in a logic that is evaluated against an abstract trace or run representing the operations of an organization. We focus on a problem in designing a logic to represent regulation. A common phenomenon in regulatory texts is for sentences to refer to others for conditions or exceptions. We motivate the need for a formal representation of regulation to accommodate such references between statements. We then extend linear temporal logic to allow statements to refer to others. The semantics of the resulting logic is defined via a combination of techniques from Reiter's default logic and Kripke's theory of truth., Sponsored in part by Office of Naval Research MURI Grant no. N00014-07-1-0907 and National Science Foundation Grants nos. CCF-0429948 and NSF-CNS-0610297. This paper is an expanded version of Dinesh, N., Joshi, A., Lee, I., Sokolsky, O.: Reasoning about conditions and exceptions to laws in regulatory conformance checking. In: Ninth Interntational Conference on Deontic Logic in Computer Science (DEON). (2008)

The sentences of deontic logic may be understood as describing what an agent ought to do when faced with a given set of norms. If these norms come into conflict, the best the agent can be expected to do is to follow a maximal subset of the norms. Intuitively, a priority ordering of the norms can be helpful in determining the relevant sets and resolve conflicts, but a formal resolution mechanism has been difficult to provide. In particular, reasoning about prioritized conditional imperatives is overshadowed by problems such as the `order puzzle' that are not satisfactorily resolved by existing approaches. The paper provides a new proposal as to how these problems may be overcome.

We revisit the issue of epistemological and semantic foundations for autoepistemic and default logics, two leading formalisms in nonmonotonic reasoning. We develop a general semantic approach to autoepistemic and default logics that is based on the notion of a belief pair and that exploits the lattice structure of the collection of all belief pairs. For each logic, we introduce a monotone operator on the lattice of belief pairs. We then show that a whole family of semantics can be defined in a systematic and principled way in terms of fixpoints of this operator (or as fixpoints of certain closely related operators). Our approach elucidates fundamental constructive principles in which agents form their belief sets, and leads to approximation semantics for autoepistemic and default logics. It also allows us to establish a precise one-to-one correspondence between the family of semantics for default logic and the family of semantics for autoepistemic logic. The correspondence exploits the modal interpretation of a default proposed by Konolige. Our results establish conclusively that default logic can be viewed as a fragment of autoepistemic logic, a result that has been long anticipated. At the same time, they explain the source of the difficulty to formally relate the semantics of default extensions by Reiter and autoepistemic expansions by Moore. These two semantics occupy different locations in the corresponding families of semantics for default and autoepistemic logics. © 2002 Elsevier Science B.V. All rights reserved., SCOPUS: ar.j, info:eu-repo/semantics/published

We revisit the issue of epistemological and semantic foundations for autoepistemic and default logics, two leading formalisms in nonmonotonic reasoning. We develop a general semantic approach to autoepistemic and default logics that is based on the notion of a belief pair and that exploits the lattice structure of the collection of all belief pairs. For each logic, we introduce a monotone operator on the lattice of belief pairs. We then show that a whole family of semantics can be defined in a systematic and principled way in terms of fixpoints of this operator (or as fixpoints of certain closely related operators). Our approach elucidates fundamental constructive principles in which agents form their belief sets, and leads to approximation semantics for autoepistemic and default logics. It also allows us to establish a precise one-to-one correspondence between the family of semantics for default logic and the family of semantics for autoepistemic logic. The correspondence exploits the modal interpretation of a default proposed by Konolige. Our results establish conclusively that default logic can be viewed as a fragment of autoepistemic logic, a result that has been long anticipated. At the same time, they explain the source of the difficulty to formally relate the semantics of default extensions by Reiter and autoepistemic expansions by Moore. These two semantics occupy different locations in the corresponding families of semantics for default and autoepistemic logics. © 2002 Elsevier Science B.V. All rights reserved., SCOPUS: ar.j, info:eu-repo/semantics/published

Commonsense reasoning is the reasoning of agents interacting with the real world. Non monotonic reasoning is a well developed research area gathering the logical formalisms that treat commonsense reasoning. One of the best known of such formalisms is Default logic. In this paper we discuss Default logic at both the proof-theoretic and semantics levels and show that Default logic provides a clear and formal framework to understand the logical nature of commonsense reasoning.

Default logic is a formal means of reasoning about defaults: what normally is the case, in the absence of contradicting information. Autoepistemic logic, on the other hand, is meant to describe the consequences of reasoning about ignorance: what must be true if a certain fact is not known. Although the motivation and formal character of these two systems are different, a closer analysis shows that they share a common trait, which is the indexical nature of certain elements in the theory. In this paper we compare the expressive power of the two systems. First, we give an effective translation of default logic into autoepistemic logic; default theories can thus be embedded into autoepistemic logic. We also present a more surprising result: the reverse translation is also possible, so that every set of sentences in autoepistemic logic can be effectively rewritten as a default theory. The formal equivalence of these two differing systems is thus established. This analysis gives an interpretive semantics to default logic, and yields insight into the nature of defaults in autoepistemic reasoning., This paper is a rewritten and expanded version of a preliminary report presented at International Joint Conference on Artificial Intelligence (10th), IJCAI87, presented at Milan, Italy in Aug 1987 and published in proceedings of the same, v1, p394-400.

When we work with information from multiple sources, the formats of the knowledge bases may not be uniform. It would be desirable to be able to combine a knowledge base of default rules with one containing autoepistemic formulas. Previous works on relating default logic and autoepistemic logic mostly impose some constraints on autoepistemic logic, and thus are not suitable for combining the two logics. We first present a fixed point formulation of autoepistemic logic analogous to that of default logic. Then we introduce a possible world framework with a partition structure, which corresponds to our intuitive notion of accessibility as linking alternate ``possible'' worlds. We show that both default logic and autoepistemic logic can be characterized using this framework, and the constraints imposed on the possible world structures correspond to the requirements in the fixed point formulations. Casting both default logic and autoepistemic logic in a common framework is important for developing a semantics applicable to the two logics, both separately and combined.

The goal of this paper is to frame a theory of reasons--what they are, how they support actions or conclusions--using the tools of default logic. After sketching the basic account of reasons as provided by defaults, I show how it can be elaborated to deal with two more complicated issues: first, situations in which the priority relation among defaults, and so reasons as well, is itself established through default reasoning; second, the treatment of undercutting defeat and exclusionary reasons. Finally, and by way of application, I show how the resulting account can shed some light on Jonathan Dancy's argument from reason holism to a form of extreme particularism in moral theory., Philosopher's Imprint: vol. 7, no. 3, (dlps) 3521354.0007.003, http://hdl.handle.net/2027/spo.3521354.0007.003, This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License. Please contact mpub-help@umich.edu to use this work in a way not covered by the license.

When we work with information from multiple sources, the formats of the knowledge bases may not be uniform. It would be desirable to be able to combine a knowledge base of default rules with one containing autoepistemic formulas. Previous works on relating default logic and autoepistemic logic mostly impose some constraints on autoepistemic logic, and thus are not suitable for combining the two logics. We first present a fixed point formulation of autoepistemic logic analogous to that of default logic. Then we introduce a possible world framework with a partition structure, which corresponds to our intuitive notion of accessibility as linking alternate ``possible'' worlds. We show that both default logic and autoepistemic logic can be characterized using this framework, and the constraints imposed on the possible world structures correspond to the requirements in the fixed point formulations. Casting both default logic and autoepistemic logic in a common framework is important for developing a semantics applicable to the two logics, both separately and combined.

The goal of this paper is to frame a theory of reasons--what they are, how they support actions or conclusions--using the tools of default logic. After sketching the basic account of reasons as provided by defaults, I show how it can be elaborated to deal with two more complicated issues: first, situations in which the priority relation among defaults, and so reasons as well, is itself established through default reasoning; second, the treatment of undercutting defeat and exclusionary reasons. Finally, and by way of application, I show how the resulting account can shed some light on Jonathan Dancy's argument from reason holism to a form of extreme particularism in moral theory., Philosopher's Imprint: vol. 7, no. 3, (dlps) 3521354.0007.003, http://hdl.handle.net/2027/spo.3521354.0007.003, This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License. Please contact mpub-help@umich.edu to use this work in a way not covered by the license.