Search

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.

International audience; In this article we propose a decision process integrating Non-Monotonic Reasoning (NMR), embedded in a deliberative architecture. The NMR process uses Default Logic to implement goal reasoning, managing partially observable or incomplete information, allowing the design of default behaviours completed by the handling of specific situations, in order to manage the current mission objective as well as safety rules. We illustrate our approach through an application of an underwater robot performing a marine biology mission.

Tremendous research effort has been dedicated over the years to thoroughly investigate non-monotonic reasoning. With the abundance of non-monotonic logical formalisms, a unified theory that enables comparing the different approaches is much called for. In this paper, we present an algebraic graded logic we refer to as LogAG capable of encompassing a wide variety of non-monotonic formalisms. We build on Lin and Shoham's argument systems first developed to formalize non-monotonic commonsense reasoning. We show how to encode argument systems as LogAG theories, and prove that LogAG captures the notion of belief spaces in argument systems. Since argument systems capture default logic, autoepistemic logic, the principle of negation as failure, and circumscription, our results show that LogAG captures the before-mentioned non-monotonic logical formalisms as well. Previous results show that LogAG subsumes possibilistic logic and any non-monotonic inference relation satisfying Makinson's rationality postulates. In this way, LogAG provides a powerful unified framework for non-monotonicity., Comment: In Proceedings TARK 2019, arXiv:1907.08335

Urban route planning is important for smart cities and intelligent transportation systems. Most of the exiting methods of urban route planning are either graph based search algorithms or optimization methods, however they show many weaknesses in real-world applications due to their high computational complexities and needs for global information of urban environments. To solve this problem, we propose a novel Recurrent Neural Network (RNN) based default logic for route planning. The proposed method is composed of three parts. The first part is the default theory of route planning, forcing no loops in the generated routes. The second part is the RNN based default reasoning to recommend default rules. The RNN outputs the probability distribution of the defaults used next, so the proposed method is a probabilistic method. The third part is the update algorithm of map models to improve the accuracy of default reasoning in dynamic environments. Training the proposed RNN is simple because no statistic computation is required for training. The time complexity of the proposed method during testing is just O(ρ2), where ρ is the length of the optimal route for two given nodes. To evaluate the proposed method, we build a new map model named BJ simulating the complex urban environments of the Beijing city, China. Extensive experiments on the BJ map model in both static and dynamic environments show the effectiveness and accuracy of the proposed method.

In this paper, we propose a computational model of human behavior events analysis that integrates perceptual causality. Design and establish a causal rule representation method based on default logic, which provides a concise syntax and semantic formal tool for potential causality. Through the analysis of the internal structure of the event, the technical framework of causality with the smallest action unit as the entity is established, which makes the traditional different entities, objects, events, states and actions naturally interrelated. By establishing the perceptual causal relationship between human goals and objects, events, reasoning the intention of human goals, and predicting their behavior, it can effectively solve the problem of human action occlusion and action error detection. The effectiveness of this method is evaluated on a new video dataset.

This study aims to model traffic flow under weak lane based heterogonous (mixed) traffic conditions. Unlike homogeneous traffic, when a follower (subject) vehicle in mixed traffic moves closer to its leader vehicle, it tends to adjust its longitudinal movement or change its lane and acts discretely. Due to this phenomenon, traffic flow modeling under such conditions is always challenging. A new driver behavioral logic is conceptualized for the vehicles' movement within a combination of surrounding vehicles. In which the following behavior was dissected with the lateral shift distance between vehicles. Two car-following models for homogeneous traffic conditions, the IDM and Gipps models were adapted with relevant lateral behavior parameters to different vehicle classes under mixed-traffic conditions. The new driving behavior logic was incorporated externally in place of default logic. The results showed that the performance of the adapted models was better accurate than the classical models.

Given a default theory \((\Delta ,D),\) where \(\Delta \) is a theory in propositional logic and D is a set of defaults, we will define three kinds of the minimal change in default logic: a theory \(\Theta \) is a \(\subseteq \)-/\(\preceq \)-/\(\vdash _\preceq \)-minimal change of D by \(\Delta ,\) where \(\Theta \) is a \(\subseteq \)-minimal change of D by \(\Delta \) if and only if \(\mathrm{Th}(\Theta \cup \Delta )\) is an extension of \((\Delta ,D).\) \(\preceq \)-minimal change has the actual importance. For example, let \((\Delta ,D)\) be a default theory, where \(\Delta \) says that someone is a human (denoted by p) and this man has no arms (denoted by \(\lnot q\)); and D contains one default \(\dfrac{p:q\wedge r}{q\wedge r},\) which says that a man defaultly has arms and legs, where r denotes that this man has legs. By default logic, \((\Delta ,D)\) has an extension \(\{p\},\) that is, we know that this man is a human.

Since its inception, logic has studied the acceptable rules of reasoning, the rules that allow us to pass from certain statements, serving as premises or assumptions, to a statement taken as a conclusion [...]

A brief idea

Default logic is one of the basic formalisms for nonmonotonic reasoning, a well-established area from logic-based artificial intelligence dealing with the representation of rational conclusions, which are characterised by the feature that the inference process may require to retract prior conclusions given additional premisses. This nonmonotonic aspect is in contrast to valid inference relations, which are monotonic. Although nonmonotonic reasoning has been extensively studied in the literature, only few works exist dealing with a proper proof theory for specific logics. In this paper, we introduce sequent-type calculi for two variants of default logic, viz., on the one hand, for three-valued default logic due to Radzikowska, and on the other hand, for disjunctive default logic, due to Gelfond, Lifschitz, Przymusinska, and Truszczyński. The first variant of default logic employs ukasiewicz’s three-valued logic as the underlying base logic and the second variant generalises defaults by allowing a selection of consequents in defaults. Both versions have been introduced to address certain representational shortcomings of standard default logic. The calculi we introduce axiomatise brave reasoning for these versions of default logic, which is the task of determining whether a given formula is contained in some extension of a given default theory. Our approach follows the sequent method first introduced in the context of nonmonotonic reasoning by Bonatti, which employs a rejection calculus for axiomatising invalid formulas, taking care of expressing the consistency condition of defaults.

Default Logic refers to a family of formalisms designed to carry out non-monotonic reasoning over a monotonic logic (in general, Classical First-Order or Propositional Logic). Traditionally, default logics have been defined and dealt with via syntactic consequence relations. Here, we introduce a family of default logics defined over modal logics. First, we present these default logics syntactically. Then, we elaborate on an algebraic counterpart. We do the latter by extending the notion of a modal algebra to acommodate for the main elements of default logics: defaults and extensions. Our algebraic treatment of default logics concludes with an algebraic completeness result. To our knowledge, our approach is novel, and it lays the groundwork for studying default logics from a dynamic logic perspective.

This chapter addresses the main approaches to formalization of default reasoning in first-order framework. The first part of the chapter overviews the historical development of nonmonotonic reasoning systems. After discussing three wellknown early formalisms (Default Logic, Nonmonotonic modal logic and Circumscription), we focus on nonmonotonic consequence relations and their close connections with conditional logics and probabilistic reasoning systems. The logic \( \mathit L ^{P,\mathbb I}_{\mathit \omega\omega}\) ww occupies the central position in this chapter. This logic extends classical first-order logic with a list of Keisler-style conditional probability quantifiers with the intention to express statistical knowledge as well as approximate probabilities. We provide a sound and complete deductive system with respect to semantics based on first-order structures endowed with suitable probability spaces. In addition, we describe two decidable fragments of \( \mathit L ^{P,\mathbb I}_{\mathit \omega\omega}\) ww that seem to be rich enough for many practical purposes. Finally, we discuss how the logic \( \mathit L ^{P,\mathbb I}_{\mathit \omega\omega}\) ww and its suitable extensions can be used to model default reasoning and analyze some properties of nonmonotonic consequence relations in the light of probabilistic inference.

In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension ( Cons ). Our algorithm can even be used to enumerate all generating defaults ( EnumSD ) that lead to stable extensions. We show that our algorithm decides Cons in linear time in the input theory and triple exponential time in the treewidth Further, our algorithm solves EnumSD with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions. Finally, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for Cons .

In nonmonotonic reasoning there are the problems of inconsistency and incoherence in general, and in default reasoning there may be only one trivial extension or no extension in special. We propose the restricted semantics of four-valued logic for default reasoning to resolve the problems of inconsistency and incoherence and in the meantime retain classical extensions in the presence of consistency and coherency. The restricted semantics can maintain both the expressiveness and reasoning ability of default logic. We provide a transformation approach to compute the restricted extensions by reducing them into classical ones.

In this paper we study the complexity of deontic logics grounded on norm-based semantics and apply norm-based deontic logic to access control. Four principal norm-based deontic logics have been proposed so far: imperative logic, input/output logic, deontic default logic and deontic defeasible logic. We present the readers that imperative logic is complete for the 2ed level of the polynomial hierarchy and deontic default logic is located in the 3ed level of the polynomial hierarchy. We then show how it is possible to impose restrictions to imperative logic such that the complexity goes down to be tractable, allowing the logic to be used in practical applications. We focus on a specific application: access control.

In inductive learning of a broad concept, an algorithm should be able to distinguish concept examples from exceptions and noisy data. An approach through recursively finding patterns in exceptions turns out to correspond to the problem of learning default theories. Default logic is what humans employ in common-sense reasoning. Therefore, learned default theories are better understood by humans. In this paper, we present new algorithms to learn default theories in the form of non-monotonic logic programs. Experiments reported in this paper show that our algorithms are a significant improvement over traditional approaches based on inductive logic programming., Comment: Paper presented at the 33rd International Conference on Logic Programming (ICLP 2017), Melbourne, Australia, August 28 to September 1, 2017 16 pages, LaTeX, 3 PDF figures (arXiv:YYMM.NNNNN)

John Horty has proposed an approach to reasoning with ought-propositions which stands in contrast to the standard modal approach to deontic logic. Horty’s approach is based on default theories as known from the framework of Default Logic. It is argued that the approach cannot be extended beyond the most simple kinds of default theories and that it fails in particular to account for conditional obligations. The most plausible ways of straightening out the defects of the approach conform to a simple theory of default reasoning in standard deontic language.

Situation identification and its analysis lead to some situation-aware state of knowledge. Uncertainties occur during this process and vastly influence the advice or alerts generated or recommendations attained. A common methodological framework based on non-monotonic logic will greatly help in the formalization and mitigation of situation awareness. The default logic allows reasoning under uncertainty along with reasoning with incomplete information, hence found the best candidate to deal with non-monotonic logic. This paper provides an approach for the study of the non-monotonicity of human commonsense reasoning, specifically for concepts like psychological prototypes and the philosophical Natural Kinds by exploiting semantic web technologies. Providing a quick at the same time right decision-support greatly depends upon the apprehension of the situation. We provide ways to perceive the reality timely, analyze it using past experiences, anticipate and predict next steps and possible actions for subsequent decision making and performance. Ordinarily, decision-makers pay attention to knowledge abstractions while taking a little notice of lower-level details. Making the end users not only identify the situation but getting aware of it will fetch all the benefits. We have utilized a hybrid of top-down and bottom-up reasoning along with the Case-based and rule-based reasoning to bestow decision support in the domain of man-made emergencies.

We build a Default Logic variant on Intuitionistic Propositional Logic and develop a sound, complete, and terminating, tableaux calculus for it. We also present an implementation of the calculus. We motivate and illustrate the technical elements of our work with examples.

Sequent-type proof systems constitute an important and widely-used class of calculi well-suited for analysing proof search. In this paper, we introduce a sequent-type calculus for a variant of default logic employing Łukasiewicz’s three-valued logic as the underlying base logic. This version of default logic has been introduced by Radzikowska addressing some representational shortcomings of standard default logic. More specifically, our calculus axiomatises brave reasoning for this version of default logic, following the sequent method first introduced in the context of nonmonotonic reasoning by Bonatti, which employs a complementary calculus for axiomatising invalid formulas, taking care of expressing the consistency condition of defaults.

We investigate interpolation and Beth definability in default logics. To this end, we start by defining a general framework which is sufficiently abstract to encompass most of the usual definitions of a default logic. In this framework a default logic \(\mathscr {D}\mathfrak {L}\) is built on a base, monotonic, logic \(\mathfrak {L}\). We then investigate the question of when interpolation and Beth definability results transfer from \(\mathfrak {L}\) to \(\mathscr {D}\mathfrak {L}\). This investigation needs suitable notions of interpolation and Beth definability for default logics. We show both positive and negative general results: depending on how \(\mathscr {D}\mathfrak {L}\) is defined and of the kind of interpolation/Beth definability involved, the property might or might not transfer from \(\mathfrak {L}\) to \(\mathscr {D}\mathfrak {L}\).

In this article we present an approach for representing a resilient system which has the capability of absorb perturbations and overcome a disaster. A framework called KOSA is depicted, which is a world that contains a set of knowledge describing objectives, states and actions, linked by a set of rules. This link is expressed by a default theory. First, we define resilience as a relation among states and objectives. Secondly, from a given state, extensions are calculated, which provides information where to go to the future state. The connection, among two or more states creates different configurations that we call trajectories. These connections represent an evolution of the knowledge. Consequently, this reveals the existence of a resilient trajectory. Examples of piloting an airplane are concerned through this paper. Eventually, we present a discrete theoretical behavior of the complete model. Finally the notion of distance among extensions is introduced.

Monotonicity is a property of the consequence relation of classical logic, which has been questioned for a range of reasons, some of which we overview. Default logic, which is a non-monotonic logic, was introduced to model defeasible conclusions that may be justified by default rules. In this paper, we scrutinize certain features of non-monotonicity of a consequence relation to legitimize it. The logic of first-degree entailments, which makes more distinctions than 2-valued logics does is especially suitable as the base logic for a system of default logic, because the applicability of default rules depends on the absence of formulas from a theory. We define two notions of extensions with default rules and illustrate their use by some standard as well as new examples.

In this article we present an implementation of non-monotonic reasoning in an embedded system. As a part of an autonomous motor-glider, it simulates piloting decisions of an airplane. A real pilot must take care not only about the information arising from the cockpit (airspeed, altitude, variometer, compass...) but also from outside the cabin. Throughout a flight, a pilot is constantly in communication with the control tower to follow orders, because there is an airspace regulation to respect. In addition, if the control tower sends orders while the pilot has an emergency, he may have to violate these orders and airspace regulations to solve his problem (e.g. emergency landing). On the other hand, climate changes constantly (wind, snow, hail..) and can affect the sensors. All these cases easily lead to contradictions. Switching to reasoning under uncertainty, a pilot must make decisions to carry out a flight. The objective of this implementation is to validate a non-monotonic model which allows to solve the question of incomplete and contradictory information. We formalize the problem using default logic, a non-monotonic logic which allows to find fixed-points in the face of contradictions. For the implementation, the Prolog language is used in an embedded computer running at 1 GHz single core with 512 Mb of RAM and 0.8 watts of energy consumption., Comment: In Proceedings ICLP 2019, arXiv:1909.07646

This thesis presents a resilient model to pilot an aircraft based on a non-monotonic logic. This model is capable of handling solutions from incomplete, contradictory information and exceptions. This is a very well known problem in the field of Artificial Intelligence, which has been studied for more than 40 years. To do this, we use default logic to formalise the situation and find possible actions. Thanks to this logic we can transform the piloting rules to defaults. Then, when we calculate the solutions, several options could result. At this point an opportunistic deci- sion criteria takes place to choose the better solution. The control of the system is done via the property of resilience, we redefine this property as the integration of the non-monotonic logic in the Minsky’s model. As a result, it is shown that the proposed resilient model could be generalised to systems that incorporate a knowledge of the world that contains situations, objectives and actions. Finally, we present the experimental results and conclusion of the thesis discussing the prospects and challenges that exist for future directions. Different applications in other fields are taken into account for the interest of the model’s behavior.; Esta tesis presenta un modelo resistente para pilotar un avión basado en una lógica no monótona. Este modelo es capaz de manejar soluciones a partir de informaciones incompletas, contradictorias y excepciones. Este es un problema muy conocido en campo de la Inteligencia Artificial, que se ha estudiado durante más de 40 años. Para hacer esto, usamos la lógica por defectos para formalizar la situación y encontrar posibles acciones. Gracias a esta lógica, podemos transformar las reglas de pilotaje en defectos. Luego, cuando calculamos las soluciones, pueden surgir varias opciones. En este punto, tiene lugar un criterio de decisión oportunista para elegir la mejor solución. El control del sistema se realiza a través de la propiedad de resiliencia. Redefinimos esta propiedad como la integración de la lógica no monótona en el modelo de Minsky. Como resultado, se muestra que el modelo resistente propuesto podría generalizarse a sistemas que incorporan un conocimiento del mundo que contiene situaciones, objetivos y acciones. Finalmente, presentamos los resultados experimentales y la conclusión de la tesis sobre las perspectivas y los desafíos que existen para futuras direcciones. Se tienen en cuenta diferentes aplicaciones en otros campos para el interés del comportamiento del modelo.; Cette thèse présente un modèle résilient pour piloter un avion basé sur une logique non monotone. Ce modèle est capable de gérer des solutions à partir d’informations incomplètes, contradictoires et des exceptions. C’est un problème très connu dans le domaine de l’Intelligence Artificielle, qui est étudié depuis plus de 40 ans. Pour ce faire, nous utilisons la logique des défauts pour formaliser la situation et trouver des actions possibles. Grâce à cette logique, nous pouvons transformer les règles de pilotage en défauts. Ensuite, lorsque nous calculons les solutions, plusieurs options peuvent en résulter. À ce stade, il existe un critère de décision opportuniste pour choisir la meilleure solution. Le contrôle du système se fait via la propriété de résilience. Nous redéfinissons cette propriété comme l’intégration de la logique non-monotone dans le modèle de Minsky. En conséquence, il est démontré que le modèle de résilience proposé pourrait être généralisé aux systèmes intégrant une connaissance du monde contenant des situations, des objectifs et des actions. Enfin, nous présentons les résultats expérimentaux et la conclusion de la thèse en discutant des perspectives et des défis pour les orientations futures. Différentes applications dans d’autres domaines sont prises en compte pour l’intérêt du comportement du modèle.

The goal of this paper is to present a prospective way to ‘translate’ normal default rules into the framework of action models logic. At the beginning we introduce default logic and normal default logic with their main properties and, separately, action models logic. Then a ‘translation’ of normal default rules in a slightly modified action models logic is presented.

This chapter is concerned with the question of what unifies reasons for action and reasons for belief, sometimes called practical and epistemic reasons. According to some views, reasons for belief are a special case of reasons to do something, and so epistemic reasons are a special case, very broadly speaking, of practical reasons. According to other views, reasons for action are a special case of reasons to draw some conclusion, and so practical reasons are a special case of epistemic reasons. This chapter considers some of the evidence that bears on whether either of these claims is correct, or whether instead practical and epistemic reasons have something else in common.

The structure-preference (SP) order is a way of defining argument preference relations in structured argumentation theory that takes into account how arguments are constructed. The SP order was first introduced in the context of endowing Brewka’s prioritised default logic (PDL) with sound and complete argumentation semantics. In this paper, we further articulate the underlying intuitions of the SP order in terms of how an agent should construct arguments. We also compare the SP order to other argument preference relations and illustrate the different results one would obtain. Finally, we prove that the SP order allows for the original version of PDL to satisfy Brewka’s and Eiter’s postulates.

We define a logic of default justifications that relies on operational semantics. One of the key features that is absent in standard justification logics is the possibility to weigh different epistemic reasons or pieces of evidence that might conflict with one another. To amend this inadequacy, we develop a semantics for “defeaters”: conflicting reasons forming a basis to doubt the original conclusion or to believe an opposite statement. Our logic is able to address interactions of normal defaults without relying on priorities among default rules and introduces the possibility of extension revision for normal default theories.

We define a logic of default justifications that relies on operational semantics. One of the key features that is absent in standard justification logics is the possibility to weigh different epistemic reasons or pieces of evidence that might conflict with one another. To amend this inadequacy, we develop a semantics for “defeaters”: conflicting reasons forming a basis to doubt the original conclusion or to believe an opposite statement. Our logic is able to address interactions of normal defaults without relying on priorities among default rules and introduces the possibility of extension revision for normal default theories.

We define a logic of default justifications that relies on operational semantics. One of the key features that is absent in standard justification logics is the possibility to weigh different epistemic reasons or pieces of evidence that might conflict with one another. To amend this inadequacy, we develop a semantics for “defeaters”: conflicting reasons forming a basis to doubt the original conclusion or to believe an opposite statement. Our logic is able to address interactions of normal defaults without relying on priorities among default rules and introduces the possibility of extension revision for normal default theories.

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.

In this paper, we study Reiter’s propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (Ext). Our algorithm can even be used to enumerate all generating defaults (EnumSE) that lead to stable extensions. We show that our algorithm decides Ext in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves EnumSE with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.

This paper put forward constrained epistemic action model logic (EAML), which extended the action modal logic and reason epistemic default logic in the dynamic epistemic theory framework. In this paper, the constrained epistemic default logic and action model logic was combined to model the dynamic cognitive update process by introducing a cognitive operator. As constrained epistemic default logic restricts the current possible epistemic state and action model logic can describe epistemic actions, the new proposed logic can better portray the cognitive operations and the restriction of the corresponding accessibility relations. The description of the logic framework was given in this study, and the related theorems were proved to show the interpretation of the constrained epistemic action model logic.

We investigate the application of Courcelle's theorem and the logspace version of Elberfeld et al. in the context of non-monotonic reasoning. Here we formalize the implication problem for propositional sets of formulas, the extension existence problem for default logic, the expansion existence problem for autoepistemic logic, the circumscriptive inference problem, as well as the abduction problem in monadic second order logic and thereby 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 XPnu, resp., XLnu) under standard complexity assumptions.

We study the tractability frontier of outlier detection problems, by analyzing it with respect to (i) the considered outlier detection problem, (ii) the reference default logic fragment, and (iii) the adopted notion of outlier. As for point (i), we shall consider three problems of increasing complexity, called Outlier-Witness Recognition, Outlier Recognition and Outlier Existence, respectively. As for point (ii), as we look for conditions under which outlier detection can be done efficiently, attention will be limited to subsets of Disjunction-free propositional default theories. As for point (iii), we shall refer to both the notion of outlier introduced in [3] and a new and more restrictive one, called strong outlier. We also present a polynomial time algorithm for enumerating all strong outliers of bounded size in a quasi-acyclic normal unary default theory. Some of our tractability results rely on the Incremental Lemma that provides conditions for a default logic fragment to have a monotonic behavior. Finally, in order to show that the simple fragments of DL we deal with are still rich enough to solve interesting problems and, therefore, that the tractability results that we prove are interesting not merely on the theoretical side, insights into the expressive capabilities of these fragments are provided, by showing that normal unary theories express all NL queries, hereby indirectly answering a question raised by Kautz and Selman [16] .

I begin by reviewing classical semantics and the problems presented by normative conflicts. After a brief detour through default logic, I establish some connections between the treatment of conflicts in each of these two approaches, classical and default, and then move on to consider some further issues: priorities among norms, or reasons, conditional oughts, and reasons about reasons.

Human non-conscious reasoning is one of the most successful procedures developed to solve everyday problems in an efficient way. This is why the field of artificial intelligence should analyze, formalize and emulate the multiple ways of non-conscious reasoning with the purpose of applying them in knowledge based systems, neurocomputers and similar devices for aiding people in the problem-solving process. In this paper, a framework for those non-conscious ways of reasoning is presented based on object-oriented representations, fuzzy sets and multivalued logic.

National audience; Le pilotage d'un avion à différentes étapes de vol est un problème de logique non monotone. Parce que les règles de pilotage peuvent changer en fonction des circonstances ex-ternes, telles que les perturbations atmosphériques ou les situations de sécurité ou d'urgence du pilote. Nous présen-tons une méthodologie pour mener un vol stable prenant en compte des facteurs d'incertitude et de contradiction des informations.

In propositional normal default logic, given a default theory (Δ,D) and a well-defined ordering of D, there is a method to construct an extension of (Δ,D) without any injury. To construct a strong extension of (Δ,D) given a well-defined ordering of D, there may be finite injuries for a default δ ∈ D. With approximation deduction ⊢s in propositional logic, we will show that to construct an extension of (Δ,D) under a given welldefined ordering of D, there may be infinite injuries for some default δ ∈ D.

International audience; In this article we study the case of an autonomous motor-glider. The aims of the aircraft is to maintain its flight as long as possible, taking advantage of the rising air from the ground, known as thermals, despite of limited energy resources and possible external influences, such as turbulences. The pilot task being to make decisions with incomplete, uncertain or even contradictory information, as well as driving to the desired path or destination. We propose the formulation of a model from the point of view of logical theory, using non-monotonic logic and more specifically default logic, to tackle these problems. Finally, we present the results of a simulation for further application in a glider(reduced model) which use solar cells for power management in embedded system.

Formal semantic theories are designed to explain how it is possible to produce and understand an infinite number of sentences on the basis of a finite lexicon and a finite number of composition rules. According to this architecture, language comprehension completely proceeds in a bottom-up fashion only driven by linear linguistic input thereby leaving no room for a predictive component which allows to make expectations about upcoming words. This is in stark contrast to neurophysiological research in the past decades on online semantic processing which has provided ample evidence that prediction plays indeed an indispensable role in language comprehension the brain as a prediction machine, [Ber10]. In this article, we present an extension of formal semantic theory that allows to make predictions of upcoming words. The basic intuition is: predictions are based on incomplete information. Drawing defeasible conclusions based on such information can be modeled by default reasoning. Since predictions can go wrong, a second strategy for retracting wrong guesses is needed in order to integrate unexpected words into the prior context. This is modeled by belief revision. We model both processing stages, making predictions about upcoming words and integrating them into the prior context, and relate the models to the empirical findings in neurophysiological research.

Cantonese has a number of sentence-final particles which serve various communicative functions. This paper looks into two of the most frequently used particles, wo3 and lo1. We propose that wo3 and lo1 are expressive items: Wo3 indicates unexpectedness of the propositional content or the current discourse move, while lo1 indicates expectedness of the propositional content or the current discourse move. We employ Default Logic to characterize the notion of (un)expectedness by normality conditionals. The analysis has a further implication on the Gricean Cooperative Principle in that the use of wo3 and lo1 makes reference to the general world knowledge which includes conditions on how the discourse should normally proceed.

Case-based reasoning is, without question, a puzzle. When students are taught to “think like lawyers” in their first year of law school, they are taught case-based common-law reasoning. Books on legal reasoning are devoted almost entirely to the topic. How do courts reason from one case to the next? Is case-based reasoning reasoning from analogy? How should case-based reasoning be modeled? How can it be justified? In contrast, rule-based legal reasoning (as exemplified in much statutory reasoning) is taken as simple in legal scholarship. Statutory interpretation — how to determine the meaning of words in a statute, the relevance of the lawmakers’ intent, and so forth — is much discussed, but there is little treatment of the structure of statutory reasoning once the meaning of the words is established. Once the meaning of terms is established, statutory reasoning is considered, roughly speaking, to be deductive reasoning. This essay examines the structure of statutory reasoning after ambiguities are resolved and the meaning of the statute’s terms established. It argues that standard formal logic is not the best approach for representing statutory rule-based reasoning. Rather, the essay argues, using the Internal Revenue Code and accompanying regulations, judicial decisions, and rulings as its primary example, that at least some statutory reasoning is best characterized as defeasible reasoning — reasoning that may result in conclusions that can be defeated by subsequent information — and is best represented using default logic. The essay then addresses the practical and theoretical benefits of this alternative understanding of rule-based legal reasoning.

This is an expository article about the solution to the frame problem proposed in 1980 by Raymond Reiter. For years, his “frame default” remained untested and suspect. But developments in some seemingly unrelated areas of computer science—logic programming and satisfiability solvers—eventually exonerated the frame default and turned it into a basis for important applications.

Brewka's Cumulative Default Logic (CDL), a new version of Reiter's default logic, puts emphasis on the joint consistency among the justifications of all applied defaults to obtain cumulativity. In this paper, a finite characterization of CDL extensions using sets of generating defaults is given. From this characterization we derive new algorithms for various reasoning tasks in CDL. Moreover, we show that (propositional) cumulative default reasoning has the same complexity as classical default reasoning.

Research in NMR has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are nowadays the main tool for storing very large sets of data, the approach of using non-monotonic formalisms as relational database query languages has been investigated to a much smaller extent. In this work we propose a novel application of default logic by introducing a default query language (DQL) for finite relational databases, which is based on default rules. The main result of this paper is that DQL is as expressive as SO∃∀, the existential universal fragment of second order logic. This result is not only of theoretical importance: We show queries -which are useful in practice- that can be expressed with DQL and cannot with other query languages based on non-monotonic logics such as DATALOGstable Another result in this paper concerns the combined complexity of DQL, i.e., when it is assumed that the query is part of the input; for this problem, NEXPTIMENP-completeness is shown.