*************************
* AI DEPARTMENT SEMINAR *
*************************
Vendredi 19 Octobre 2018 à 14h30, salle des thèses
Célia da Costa Pereira (Univ. Nice Sophia Antipolis) "De la génération de buts dans les agents BDI à la recherche et fouille d'informations textuelles"
ABSTRACT. Nos actions sont souvent motivées par nos objectifs qui, eux, peuvent dépendre fortement de nos
croyances. Pour augmenter les chances de réaliser nos objectifs, nous tenons donc compte des
changements dans notre environnement en mettant d'abord à jour nos croyances et puis aussi nos
objectifs, si nécessaire. Les changements dans nos croyances sont dus, entre autres, à la prise
en compte de nouvelles informations venant de sources plus ou moins fiables. Ce processus peut
se vérifier dans plusieurs situations comme, par exemple, dans le cas où nous sommes à la recherche
d'informations.
Pendant ma présentation, je vais me focaliser sur deux thématiques de recherche auxquelles je me suis intéressée ces dernières années. La première concerne l'extension de l'architecture BDI (Belief-Desire-Intention) proposée par Rao et Georgeff. Le but de cette extension a été de proposer un formalisme pour la génération d'objectifs (les désirs que l'agent a décidé d'exhaucer) qui tient compte du fait que (i) les buts d'un agent ne sont pas toujours fixés à l'avance, (ii) qu'ils dépendent de ses croyances qui évoluent avec l'arrivée de nouvelles informations.
La deuxième thématique concerne le traitement de l'information textuelle. En particulier, je me suis intéressée (i) à la modélisation du comportement d'un agent en quête d'information, (ii) à l'extension de la définition de "pertinence" de façon à ce que les différents critères qui influencent le calcul de la pertinence soient pris en considération et, enfin, (iii) je me suis intéressée à la fouille des textes courts.
Pour conclure, je présenterai quelques pistes sur la façon de combiner les résultats de ces deux thématiques qui semblent n'avoir aucune liaison apparente, le but final étant d'améliorer la qualité d'un système de recherche d'information.
Vendredi 12 octobre a 14h30, salle du conseil
Elise Perrotin "A semantic approach to non-prioritized belief revision"
ABSTRACT. Belief revision is concerned with belief change fired by incoming information. Despite the variety of frameworks representing this process, most revision policies share one crucial feature: incoming information outweighs current information and hence, in case of conflict, the new information will prevail. However, if one is interested in representing the way actual humans revise their beliefs, one might not always want for the agent to blindly believe everything they are told.
We propose a semantic approach to non-prioritized revision in which the decision of whether to accept or reject the incoming information depends on how different the resulting model and the original one would be. The approach uses plausibility models in order to represent an agent’s beliefs. Then, when attempting to revise with respect to a given formula ?, the proposed screened revision obtains the distance between the original and updated models (with this distance between models given by the distance between their plausibility relations), returning the revised one when the distance is below or equal to a given threshold, and the original one otherwise.
This initial step leads to further developments. First, the threshold represents the agent’s stubbornness, but also their trust in the source of the information. From a more general perspective, it can be seen as a function indicating the trust the agent has in the elements of a given set of different sources. A more interesting aspect, which we are currently working on, is a shift from the given binary decision of acceptance or rejection to a more general setting in which a revision always occurs, and the threshold is used rather to choose the right revision for that input.
Lundi 24 sept. a 14h30, Salle des theses
Arianna Novaro (joint work with F. Belardinelli, U. Grandi, A. Herzig, D. Longin, E. Lorini, L. Perrussel) "Relaxing Exclusive Control in Boolean Games" (TARK 2017, https://arxiv.org/pdf/1707.08736.pdf)
ABSTRACT. In the typical framework for boolean games (BG) each player can change the truth value of some propositional atoms, while attempting to make her goal true. In standard BG goals are propositional formulas, whereas in iterated BG goals are formulas of Linear Temporal Logic. Both notions of BG are characterised by the fact that agents have exclusive control over their set of atoms, meaning that no two agents can control the same atom. In the present contribution we drop the exclusivity assumption and explore structures where an atom can be controlled by multiple agents. We introduce Concurrent Game Structures with Shared Propositional Control (CGS-SPC) and show that they account for several classes of repeated games, including iterated boolean games, influence games, and aggregation games. Our main result shows that, as far as verification is concerned, CGS-SPC can be reduced to concurrent game structures with exclusive control. This result provides a polynomial reduction for the model checking problem of specifications in Alternating-time Temporal Logic on CGS-SPC.
Lundi 10 sept. a 14h30, Salle 003
Emiliano Lorini "Logic of Desires, Part II: Explicit vs. Implicit Attitudes"
Vendredi 7 sept. a 14h30, Salle 003
Emiliano Lorini "Logic of Desires, Part I: From Beliefs to Desires, Part II: Explicit vs. Implicit Attitudes"
ABSTRACT. An important and general distinction in philosophy of mind is between epistemic attitudes and motivational attitudes. This distinction is in terms of the direction of fit of mental attitudes to the world. While epistemic attitudes aim at being true and their being true is their fitting the world, motivational attitudes aim at realization and their realization is the world fitting them. The philosopher John Searle calls "mind-to-world" the first kind of direction of fit and "world- to-mind" the second one. There are different kinds of epistemic and motivational attitudes with different functions and properties. Examples of epistemic attitudes are beliefs, knowledge and opinions, while examples of motivational attitudes are desires, preferences, moral values and intentions. The tutorial is aimed at discussing logics for modeling static and dynamic aspects of motivational attitudes whose most representative example is the logic of desires. It places special emphasis on the bipolar
aspect of motivational attitudes (i.e., attraction vs. repulsion) as well as on the connection between the logic of desires and the theory of reinforcement.
Jeudi 22 mars a 14H30, Salle des theses
Marcelo Esteban Coniglio (Department of Philosophy-IFCH and Centre for Logic, Epistemology and the History of Science CLE, State University of Campinas UNICAMP, Campinas, Brazil; joint work with F. Esteva, J. Gispert and L. Godo) "Maximality and strong maximality in the lattice of finite-valued Lukasiewicz logics"
ABSTRACT. In this talk the logics Ln,i obtained from the (n+1)-valued Lukasiewicz logics by taking the order filter generated by i/n as the set of designated elements, will be discussed. In particular, the relationship of maximality and strong maximality among them will be analysed. A very general theorem which states sufficient conditions for maximality between logics will be presented. As a corollary of this theorem it will be shown that Lp,i is maximal w.r.t. CPL whenever p is prime. Concerning strong maximality between the logics Ln,i (that is, maximality w.r.t. rules instead of axioms), algebraic arguments will be given in order to shown that Lp,i is not strongly maximal w.r.t. CPL, even for p prime. Indeed, there is just one extension-by-rules between Lp,i and CPL, obtained by adding to Lp,i a kind of ith graded explosion rule. The case of p=3 will be discussed in detail, presenting a 4-valued paraconsistent logic called J4 which generalizes the well-known 3-valued paraconsistent logic J3 introduced by D'Ottaviano and da Costa.
Vendredi 2 fevrier 2018 a 14h30, Salle des thèses
Eduardo Fermé "AGM 30 years"
This tutorial will overview the history of belief revision in the tradition of Alchourron, Gardenfors and Makinson.
Jeudi 14 dec. 2017 a 14h30, Salle des theses
Marie-Christine Lagasquie-Schiex "Enriched abstract argumentation graphs: A logical point of view" (slides in English, talk in French)
ABSTRACT. Initially (Dung, 1995), argumentation graphs were simple directed graphs, nodes corresponding to arguments and edges expressing attacks between two arguments. In this framework, the aim was to identify and compute sets of arguments (called extensions) representing coherent states of the world encoded by the graph. And finally, the conclusions of the argumentation process were defined, using these extensions.
Since 1995, several extensions of this framework have been defined producing enriched argumentation graphs. For instance:
- introduction of a new binary relation of support between arguments (so argumentation graphs can contain two kinds of edge);
- introduction of recursive interactions (so an edge can be defined from an argument to another edge).
Our present work consists in a logical formalization of argumentation graphs in order to allow for the representation and the exploitation of such enriched graphs. In a first step, we propose a logical encoding of a simple argumentation graph and the main principles used for identifying extensions.
Then this encoding is extended in order to take into account recursive attacks. That allows for the definition of new semantics for enriched graphs.
Vendredi 10 nov. a 14h15, Salle des theses
Philippe Balbiani "About strong non-contingency"
ABSTRACT. Past decades have witnessed a variety of research on logics with a sole primitive modality that is essentially a combination of another modality and boolean connectives. For instance, in non-contingency logic, a formula is noncontingent iff it is either necessarily true or necessarily false, whereas a formula is contingent iff it is possibly true and also possibly false; in the logic of essence and accident, a formula is essential iff once it is true, it is necessarily true, while a formula is accident iff it is true but possibly false. Despite being definable with known modalities such as necessity/belief, these modalities have philosophical interests in their own right, and deserve to be studied independently. Recently, Fan (2017) has introduced the notion of strong non-contingency by saying that a formula is strongly non-contingent iff it is necessarily true when it is true and it is necessarily false when it is false. This notion is related to Hintikka's treatment of question embedding verbs like `know', `remember'. The logic with strong non-contingency as a sole primitive modality, a non-normal modal logic, is less expressive than standard modal logic on various classes of models, and cannot define many usual frame properties including Euclideanity. This may invite technical difficulties and novelties in completely axiomatizing this new logic over various frames.
Vendredi 22 sept. a 14h15, Salle du Conseil
Emiliano Lorini "In Praise of Belief Bases: Doing Epistemic Logic without Possible Worlds"
ABSTRACT. We introduce a new semantics for a logic of explicit belief and implicit belief based on the concept of multi-agent belief base. Differently from existing Kripke-style semantics for epistemic logic in which the notions of possible world and doxastic/epistemic alternative are primitive, in our semantics they are non-primitive but are defined from the concept of belief base. We provide a complete axiomatization as well as a decidability result for our logic and study a variant in which the concept of belief is replaced by a concept of truthful knowledge.
Vendredi 30 juin a 14h15, Salle du Conseil
Mathieu Serrurier "The role of formal approaches in machine learning II" (first part: Vendredi 10 mars 2017)
slides:
https://www.irit.fr/~Andreas.Herzig/SemiThm4/201704_Serrurier_formalml.pdf
Jeudi 29 juin a 16h, Salle 001, IRIT (seminaire math-info)
Juan Pablo Aguilera (Vienna University of Technology) "The Infinite Epsilon Calculus"
ABSTRACT. The Epsilon Calculus is a formal framework designed by Hilbert as part of his foundational program. As we show, there is a natural way in which it can be generalized to incorporate expressions of countable length, e.g., statements of the form "x=0 or x=1 or x=2 or ...". We give an overview of the general theory of the Infinite Epsilon Calculus, focusing on its connection to infinite games and various mathematical axioms.
Mardi 27 juin 2017 a 14h15, salle 001
Emiliano Lorini "Exploring the bidimensional space: a dynamic logic approach"
Lundi 26 juin a 14h15, Auditorium de l'IRIT
Brian Epstein (Tufts University, USA) "Two ways of making the social world"
ABSTRACT. This talk sets out an organizing framework for the field of social ontology—the study of the nature of the social world. I discuss the subject matter of social ontology, and present a model aiming to clarify a variety of projects that have been traditionally confused with one another. The model helps explain and situate, for instance, varieties of individualism, theories of the building blocks of the social world, and theories of convention and collective intentionality. It is built on the distinction between two different inquiries: the study of the grounding of social facts, and the study of how social categories are “anchored” or set up. In the talk I explore these inquiries and discuss some applications.
Vendredi 23 juin a 14h15, salle des theses
Jean-Marie Lagniez (CRIL) "A Recursive Shortcut for CEGAR: Application to the Modal Logic K Satisfiability Problem"
ABSTRACT. Counter-Example-Guided Abstraction Refinement (CEGAR) has been very successful in model checking. Since then, it has been applied to many different problems. It is especially proved to be a highly successful practical approach for solving the PSPACE complete QBF problem. In this paper, we propose a new CEGAR-like approach for tackling PSPACE complete problems that we call RECAR (Recursive Explore and Check Abstraction Refinement). We show that this generic approach is sound and complete. Then we propose a specific implementation of the RECAR approach to solve the modal logic K satisfiability problem. We implemented both CEGAR and RECAR approaches for the modal logic K satisfiability problem within the solver MoSaiC. We compared experimentally those approaches to the state-of-the-art solvers for that problem. The RECAR approach outperforms the CEGAR one for that problem and also compares favorably against the state-of-the-art on the benchmarks considered.
Jeudi 22 juin a 16h, salle 001, IRIT (seminaire math-info)
Thibaut Godin (joint work with D. D'Angeli, I. Klimann, M. Picantin, and E. Rodaro) "Mealy automata: dynamic of the action, singular points and Wang tilings"
Mealy automata are a powerful tool to generate (semi)groups. Since the 80's, they have been used to solved several major conjectures in (semi)group theory. Although, people started to study them from a (theoretical) computer science perspective only recently. This approach is rich and brought many interesting results and questions.
In this talk, we focus on the dynamic of the action of the group on the regular tree and we show that classical tool from automata theory can be used to simplify and generalize known results and to provide information on this action. Then, we study a closely related problem and use a connection between Mealy automata and Wang tilings to obtain an undecidability theorem.
Vendredi 16 juin a 14h15, Salle des theses
Jorge Fandino "Causal Logic Programming"
Logic Programming (LP) and, in particular, Answer Set Programming are well-developed paradigms for Knowledge Representation and Reasoning. In this talk, we present an extensions of LP, so that causal information is included into the models of a program and used to reason with statements of the form “A has caused B." In particular, we studied causal semantics that are conservative extensions of the well-founded model and the stable model semantics. The causal information included in the models of a program can also be useful for providing justifications explaining why a given atom holds in a model.
Jeudi 15 juin a 14h15, Salle du Conseil
Sonia Marin "Focused nested proof systems for modal logics"
Nested sequents are a generalization of ordinary sequents to tree-like instead of list-like structures. They have been defined by Brünnler to give analytic proof systems to every modal logic in the S5-cube. That is, for each combination of the standard axioms d, t, b, 4, and 5, an equivalent set of inference rules in a nested sequent system can be obtained, such that, when added to the basic system for the modal logic K, the resulting system is sound and complete for the corresponding logic.
Focusing is a general technique initially defined by Andreoli for transforming a sequent proof system into one with a syntactic separation of non-deterministic choices without sacrificing completeness. This not only improves proof search, but also has the representational benefit of distilling sequent proofs into synthetic normal forms. We show how to apply the focusing technique to nested sequent calculi. We thus improve the reach of focusing to the logics of the modal S5 cube. Among our key contributions is a focused cut-elimination theorem for focused nested sequents, which is key to ensure completeness of focusing.
Vendredi 2 juin a 14h15, Salle des thèses
Arthur Bit-Monnot (LAAS) "Temporal and Hierarchical Models for Planning and Acting in Robotics"
ABSTRACT. The field of AI planning has seen rapid progress over the last decade and planners are now able to find plans with hundreds of actions in a matter of seconds. Despite those important progresses, robotic systems still tend to have a reactive architecture with very little deliberation on the course of the plan they might follow. In this talk, we propose novel models and techniques to handle the temporal and procedural knowledge that is critical for the deliberation of autonomous agents.
In a first part, we present a planning model and algorithm for temporal planning unifying the generative and hierarchical approaches. At the center of the model are temporal action templates, complemented with a specification of the initial state as well as the expected evolution of the environment over time. In addition, our model allows for the specification of procedural knowledge in the form of hierarchical actions, possibly with a partial coverage. Consequently, our model generalizes the existing generative and hierarchical approaches together with a rich time representation. We then introduce a constraint-based planning procedure suitable for our planning model. In order to support hierarchical features, the existing Partial-Order Causal Link approach is extended with the notions of task and decomposition. It is implemented in FAPE (Flexible Acting and Planning Environment) together with automated problem analysis techniques used for search guidance. We show FAPE to have performance competitive with state of the art temporal planners when used in a generative setting. The addition of hierarchical information leads to further performance gain.
In a second part, we study the usual methods used to reason on temporal uncertainty that is critical in many realistic scenarios. We relax the usual assumption of total observability and instead provide techniques to reason on the observations needed to maintain a plan executable. We show how such needed observations can be detected at planning time and incrementally dealt with by considering the appropriate sensing actions.
Finally we show how FAPE is used as a central component for the control of a robotic actor, taking advantage of the constraint-based representation for online plan adaptation and of its rich temporal model for execution monitoring.
Jeudi 1 juin, 16h, salle 001
Eduardo Hermo Reyes "Relational semantics and Turing progressions"
ABSTRACT. Turing progressions arise by iteratedly adding consistency statements to a base theory. Different notions of consistency give rise to different Turing progressions. In this talk, we will present a modal system (TSC) that generates principles that hold between the different Turing progressions under a natural arithmetical interpretation. We will also discuss the completeness of TSC w.r.t. a minor variation of Ignatiev's model for the closed fragment of Japaridze's provability logic GLP.
Vendredi 28 avril, 14h45, salle du conseil
Emiliano Lorini "Logics for Multi-Agent Systems: A Semantic Perspective" (tutorial at AAMAS 2017)
ABSTRACT: The tutorial will provide a general introduction to logics for modelling autonomous agents and multi-agent systems. This includes propositional dynamic logic (PDL), the logic of `seeing to it that' (STIT), the logic of `bringing it about that' (BIAT), coalition logic (CL), alternating-time temporal logic (ATL) and strategy logic (SL). During the tutorial we will also present some extensions of these logics by common sense `mentalistic' concepts such as knowledge, belief and preference.
Jeudi 16 mars, 14h, salle 001
Virginia and Frank Dignum "Interactions as Social Practices: towards a formalization"
ABSTRACT. Multi-agent models are a suitable starting point to model complex social interactions. However, as the complexity of the systems increase, we argue that novel modeling approaches are needed that can deal with inter-dependencies at different levels of society, where many heterogeneous parties (software agents, robots, humans) are interacting and reacting to each other. In this paper, we present a formalization of a social framework for agents based in the concept of Social Practices as high level specifications of normal (expected) behavior in a given social context. We argue that social practices facilitate the practical reasoning of agents in standard social interactions.
Vendredi 10 mars 2017, 14h30, salle 175
Mathieu Serrurier "The role of formal approaches in machine learning"
ABSTRACT. Statistical and numerical approaches, especially deep learning, dominate research in machine learning at the expense of formal approaches. However, the increasing needs of readability and interpretability in learning systems may change the story. In this seminar I will present briefly the background of machine learning. Then, I will present ways for machine learning to benefit from formal approaches.
Vendredi 3 mars 2017, 14h30, salle 175
Umberto Grandi (joint work with Ulle Endriss, ILLC Amsterdam) "Graph aggregation" (https://www.irit.fr/~Umberto.Grandi/publications/EndrissGrandiAIJ2017.pdf)
ABSTRACT. Graph aggregation is the process of computing a single output graph that constitutes a good compromise between several input graphs, each provided by a different source. One needs to perform graph aggregation in a wide variety of situations, e.g., when applying a voting rule (graphs as preference orders), when con solidating conflicting views regarding the relationships between arguments in a debate (graphs as abstract argumentation frameworks), or when computing a consensus between several alternative clusterings of a given dataset (graphs as equivalence relations). In this paper, we introduce a formal framework for graph aggregation grounded in social choice theory. Our focus is on understanding which properties shared by the individual input graphs will transfer to the output graph returned by a given aggregation rule. We consider both common properties of graphs, such as transitivity and reflexivity, and arbitrary properties expressible in certain fragments of modal logic. Our results establish several connections between the types of properties preserved under aggregation and the choice-theoretic axioms satisfied by the rules used. The most important of these results is a powerful impossibility theorem that generalises Arrow’s seminal result for the aggregation of preference orders to a large collection of different types of graphs.
Jeudi 2 mars, 14h, salle 175
Abdallah Saffidine (The University of New South Wales) "The (Parameterized) Complexity of (Positional) Games"
ABSTRACT. Classical Computational Complexity is a popular tool from Theoretical Computer Science used to characterize the difficulty of solving decision problems. I will present how a couple intuitive criteria allow one to guess the most likely complexity class of games of various sort. We'll then move to Parameterized Complexity which addresses some of the practical shortcomings of classical computational complexity and has seen increased adoption for studying graph-theoretic problems. I will describe ongoing work on building a better understanding of the Parameterized Complexity of Games. As an application, we'll show that Short Generalized Hex is W[1]-complete parameterized by the number of moves. This disproves a conjecture from Downey and Fellows' influential list of open problems from 1999.
BIO. Abdallah Saffidine is an ARC DECRA Fellow and a Research Associate at the University of New South Wales, Sydney, Australia. He works in the Artificial Intelligence and Algorithms groups. He arrived at UNSW in 2013 as a postdoc with Pr. Michael Thielscher and obtained his PhD from the Universite Paris-Dauphine, France, under the supervision of Pr. Tristan Cazenave. Abdallah has a wide range of interests from games, planning, and other areas of decision-making to logic, complexity and other areas of theory.
Vendredi 3 fev. 2017, 15h45, salle du conseil
Petar Iliev "An Introduction to Lower Bounds on Formula-size in Boolean and Modal Logic"
ABSTRACT. I am going to present a number of results and open questions related to the problem of proving lower bounds on the size of modal formulae defining properties of Kripke frames and models. To put things in perspective, I am going to start by giving an informal overview of some techniques used for proving lower bounds on the size of Boolean formulae and then I am going to show how to extend and apply them in the modal case. This is going to be an informal introduction to the area starting from first principles. Thus, the only real prerequisite for grasping the main ideas is familiarity with propositional truth-tables and Kripke models.
Vendredi 16 dec. 2016, 14h30, salle des theses
Gilles Richard "ILP = Logic + Machine learning"
ABSTRACT. Logic is everywhere and it is amazing to see that it can be used as a framework for (not so) effective machine learning algorithms. Instead of having a statistical approach, the viewpoint is coming from first order logic. While there are several types of logic, only a fragment of first order logic is easily amenable to an efficient automatic deduction process. Reversing this deduction process can be done via diverse techniques leading to inductive logic programming machineries: Progol is one of them and is formally based on inverse entailment. Extension to higher order logic and stochastic logic programs are also available. We will discuss these options as well. We will (try to) understand how it works and I hope we will have time for a demo. The guru in the field is Stephen Muggleton, currently Head of Computational Bioinformatics Laboratory at Imperial College and designer of Progol (http://wp.doc.ic.ac.uk/shm/). After all, "There is Nothing More Practical Than A Good Theory" (Kurt Lewin, 1890-1947).
Lundi Nov. 28 2016, Manufacture
Francesco Belardinelli "On Logics of Strategic Ability based on Propositional Control"
ABSTRACT. Recently logics for strategic ability have gained pre-eminence in the modelisation and analysis of game-theoretic scenarios. In this paper we provide a contribution to the comparison of two popular frameworks: Concurrent Game Structures (CGS) and Coalition Logic of Propositional Control (CL-PC). Specifically, we ground the abstract abilities of agents in CGS on Propositional Control, thus obtaining a class of CGS that has the same expressive power as CL-PC. We study the computational properties of this setting. Further, we relax some of the assumptions of CL-PC so as to introduce a wider class of computationally-grounded CGS.
Mardi 20 Oct. 2016, 14h, IRIT auditorium
Hector GEFFNER (Universitat Pompeu Fabra, Barcelona) "Planning in Artificial Intelligence: Heuristics, Models, and Transformations"
ABSTRACT. Planning in AI stands for the model-based approach to autonomy where actions are selected from a model of the actions, sensors, and goals. The main challenges in planning are computational, as all the models, whether accommodating feedback and uncertainty or not, are intractable in the worst case. In this talk, I'll review some the models considered in planning research and some of the ideas that have turned to be most useful computationally. I'll focus mainly on three threads from our own work on classical planning, planning with partial observability, and planning with nested beliefs in the presence of other agents.
Monday Sep. 19, 14h, salle des theses
Mark Ryan (Univ. Birmingham) "Reconciling online privacy and societal security"
ABSTRACT. Privacy is a core human need, but society sometimes has the requirement to do targeted, proportionate investigations in order to provide security. To reconcile individual privacy and societal security, we explore whether we can have surveillance in a form that is verifiably accountable to citizens. This means that citizens get verifiable proofs of the quantity and nature of the surveillance that actually takes place. In our scheme, governments are held accountable for the extent to which they exercise their surveillance power, and political parties can pledge in election campaigns their intention about reducing (or increasing) this figure.
We propose a general idea of {\em accountable escrow} to reconciling and balancing the requirements of individual privacy and societal security. We design a balanced crypto system for asynchronous communication (e.g., email). We propose a novel method for escrowing the decryption capability in public-key cryptography. A government can decrypt it in order to conduct targeted surveillance, but doing so necessarily puts records in a public log against which the government is held accountable. This means that citizens get verifiable proofs of the quantity and nature of the surveillance that actually takes place. Political parties can pledge in election campaigns their intention about reducing (or increasing) this figure.
Thursday June 16, 14h, room 001
Yan Zhang (Western Sydney University, Australia) "Existential Rule Languages with Finite Chase: Complexity and Expressiveness"
Tuesday June 7, 14h, salle des theses de l'IRIT
Yan Zhang (Western Sydney University, Australia) "Foundations of First-order Answer Set Programming"
Tuesday May 3, 14h, room to be decided, Manufacture de Tabacs
Dennis Wilson(VORTEX) "An Overview of Deep Learning".
ABSTRACT. Deep Learning has recently made headlines by winning matches of Go [1], running hotels [2], and, most importantly, identifying cats in YouTube videos [3]. The term has become synonymous, for some, with state of the art AI and deserves understanding. In this talk, I will demystify the phrase and give an overview of the underlying theory. Using real-world
examples, I will cover the basics of a single perceptron and the complexities of back propagation and convolutional neural networks. I will illustrate why this method is now receiving widespread attention, and attempt to shed light on some of its current challenges.
[1] http://www.theverge.com/2016/3/9/11184362/google-alphago-go-deepmind-result
[2] http://arstechnica.com/gadgets/2016/03/ibm-watson-hilton-robot-connie/
[3] http://www.nytimes.com/2012/06/26/technology/in-a-big-network-of-computers-evidence-of-machine-learning.html
Tuesday April 19, 2016, 14h in room "Salle du conseil" (1st floor, behind the library)
Jan van Eijck (CWI and ILLC, Amsterdam; joint work with Fengkui Ju, Beijing Normal University, Beijing, China) "Modelling Legal Relations"
We use propositional dynamic logic and ideas about propositional control from the agency literature to construct a simple model of how legal relations interact with actions that change the world, with actions that change the legal relations, and with actions that change basic knowledge about the world. Our model allows us to study the interplay of knowledge, ignorance and legal obligation, and to chart how legal rights and duties are affected by action.
Friday April 15, 2016, 14h IRIT room 001 (ground floor)
Sabine Frittella (U Delft) "Display calculus for Dynamic Epistemic Logic"
ABSTRACT. Display calculi are a specific type of sequent calculi with a cut-elimination meta-theorem. We will present their features and properties, then, if times allows, we will study the design of a display calculi for dynamic epistemic logic.
Tuesday April 12, 2016, 14h, IRIT salle des theses
Tristan Charrier (joint work with Andreas Herzig, Emiliano Lorini, Faustine Maffre, Francois Schwarzentruber, KR 2016) "Building epistemic logic from observations and public announcements"
We study an epistemic logic where knowledge is built from what the agents observe (including higher-order visibility) and what the agents learn from public announcements. This fixes two main drawbacks of previous observability-based approaches where who sees what is common knowledge and where the epistemic operators distribute over disjunction. The latter forbids the modeling of most of the classical epistemic problems, starting with the muddy children puzzle. We integrate a dynamic dimension where both facts of the world and the agents’ observability can be modified by assignment programs. We establish that the model checking problem is PSPACE-complete.
Friday April 8, 15h30 at Manufacture, room ME302
Umberto Grandi (joint work with Ulle Endriss, Ronald de Haan and Jerome Lang, KR 2016) "Succinctness of Languages for Judgment Aggregation"
ABSTRACT. We review several different languages for collective decision making problems, in which agents express their judgments, opinions, or beliefs over elements of a logically structured domain. Several such languages have been proposed in the literature to compactly represent the questions on which the agents are asked to give their views. In particular, the framework of judgment aggregation allows agents to vote directly on complex, logically related formulas, whereas the setting of binary aggregation asks agents to vote on propositional variables, over which dependencies are expressed by means of an integrity constraint. We compare these two languages and some of their variants according to their relative succinctness and according to the computational complexity of aggregating several individual views expressed in such languages into a collective judgment. Our main finding is that the formula-based language of judgment aggregation is more succinct than the constraint-based language of binary aggregation. In many (but not all) practically relevant situations, this increase in succinctness does not entail an increase in complexity of the corresponding problem of computing the outcome of an aggregation rule.
Vendredi 29 janvier 2016 a 10h (salle 001)
Christos Rantsoudis "In all, but finitely many, possible worlds: model-theoretic investigations on `overwhelming majority' default conditionals"
ABSTRACT. Defeasible conditionals of the form `if A then normally B' are usually interpreted with the aid of a `normality' ordering between possible states of affairs: (A à B) is true if it happens that in the most `normal' (least exceptional) A-worlds, B is also true. Another plausible interpretation of `normality' introduced in nonmonotonic reasoning dictates that (A à B) is true iff B is true in `most' A-worlds. A formal account of `most' in this majority-based approach to default reasoning has been independently introduced by K. Schlechta and V. Jauregui, through the notion of `weak filters', a weakening of classical filters used in Set Theory. In this paper, we investigate defeasible conditionals constructed upon a notion of `overwhelming majority', defined as `truth in a cofinite subset of ?', the first infinite ordinal. One approach employs the modal logic of the frame (?, <), used in the temporal logic of discrete linear time. We introduce and investigate conditionals, defined modally over (?, <); several modal definitions of the conditional connective are examined, with an emphasis on the nonmonotonic ones. An alternative interpretation of `majority' as sets cofinal (in ?) rather than cofinite (subsets of ?) is examined. For all these modal approaches over (?, <), a decision procedure readily emerges, as the modal logic KD4LZ of this frame is well-known and a translation of the conditional sentences can be mechanically checked for validity. A second approach employs the conditional version of Scott-Montague semantics, in the form of ?-many possible worlds, endowed with neighborhoods populated by collections of cofinite subsets of ?. Again, different conditionals are introduced and examined. Although it is difficult to obtain a complete axiomatization of these, model-theoretically defined, logics (capturing `cofiniteness-in-?' syntactically seems elusive) this research reveals the possible structure of `overwhelming majority' conditionals, whose relative strength is compared to (the conditional logic `equivalent' of) KLM logics and other conditional logics in the literature.
Vendredi 11 decembre 2015 a 11h (salle 175)
Faustine Maffre (joint work with Andreas Herzig, AT'2015) "How to share knowledge by gossiping"
ABSTRACT. Given n agents each of which has a secret (a fact not known to anybody else), the classical version of the gossip problem is to achieve shared knowledge of all secrets in a minimal number of phone calls. There exist protocols achieving shared knowledge in 2(n-2) calls: when the protocol terminates everybody knows all the secrets. We generalize that problem and focus on higher-order shared knowledge: how many calls does it take to obtain that everybody knows that everybody knows all secrets? More generally, how many calls does it take to obtain shared knowledge of order k? This requires not only the communication of secrets, but also the communication of knowledge about secrets. We give a protocol that works in (k+1)(n-2) steps and prove that it is correct: it achieves shared knowledge of level k. The proof is presented in a dynamic epistemic logic that is based on the observability of propositional variables by agents.
Mercredi 25 novembre 2015 a 14h en salle 001 (rdc de l'IRIT)
Paolo Viappiani (CNRS et LIP6) "Characterization of Scoring Rules with Distances: Application to the Clustering of Rankings" (http://ijcai.org/papers15/Papers/IJCAI15-022.pdf)
ABSTRACT. Positional scoring rules are often used for rank aggregation. In this work we study how scoring rules can be formulated as the minimization of some distance measures between rankings, and we also consider a new family of aggregation methods, called biased scoring rules. This work extends a previous known observation connecting Borda count with the minimization of the sum of the Spearman distances (calculated with respect to a set of input rankings). In particular we consider generalizations of the Spearman distance that can give different weights to items and positions; we also handle the case of incomplete rank data. This has applications in the clustering of rank data, where two main steps need to be performed: aggregating rankings of the same cluster into a representative ranking (the cluster's centroid) and assigning each ranking to its closest centroid. Using the proper combination of scoring rules (for aggregation) and distances (for assignment), it is possible to perform clustering in a computationally efficient way and as well account for specific desired behaviors (give more weight to top positions, bias the centroids in favor of particular items).
Ulle Endriss (ILLC, University of Amsterdam) "Judgment Aggregation under Issue Dependencies" (https://staff.science.uva.nl/u.endriss/slides/seminars/endriss-irit-2015.pdf; https://staff.science.uva.nl/u.endriss/pubs)
ABSTRACT. Judgment aggregation is concerned with the problem of aggregating the views of the members of a group regarding the acceptability of a number of issues. It has been studied in a variety of disciplines, ranging from Legal Studies, Philosophy, Logic, and Economics to Computer Science and Artificial Intelligence. In this talk, I will present a new family of judgment aggregation rules, called the binomial rules, that were designed to account for hidden dependencies between some of the issues being judged. To place them within the landscape of judgment aggregation rules, I will discuss both their axiomatic properties and their computational complexity, and I will show that they contain some well-known rules as special cases. To evaluate the performance of the binomial rules empirically, we have applied them to a dataset of crowdsourced judgments regarding the quality of hotels extracted from the travel website TripAdvisor. I will report on these experiments and discuss a number of new ideas for performing this kind of experimental evaluations in judgment aggregation. This is based on joint work with Marco Costantini and Carla Groenland. The talk will be broadly accessible. In particular, I will not assume any prior exposure to judgment aggregation.
Vendredi 16 octobre a 14h en salle des theses
Edouard Pauwels "Optimisation et apprentissage, présentation de quelques travaux"
RESUME. J'ai été recruté cette année sur le poste MCF 27/26 dans l'équipe ADRIA. L'orientation de mon dossier pour ce concours était "optimisation pour les mégadonnées". Je profiterai de ce séminaire pour présenter un aperçu de mon parcours académique: thèse en bioinformatique, deux postdocs, le premier en commande optimale et le second en optimisation convexe de grande taille. Depuis la fin de ma thèse je me concentre essentiellement sur des problématiques liées à l'optimisation continue et ses applications. L'objectif est de présenter les thématiques qui m'intéressent pour engager une discussions et envisager des développements en liens avec les activités de l'IRIT.
Martin Cooper "A la recherche de nouvelles classes polynomiales"
RESUME. L'identification de la frontière entre P et NP-complet est un problème fondamental en Informatique. Dans le cadre CSP (problème de satisfaction de contraintes, un problème combinatoire générique très étudié en IA) de nombreux travaux portent sur cette question. Pendant une trentaine 'années une théorie très riche s'est construite en s'appuyant sur l'algèbre universelle ou encore sur la théorie des graphes. Ces approches classiques cherchent à identifier les classes polynomiales définies par des restrictions soit sur le type de contraintes (par exemple, les clauses de Horn), soit sur la forme du graphe de contraintes (par exemple, de largeur d'arbre bornée).
Plus récemment une troisième approche s'est vu le jour, basée sur la définition de classes d'instances par l'interdiction de sous problèmes. Nous passerons en revue les nouvelles classes polynomiales qui sont le fruit de cette nouvelle approche avant de présenter les avancés les plus récents (nouvelles opérations de simplification, une définition de mineur tpologique d'instance CSP, une généralisation des contraintes "max-closed").
Mercredi 14 octobre a 14h en salle 001
David Fernandez Duque "Dynamic Topological Logic"
ABSTRACT. Dynamic Topological Logics are polymodal system which combines the topological interpretation of S4 with Linear Temporal Logic in order to reason about dynamical systems, which are essentially mathematical models of movement in space. We will give an introduction to these logics, show how they can be used to express interesting properties of dynamical systems, and give an overview of known completeness and incompleteness results.
Lundi 31 aout à 10h, salle des thèses
Raul Fervari (U Nacional de Cordoba, Argentine, based on a paper at WoLLIC with Carlos Areces, Hans van Ditmarsch, Francois Schwarzentruber) "Logics with copy and remove"
Jeudi 21 mai à 11h, salle ME303 (Manufacture des Tabacs)
Elise Bonzon (joint work with Nicolas Maudet and Stefano Moretti) "Coalitional games for abstract argumentation"
Abstract: In this work we address the issue of uncertainty in abstract argumentation. We propose a way to compute the relative relevance of arguments by merging the classical abstract argumentation framework into a game theoretic coalitional setting, where the worth of a collection of arguments can be seen as the combination of the information concerning the defeat relation and the preferences over arguments of a ``user''. Via a property-driven approach, we show that the Shapley value for coalitional games defined over an argumentation framework, can be applied to resume all the information about the worth of sets of arguments into an attribution of relevance for the single arguments. We also prove that, for a large family of (coalitional) argumentation frameworks, the Shapley value can be easily computed.
Mardi 19 mai à 12h30, salle ME303 (Manufacture de Tabacs)
Edith Elkind (Oxford University, based on joint work with Haris Aziz, Markus Brill, Vince Conitzer, Rupert Freeman, and Toby Walsh, AAAI'15) "Justified Representation"
ABSTRACT. We consider approval-based committee voting, i.e., the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of these rules, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MAV (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and unanimity, and the complexity of the associated algorithmic problems.
Lundi 11 mai à 15h30, salle des thèses
Nizar Habash (New York University Abu Dhabi, http://www.nizarhabash.com) "Computational Processing of Arabic Dialects"
ABSTRACT. The Arabic language is a collection of variants among which Modern Standard Arabic (MSA) has a special status as the formal written standard of the media, culture and education across the Arab World. The other variants are informal spoken dialects that are the media of communication for daily life. As expected, most of the natural language processing resources and research in Arabic focuses on MSA. However, there is more work now on Arabic dialects, which includes efforts to build resources as well as exploit existing resources from MSA. In this talk, we present the challenges of processing Arabic dialects and the current advances in that area, with special emphasis on directions that exploit existing MSA (and other dialect) resources.
Jeudi 30 avril a 16h, salle des theses
Umberto Grandi "Collective Sentiment Analysis and Judgment Aggregation"
Vendredi 23 Janvier 2015 à 14h30 en salle des thèses
Jonathan Ben-naim (with L. Amgoud) "Ranking Semantics for Argumentation"
ABSTRACT. Argumentation is a form of common-sense reasoning for drawing conclusions, making decisions, convincing someone of an idea (etc.) by constructing and evaluating arguments (i.e., reasons) in favor or against conclusions, decisions, ideas, or other arguments. In the present work, we focus on a certain kind of systems related to the notion of argumentation. More precisely, an argument-evaluation system consists of the three following parts: a set of arguments; a set of attack relations between them; and a method, called semantics, for evaluating the arguments. Our goal is to construct ranking semantics (i.e., semantics that rank the arguments from the weakest to the strongest ones) and analyze them on the basis of nine axioms, which provides a certain degree of theoretical validation for them. Finally, as an extension, we show how ranking semantics can be used to deal with inconsistent databases.
Mardi 18 Novembre de 16h à 17h en salle des thèses
Javier Bajo (Madrid) "Multiagent Systems and Virtual Organizations"
Research on Agents and Multi-Agent Systems has matured during the last decade and many effective applications of this technology are now deployed. Particular interest has been paid to social behaviors and intelligent environments, including organizational aspects. Virtual organizations can be considered as a set of individuals and institutions that need to coordinate resources and services across institutional boundaries. Multi-agent systems (MAS) technology, which allows forming dynamic agent organizations, is particularly well suited as a support for the development of these open systems.
Some applications áreas of this technology can be Social Computing (the computational facilitation of social studies and human social dynamics as well as the design and use of ICT technologies that consider social context) or Ambient Intelligence (a recent paradigm oriented to use computational resources as proactive tools assisting people with their day-to-day activities, making everyone’s life more comfortable).
In this lecture I will introduce the concept of virtual organization in MAS and will present current trends in related with this area.
Mardi 4 novembre 2014 de 12:30 à 13:30 en salle ME303, Manufacture
Guifei Jiang (University of Western Sydney et Université Toulouse 1 Capitole) "A Logic for Game Description and Strategic Reasoning"
ABSTRACT. Logical analysis of games has been an important topic across the study of game theory, mathematics, philosophy and co mputer s cience. It deals with the problems of how to specify a game situation, how to represent a game strategy and, more importantly, how to model strategic reasoning of game players.
In this report, I will present a logical framework we have proposed for game description and strategic reasoning. The language of this framework extends Game Description Language (GDL) [1] with coalition operators from Alternating-time Temporal Logic (ATL) [2] and prioritised strategy connectives from Zhang and Thielscher's framework [3]. The semantics is built upon the standard state transition model. The new framework allows us to formalise van Benthem's game-oriented principl es in multi-player games, and formally derive Weak Determinacy and Zermelo's Theorem for two-player games. I will demonstrate with a real-world game how to use our language to specify a game and represent a winning/no-losing strategy. The model-checking problem of our logic is proved in 2EXPTIME with respect to the size of game structure and the length of a formula, which is no worse than the model-checking problem in ATL*.
Références
[1] Love, N., Hinrichs, T., Genes ereth, M.: General game playing: Game description language specification. Tech. rep., Computer Scinece Department, Stanford University (2006).
[2] Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic.Journal of the ACM 49(5), 672--713 (2002).
[3] Zhang, D., Thielscher, M.: Representing and reasoning about game strategies. To appear in J. Phi losophic al Logic (2014).
Mardi 14 Octobre 2014 à 10h30 en salle 001
Sylvie Doutre (with A. Herzig and L. Perrussel) "A Dynamic Logic Framework for Abstract Argumentation"
ABSTRACT. We provide a logical analysis of abstract argumentation frameworks and their dynamics. Following previous work, we express attack relation and argument status by means of propositional variables and define acceptability criteria by formulas of propositional logic. We here study the dynamics of argumentation frameworks in terms of basic operations on these propositional variables, viz. change of their truth values. We describe these operations in a uniform way within a well-known variant of Propositional Dynamic Logic PDL: the Dynamic Logic of Propositional Assignments, DL-PA. The atomic programs of DL-PA are assignments of propositional variables to truth values, and complex programs can be built by means of the connectives of sequential and nondeterministic composition and test. We start by showing that in DL-PA, the construction of extensions can be performed by a DL-PA program that is parametrized by the definition of acceptance. We then mainly focus on how the acceptance of one or more arguments can be enforced and show that this can be achieved by changing the truth values of the propositional variables describing the attack relation in a minimal way.
Yuming Xu (School of Mathematics, Shandong University) "Dynamic properties of argumentation frameworks based on extensions"
ABSTRACT. The matrices and their subblocks are introduced into the study of Dung’s theory of argumentation frameworks. It is showed that every argumentation framework can be represented by a matrix, and the basic extensions (such as admissible, stable, complete) of an argumentation framework can be de- termined by subblocks of its matrix. In particular, a general approach to find out basic extensions has been developed by two kinds of normal form of matrices. Furthermore, the sub-argumentation framework is proposed for the study of union of two admissible extensions. As a result, the alternative approaches to find out the grounded and preferred extensions are described roughly.
Lundi 13 octobre à 14h en la salle du conseil
Shafiq Joty (Qatar Computing Research Institute) "Discursive parsing"
Vendredi 19 septembre a 14h en salle 175
Georgios Chalkiadakis (Technical University of Crete) "On Cooperative (Coalitional) Games in the context of Multiagent Systems" (2nd part)
Vendredi 12 septembre de 14h a 16h, salle du conseil (ancienne bibliotheque)
Georgios Chalkiadakis (Technical University of Crete) "On Cooperative (Coalitional) Games in the context of Multiagent Systems"
ABSTRACT. Cooperative game theory studies the behavior of self-interested agents in strategic settings where binding agreements among agents are possible. We present a survey of work on the computational aspects of cooperative game theory, in the context of multiagent systems research. We begin by formally defining transferable utility games, and introducing key solution concepts for such games. We then discuss identifying compact representations for games, and the closely related problem of efficiently computing solution concepts for games. We survey several formalisms for cooperative games that have been proposed in the literature. We overview algorithms for identifying welfare-maximizing coalition structures and methods used by rational agents to form coalitions (even under uncertainty), including bargaining algorithms. We conclude by considering applications and future research directions.
The tutorial is closely based on a recent textbook by Chalkiadakis, Elkind, and Wooldridge entitled Computational Aspects of Cooperative Game Theory : http://web.spms.ntu.edu.sg/~eelkind/coopbook/.
Wednesday 9th July, salle des theses (from 14h on): Mini-Workshop "Logic and social choice"
14h-14h45: Fangzhen Lin (U Hongkong, with Ning Ding) "On Computing Optimal Strategies in Open List Proportional Representation: the Two Parties Case"
ABSTRACT. Open list proportional representation is an election mechanism used in many elections, including the 2012 Hong Kong Legislative Council Geographical Constituencies election. In this paper, we assume that there are just two parties in the election, and that the number of votes that a list would get is the sum of the numbers of votes that the candidates in the list would get if each of them would go alone in the election. Under these assumptions, we formulate the election as a mostly zero-sum game, and show that while the game always has a pure Nash equilibrium, it is NP-hard to compute it.
14h45-15h30: Umberto Grandi (with Edith Elkind, Francesca Rossi and Arkadii Slinko) "Games Gibbard-Satterthwaite Manipulators Play"
ABSTRACT. The Gibbard-Satterthwaite theorem implies the ubiquity of manipulators---the voters who could change the election outcome in their favor by unilaterally modifying their vote. In this paper, we ask what happens if a given profile admits several such voters. We model the strategic interactions among these voters, whom we call Gibbard-Satterthwaite manipulators, as a normal-form game. We classify the two-by-two games that can arise in this setting for some simple voting rules, and study the complexity of determining whether a given manipulative vote weakly dominates truthtelling, as well as existence of Nash equilibria.
15h30-16h15: Thomas Agotnes (U Bergen) "Is reasoning about social choice decidable?"
Mardi 8 juillet a 11h, en salle 001
Etienne Fieux (IMT Toulouse)"Combinatoire topologique, illustrations"
RESUME. Par opposition à la topologie combinatoire (qui s'est développée en topologie algébrique), l'expression de combinatoire topologique veut exprimer l'idée d'utiliser des méthodes et résultats classiques en topologie pour résoudre des problèmes de nature combinatoire. Cela peut ouvrir le champ d'application de notions usuelles (comme l'homotopie) à d'autres champs de recherche. Le but de cet exposé est d'expliquer en quoi consiste cette approche et de l'illustrer sur des exemples ayant (peut-être ?) un lien avec des questions en informatique : (1) formules booléennes et problème SAT, (2) conjecture d'évasivité - evasiveness conjecture - et complexité de l'arbre de décision d'une fonction booléenne, (3) une autre approche pour le théorème d'Arrow (théorie du choix social/agrégation de préférences).
Références :
1. Conant J., Thistlethwaite O., Boolean formulae, hypergraphs and combinatorial topology, Topology Appl. 157 (2010), no. 16, 2449–2461.
2. Lovasz L., Lecture Notes on Evasiveness of Graph Properties, notes rédigées par N. E. Young, Arxiv cs/0205031, mai 2002.
3. Tanaka Y., On the equivalence of the Arrow impossibility theorem and the Brouwer fixed point theorem when individual preferences are weak orders, J. Math. Econom. 45 (2009), no. 3-4, 241–249.
Thursday July 3, Salle du Conseil from 10h on: Workshop "Planning and logic"
10h00-10h45 Laurent Perrussel (with Guifei Jiang and Dongmo Zhang) "GDL Meets ATL: A logic for game description and strategic reasoning"
11h-11h45 Frédéric Maris "Planning with temporally extended actions"
14h-15h Thomas Bolander (DTU Denmark) "Epistemic planning and undecidability"
15h-16h Thomas Agotnes (U Bergen) "Undecidability of Group Announcement Logic"
16h-17h Andreas Herzig (with Viviane Menezes, Leliane Nunes de Barros, Renata Wassermann) "On the revision of planning tasks"
Wednesday July 2, Salle des thèses
15h Thomas Bolander "Epistemic planning" (tutorial, 2h, part of the Workshop "Planning and logic")
Jeudi 26 juin a 15h15 en salle 175
Philippe Besnard "Revisiting postulates for inconsistency measures"
Martin Dieguez (University of Corunna) "Strong Equivalence of Non-Monotonic Temporal Theories" (joint work with Pedro Cabalar)
ABSTRACT. Temporal Equilibrium Logic (TEL) is a non-monotonic temporal logic that extends Answer Set Programming (ASP) by introducing modal operators as those considered in Linear time Temporal Logic (LTL). TEL allows proving temporal properties of ASP-like scenarios under the hypothesis of infinite time while keeping decidability. Formally, it extends Equilibrium Logic (the best-known logical formalisation of ASP) and, as the latter, it selects some models of a monotonic basis: the logic of Temporal Here-and-There (THT).
In this paper we solve a problem that remained unanswered for the last six years: we prove that equivalence in the logic of THT is not only a sufficient, but also a necessary condition for strong equivalence of two TEL theories. This result reinforces the need of THT as a suitable monotonic basis for TEL and furthermore when two temporal theories are not strongly equivalent the proof provides a context that makes them behave differently as well as a method to compute temporal equilibrium models that arise from such difference.
Joseph Boudou "Decidability of Iteration-free PDL with Parallel Composition" (joint work with Philippe Balbiani)
ABSTRACT. PRSPDL is a highly undecidable propositional dynamic logic with an operator for parallel composition of programs. This operator has a separation semantic such that a multiplicative conjunction similar to the one found in the logic of Boolean bunched implications is definable. The present work identifies an iteration-free decidable fragment of PRSPDL in which the multiplicative conjunction is still definable. A NEXPTIME complexity upper bound for the fragment is given.
Mercredi 4 juin a 10h en salle des theses
Emiliano Lorini "A STIT Logic Analysis of Social Influence"
ABSTRACT. In this paper we propose a method for modeling social influence within the STIT approach to action. Our proposal consists in extending the STIT language with special operators that allows us to represent the consequences of an agent’s choices over the rational choices of another agent.
Vendredi 2 mai a 14h30 dans l'aquarium du 3eme etage
Emiliano Lorini, Giovanni Sartor "A STIT logic analysis of social influence"
Olivier Gasquet, Valentin Goranko, Francois Schwarzentruber "Big Brother Logic: Logical modeling and reasoning about agents equipped with surveillance cameras"
Lundi 7 avril 2014 a 14h dans l'auditorium de l'IRIT
Peter Gardenfors "The Geometry of Meaning: Semantics Based on Conceptual Spaces"
Vendredi 21 fevrier 2014 a 14h en salle des theses
Francesco Belardinelli (Université d'Evry) "Verification of Auctions as Artifact Systems: Decidability via Finite Abstraction"
Artifact Systems are a novel paradigm in business processes that has received recently considerable attention in service-oriented computing. Artifact Systems (AS) are best described in terms of interacting modules, or artifacts, consisting of a data model and a lifecycle, which account respectively for the relational structure of data and their evolutions over time. However, by considering data and processes as equally relevant tenets of AS, the typical questions concerning the verification of these services can no longer be solved by current methodologies, as the presence of data means that the number of states in AS is infinite in general.
In this talk we show that the framework of Artifact Systems can be applied fruitfully to game-theoretic scenarios. Specifically, we provide a formalisation of English (ascending bid) auctions as AS. Then, we present agent-based abstraction techniques to model check AS against temporal epistemic specification, thus obtaining decidability results for the auction scenario in question.
The research presented in this talk includes joint work with Prof A. Lomuscio and Dr F. Patrizi and it has been partially funded by the EU STREP Project ACSI.
%%%%%%%%%%%%%%% 2014 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Mercredi 18 decembre
Seminaire argumentation (ADRIA)
Mercredi 9 octobre 2013 a 11h00 en salle des theses
Hitoshi Omori "Intuitionisitic logic is missing negation"
One of the most well known non-classical logics is intuitionistic logic. And since intuitionistic logic is a subsystem of classical logic, it is generally thought that it contains negation. In this talk, we challenge this view. The aim of the talk is twofold. First, we clarify what we mean by negation in terms of semantic framework, and show that intuitionistic negation is not a negation. Note here that this kind of objection is not new at all. For example, Arnon Avron defends that classical negation is the perfect negation and rejects other negations, including intuitionistic negation. Second, we consider two ways of enriching intuitionistic logic by negation. One is by adding de Morgan negation which results in Nelson logics. The other is by adding classical negation. The latter sounds paradoxical in view of the well known result, but we show that there is a way to make sense of it.
Mardi 16 juillet 2013 a 11h00 (salle 001)
Andreas Herzig "Logics for belief change operations: a short history of nearly everything"
ABSTRACT. We examine several belief change operations in the light of a dynamic logic of propositional assignments DL-PA. We show that we can encode in a systematic way updates as particular DL-PA programs. This provides a syntactical update method.
Mercredi 19 juin 2013 a 11h à l'IRIT (salle des theses)
David Fernández Duque (University of Sevilla) "Geometric solutions for the generalized Russian cards problem" (séminaire dans le cadre du séjour de Valentin Goranko, expert invité CIMI)
ABSTRACT. In the generalized Russian cards problem Alice, Bob and Cath draw a,b and c cards, respectively, from a deck of a+b+c cards in total. Each player may only see the cards that they hold, but Alice and Bob wish to communicate their hand to each other without Cath learning who owns a single card that is not hers. However, they may not communicate beforehand and once the cards have been drawn, Cath has access to all communications between them. For which values of a,b,c can Alice and Bob achieve this? What steps must they follow?
In this talk we will present a general solution for the problem for many values of a,b,c. They are based on finite vector spaces. The solutions we present will assume that Cath has less cards than either Alice or Bob, but time permitting we will discuss improvements which allow us to drop this condition.
Mardi 14 mai 2013 a 14h en auditorium
Nils Bulling "Comparing Variants of Strategic Ability--How Uncertainty and Memory Influence General Properties of Games"
ABSTRACT. Alternating-time temporal logics (ATL) have been studied extensively in previous years. However, most of the research was focused on the way such logics can be used for the specification and verification of multi-agent systems. Studies of other decision problems and meta-properties of these logics were mostly limited to the basic variant of ATL where agents possess perfect information and perfect memory.
In this talk, we show that different assumptions about agents' knowledge and memory in ATL give rise to different validity sets. As a consequence, we show that different notions of ability induce different strategic logics and different general properties of games.
Moreover, the study can be seen as the first systematic step towards satisfiability-checking algorithms for ATL with imperfect information.
Vendredi 12 avril 2013 a 14h30 en salle du conseil
Andreas Herzig (with Emiliano Lorini and Dirk Walther) "Reasoning about actions meets strategic logics"
We introduce ATLEA, a novel extension of Alternating-time Temporal Logic with explicit actions in the object language. ATLEA allows to reason about abilities of agents under commitments to play certain actions. Pre- and postconditions as well as availability and unavailability of actions can be expressed. We show that ATLEA allows to reason about actions in a multiagent context by encoding Reiter’s solution to the frame problem, or more precisely, its multiagent version. We also consider an epistemic extension of ATLEA along the lines of Alternating-time Temporal Epistemic Logic (ATEL). We demonstrate that the resulting logic is sufficiently expressive to reason about uniform choices of actions.
jeudi 14 mars 2013 a 11h30 dans l'auditorium
Emiliano Lorini "Ockhamist Propositional Dynamic Logic: a natural link between PDL and CTL*"
ABSTRACT. We present a new logic called Ockhamist Propositional Dynamic Logic, OPDL, and study its relationship with PDL and CTL*. We prove the decidability of its satisfiability problem and we show that it provides a rich logical framework for representing several deontic concepts such as obligation of action, permission as lack of prohibition, free-choice permission, obligation with deadline and conditional obligation whose formalization requires the expressive power of branching-time temporal logics such as CTL or CTL*.
lundi 25 fevrier 2013 à 12h45 en salle ME-303
Frédéric Moisan "When the Group Matters: A Game-Theoretic Analysis of Empathy, Team Reasoning, and Social Ties"
ABSTRACT. In this work, we provide a comparative analysis of two theories from the economics literature whose aim is to clarify how agents reason and are able to coordinate when acting as members of the same group: Binmore's theory of empathetic preferences and Bacharach's theory of team reasoning. After discussing the various limitations of these two theories in modeling large multiagent systems and (artificial or human) societies where different competing groups may coexist, we introduce a new model of social ties which appears to provide a simpler and more intuitive approach to modeling collaborative action in the context of multiagent systems.
lundi 4 fevrier à 12h40 à UT1C-manufacture des tabacs
Guilin Qi (University of Nanjing) "An Introduction to Ontology Languages for the Semantic Web"
ABSTRACT. The Semantic Web is considered as the next generation of World Wide Web, where information is published and interlinked in order to facilitate the exploitation of its structure and semantics (meaning) for both humans and machines. To foster the realization of the Semantic Web, the World Wide Web Consortium (W3C) developed a set of languages to represent metadata (Resource Description Framework or RDF for short), ontologies (RDF Schema and Ontology Web Language or OWL for short), and queries (e.g., SPARQL). In this talk, I will first give an introduction of RDF(S) and OWL. I then introduce description logics, which are decidable fragments of first-order predicate logic and provide logical underpinings of OWL. Finally, I will introduce some recent work on applying ontologies to integrate information extracted from the Web pages of traditional Web.
vendredi 1 fevrier a 14h en salle 001
Guillaume Escamocher "Variable Elimination in Binary CSPs via Forbidden Patterns"
ABSTRACT. A variable elimination rule allows the polynomial-time identification of certain variables whose elimination does not affect the satisfiability of an instance. Variable elimination in the constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. We show that there are essentially just four variable elimination rules defined by forbidding generic sub-instances, known as irreducible patterns, in arc-consistent CSP instances.
Soumya Paul (with Cedric Degremont, Guillaume Feuillade) "Strategy resistant games"
ABSTRACT. We explore infinite games where the winning condition of the game is stated in some language $L$ and the players are allowed to reason in another (possibly less-expressive) language $L'$. We investigate when a player can win playing for a condition in $L$ even though she strategises in the weaker language $L'$. We also study the kind of restrictions one needs to impose on the reasoning abilities of the player (the language $L'$) so that she cannot win the game with the $L$ winning condition.
vendredi 25 janvier à 14h30 en salle des theses
Enrico Marchioni "Many-valued logics and the representation of uncertainty: An overview"
ABSTRACT: The aim of this talk is to offer a concise overview of some of the main properties of many-valued logics and their use in the representation of uncertainty. One of the main features of many-valued logics with real-valued semantics is the fact that the evaluation of each formula corresponds to a function over the reals. For instance, Lukasiewicz infinite-valued logic is the logic of continuous piecewise linear polynomial functions over the unit cube $[0, 1]^n$ and has as basic functions the bounded sum and an order-reversing involution. Other logics include operations like multiplication, truncated division, and rational constant functions. The fact that these operations are encoded in the syntax makes it possible to use formulas to represent functional relations at the symbolic level. This has been exploited in order to represent measures such as probability, possibility and necessity, and belief functions. In fact, in several works, many-valued logics have been expanded with the addition of a modality whose intended meaning is the degree of uncertainty of a certain proposition. The basic properties of a class of uncertainty measures can then be encoded through formulas depending on the operations that characterize the class. This approach is also being used to represent expected utility and strategic interaction between players in noncooperative games.
vendredi 18 janvier à 14h30 en salle des theses
Guilin Qi "Belief revision in description logics"
ABSTRACT. Recently, there is an increasing interest in the problem of revision of ontologies in description logics, which are a family of important ontology languages. This problem is closely related to the problem of belief revision which has been widely discussed in the literature. In this talk, will give an overview of existing works on revising ontologies in description logics. We will first laybare the difficulties of applying belief revision theory to description logics. We then present works on applying AGM postulates for revision to description logics and discuss their weakness. This raises the fundamental question what is a rational revision operator in description logics. Afterwards, we introduce syntax-based revision operators and model-based revision operators in description logics. We argue that model-based revision is not as promising as syntax-based one. Finally, we propose some ideas for future research of revision of ontologies in description logics.
mardi 8 janvier 2013 à 14h en salle des theses
Christophe Chareton "Updatable Strategy Logic"
ABSTRACT: This presentation is about temporal multi-agent logics. Several of these formalisms have been already presented (ATL-ATL*, ATLsc, SL). They enable to express the capacities of agents in a system to ensure the satisfaction of temporal properties. Particularly, SL and ATLsc enable several agents to interact in a context mixing the different strategies they play in a semantical game. We generalize this possibility by proposing a new formalism, Updating Strategy Logic (USL). In USL, an agent can also refine its own strategy. The gain in expressive power rises the notion of ``sustainable capacities'' for agents.
USL is built from SL. It mainly brings to SL the two following modifications: semantically, the successor of a given state is not uniquely determined by the data of one choice from each agent. Syntactically, we introduce in the language an operator, called an ``unbinder'', which explicitely deletes the binding of a strategy to an agent. We show that USL is strictly more expressive than SL. We also give the results of model-checking for USL and its memoryless version. They are the same as those of formalisms with implicit unbinders, such as SL and ATLsc.
%%%%%%%%%%%%%%% 2013 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
vendredi 14 decembre 2012 a 15h en salle des theses
Frédéric Maris "Tractable Monotone Temporal Planning"
ABSTRACT: We describe a polynomially-solvable sub-problem of temporal planning. Polynomiality follows from two assumptions. Firstly, by supposing that each sub-goal fluent can be established by at most one action, we can quickly determine which actions are necessary in any plan. Secondly, the monotonicity of sub-goal fluents allows us to express planning as an instance of STP? (Simple Temporal Problem, difference constraints). Our class includes temporally-expressive problems, which we illustrate with an example of chemical process planning.
RESUME : Nous présentons une classe de problèmes de planification temporelle solubles en temps polynomial. Ce résultat découle de deux hypothèses. Nous supposons d’abord que les sous-buts ne peuvent être établis que par une action unique, ce qui nous permet de déterminer rapidement les ac-tions qui sont nécessaires dans tous les plans. Nous supposons également que les sous-buts sont monotones, ce qui nous permet d’exprimer la planification comme une instance de STP? (Simple Temporal Problem, difference constraints). Notre classe contient des problèmes temporellement expressifs, ce que nous illustrons avec un exemple de planification de processus chimique.
vendredi 16 novembre a 14h en *salle du conseil*
Dirk Walther (Universidad Politecnica de Madrid) "Modularity in Ontologies"
ABSTRACT.
Nowadays, logical theories in guise of ontologies are designed for applications in bioinformatics, medicine, geography, linguistics and other areas. They are often based on description logics with well-understood and implemented reasoning problems and procedures. The challenges are now to provide automatic support for sharing and reuse of ontologies as well as their design and maintenance. A key concept in tackling the challenges is the notion of modularity. Recently we have seen the introduction of many related notions together with challenging technical results. In this talk I explain how model-theoretic notions of modularity and relevant reasoning problems can be based on the notion of inseparability of logical theories. Algorithms for module extraction for the description logics EL and ALC will be discussed as well as their complexity and an experimental evaluation. The notion of inseparability is rather versatile, and I briefly explain its relationship to logical difference and forgetting of vocabulary.
vendredi 5 octobre a 14h *en salle 175*
Christian Retoré (Université Bordeaux 1 et LaBRI en délégation CNRS à l'IRIT) "Sémantique du langage naturel en théorie types"
RESUME. Cet exposé a pour but de présenter le programme de recherche que je compte développer à l'IRIT durant mon année de délégation.
J'essaierai de montrer comment la théorie des types, et plus particulièrement le lambda calcul typé du second ordre, donne un cadre général pour la sémantique du langage naturel. Il s'agit d'une sémantique compositionnelle qui calcule la ou les formules logiques associées au sens d'une phrase à partir d'un lexique et de la structure syntaxique. L'utilisation d'un système de types plus riche (le lambda calcul du second ordre) que celui initialement utilisé par Montague (le lambda calcul simplement typé) permet de surcroît de rendre compte du sens lexical et de sa variation en contexte. Ce travail développé avec Ch. Bassac, B. Mery, R. Moot, L. Prévot,... est à rapprocher de certains travaux de Asher, Luo et Soloviev.
Du point de vue de la sémantique lexicale on peut rendre compte de la référence à une facette du sens d'un mot, de la prédication sur diverses facettes du sens d'un même mot ("Liverpool a battu Chelsea." "Liverpool est une ville portuaire.") On peut même rendre compte de glissement de sens plus complexes encore, comme le voyageur virtuel (fictive motion). ("La route descend pendant deux heures.")
Du point de vue de la sémantique compositionnelle, on peut calculer les formes logiques d'énoncés comportant
- des quantifications généralisées, ("Les anglais aiment la France.")
- des pluriels, ("Les bleus ont perdu." "Les bleus ont moins de trente ans.").
Finalement, et c'est sans doute le plus important, je présenterai quelques questions dont j'aimerais beaucoup discuter avec vous lors de mon séjour à l'IRIT. Quels sont les types de base? Comment les acquérir? Quelle notion de sous-typage est à la fois adaptée au système de types et à son utilisation linguistique?
Christian Bassac, Bruno Mery, Christian Retoré. Towards a Type-Theoretical Account of Lexical Semantics. Journal of Logic Language and Information, 19 (2010) 229-245. http://hal.inria.fr/inria-00408308
Christian Retoré. Variable types for meaning assembly: a logical syntax for generic noun phrases introduced by "most". Recherches linguistiques de Vincennes 41 (2012) 83-102. http://hal.archives-ouvertes.fr/hal-00677312
vendredi 29 juin 2012 a 14h en salle du conseil
Emiliano Lorini "A logic for reasoning about agents' attitudes in strategic contexts"
ABSTRACT. Logics, especially modal logics, have been widely used in the past to model the properties of autonomous agents and multi-agent systems (MAS). Different variants of epistemic logics, dynamic epistemic logics, logics of preferences and intention have been proposed whose aim is to describe both the static and the dynamic properties of agents' mental attitudes. Furthermore, there are logics of collective attitudes including common knowledge and common belief, joint intention and collective acceptance. Finally, several logical systems for reasoning about actions and capabilities of agents and groups of agents have been proposed such as Coalition Logic, STIT logic and ATL. The concepts formalized in these logics are mainly inspired by game theory and social choice theory.
In this talk I will present a recent work on the logical formalization of agents' attitudes, both individual and collective, in strategic contexts. The logic I will present supports reasoning about different concepts such as graded belief, disposition to believe, certain belief, robust belief, common certainty and common robust belief. I will show how this logic can be applied to game theory by providing a formal analysis of the epistemic conditions of different solution concepts such as Nash equilibrium, iterated strong dominance and iterated weak dominance. In the last part of my talk (time permitting) I may discuss some open issues and challenges in the area of logical modelling of agents' attitudes in strategic contexts such as the problem of relaxing the assumption of logical omniscience in order to represent both the static and the dynamic properties of explicit beliefs and explicit common beliefs and in order to distinguish them from implicit beliefs and implicit common beliefs.
jeudi 28 juin a 14h en salle du conseil
Dongmo Zhang (Intelligent System Laboratory, University of Western Sydney; joint work with Michael Thielscher) "Representing and Reasoning about Game Strategies"
ABSTRACT. As a contribution to the challenge of building AI systems for playing a wide variety of games, we develop a practical-oriented formalism for representing and reasoning about strategies. Our logical language, which is intended to be used to describe strategies for software game players, builds on the existing general Game Description Language (GDL) and extends it by a single temporal operator for linear time and by two connectives for strategy combination and composition. The semantics of the language is provided by a standard state-transition model. As such, problems that require reasoning about games and strategies can be solved by the standard methods for reasoning about actions and change.
vendredi 15 juin 2012 a 14h
Yves Moinard (Rennes) "Pont miné, vieil éléphant mangeur de bananes, et utilisation de la programmation par ensembles réponses"
jeudi 10 mai a 12h30 en salle ME 303 de la Manufacture des Tabacs
Clara Smith (Universidad Nacional de La Plata, Argentine) "Responsibility of agents in non contractual scenarios. A multi-modal account"
ABSTRACT. Theorizing in domains such as legal and cognitive status of agents is crucial for designers of agent systems, especially, for those who design “on demand” MAS. Within this engineering approach, a lawful question arises: do the designed agents are to be autonomous enough to have rights and responsibilities?. What justifies -in the head of another agent different from the one acting- the obligation to compensate is the fact that a principal agent has lengthen its own action through the implementation of a /foreign activity/ for its own interests.
We focus on the legal binding between a principal agent and a helper (or dependent) agent. But we keep apart from this analysis those situations in which the performance in the interest of another one has its origin in a contract (this because, in contracts, function for another one and subordination are somehow straightforward to identify, mainly because in a contract there is an explicit notion of obligation involved). Therefore, we discuss the impact of the helper’s harmful performance that has its origin in /extra contractual/ situations e.g factual, occasional situations, altruistic behaviour, or courtesy.
We devise two relativized modal operators for representing, respectively, intentions in the interest of another agent and agency in the interest of another agent. They are useful for characterizing the concept of responsibility by reflex in a multi-modal multi-agent system (MAS) context.
vendredi 27 avril 2012 a 14h en salle 001
Geng Wang "Modelling non monotonic properties in propositional argumentation"
vendredi 16 mars 2012 a 14h15 en salle du conseil
Lamia Belouaer (équipe MAD du GREYC) "Représentation de la connaissance spatiale pour la planification"
RESUME. Nous nous intéressons à la prise en compte de l'information spatiale d'un point de vue de la représentation et du raisonnement afin de planifier une mission dans le cadre de l'interaction homme-robot. Une première partie de la thèse concerne la représentation et le raisonnement spatial. Nous proposons une ontologie spatiale : SpaceOntology permettant de représenter l'information spatiale qualitative, quantitative et de mener un raisonnement sur celle-ci. Sur la base de cette modélisation spatiale nous avons mis en place un planificateur avec deux modules : un module de raisonnement symbolique supporté par un planificateur de tâches et un module de raisonnement spatial supporté par le planificateur de chemins et SpaceOntology. Enfin, la troisième partie de nos contributions concerne l'extension du langage de planification PDDL à l'information spatiale. Cette extension permet de donner à un problème de planification une sémantique spatiale.
- lundi 30 janvier 2012 a 15h en salle 001 (rdc)
David Traum (USC Institute for Creative Technologies) "Computational Models of Non-cooperative dialogue"
%%%%%%%%%%%%%%% 2012 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- vendredi 18 novembre 2011 a 14h en salle du conseil
Davide Ciucci "Three-valued logics and uncertainty management"
In literature, several 3-valued logics can be found. They differ from a syntactic and proof-theoretic point of view as well as on the interpretation given to the third value. The project “3VAL” is aimed to review these logics with a particular attention to semantics and to the intuition behind each logic. The challenge is to link formal studies with applications (such as rough sets, conditional events, null values in databases, logic programming, etc.) in order to arrive at a better understanding of three-valued logics and their role in knowledge representation. Here, we give a preliminary attempt to clarify the situation of three-valued logics. Logical operations on three-valued functions are studied and their relationship put forward. They are also linked to existing logics, pointing out their usage and interpretation of the third value.
- jeudi 10 novembre a 14h en salle des theses
Davide Grossi (University of Liverpool) "Argumentation and modal logic"
ABSTRACT. In this talk I will pursue the simple idea of viewing Dung frameworks as Kripke frames. Several techniques and results can accordingly be imported from modal logic to abstract argumentation. Some of these results are of interest from a merely logical point of view (e.g., syntactic proofs of theorems known in argumentation) some others, I argue, also from the point of view of argumentation theory itself (e.g., adequate games for Dung semantics, or invariance notions such as bisimulation).
- lundi 7 novembre a 14h en salle du conseil
Table ronde sur le sujet du lexique et de l'espace. Intervenants: J. Pustejovsky, N. Asher (IRIT), P. Muller (IRIT), C. Rétoré (Labri, Bordeaux), Richard Moot (Labri, Bordeaux)
- lundi 7 novembre a 10h dans l'Auditorium de l'IRIT
James Pustejovsky (Brandeis University) "Representing Space in Language"
- mardi 6 ??? novembre 2011 a 14h en salle 001 (rdc)
Marcelo Finger (University of Sao Paulo) "A Modal view of Probabilistic Logic"
ABSTRACT. We introduce recent results on probabilistic logic and probabilistic satisfiability. We then show that, when the notion of probabilistic satisfiability is extended to probabilistic inference, a modal view of probabilistic logic naturally arises. We then take this modal view to deal with the problem of contextual probability and conditional probability as a bimodal logic.
- vendredi 4 novembre a 16h en salle des thèses
Frédéric Moisan "An Epistemic Logic of Extensive Games"
ABSTRACT: The aim of this work is to propose a logical framework for representing interacting agents in the context of extensive form games. Because of the importance of the temporal dimension provided by such games, we create a modal epistemic logic that allows to quantify over both strategies and vertices within the game tree. The first part of the article is devoted to the logic itself with the definition of its language and its semantics. In order to illustrate the use of this logic, we define, in the following part, the concept of rationality in the case of extensive form games and the backward induction concept, as they are defined by Robert Aumann. Based on these definitions, we then provide a syntactic proof of Aumann’s theorem that states the following: "for any non degenerate game of perfect information, common knowledge of rationality implies the backward induction solution". We finally propose an in-depth formal analysis of the hypotheses that are needed to prove such a theorem.
- vendredi 4 novembre de 10h a 13h en salle du conseil
Nicholas Asher "Lexique, semantique, types, concepts, catégories" (tutoriel)
- jeudi 20 octobre a 10h en salle 175
Mehdi Dastani (University of Utrecht) "Normative mechanism design"
- mardi 18 octobre a 14h en salle des thèses
Thomas Bolander (Denmark Technical University) "Epistemic planning for single- and multi-agent systems"
- jeudi 13 octobre a 14h en *salle du conseil*
Radnakrishnan Delhi Babu (Anna University, India) "Knowledge representation and reasoning in database and robotics (Reiter views)"
- lundi 29 aout a 14h en salle du conseil
Cedric Degremont "Temporal representations of DEL: the role of informational equivalence"
ABSTRACT. What are the epistemic temporal properties characterizing DEL updaters? We discuss to what extent the answer is dependent on an underlying notion of informational equivalence. (This joint and ongoing work with Tomohiro Hoshi, Benedikt Löwe and Andreas Witzel).
- vendredi 8 juillet a 14h en *salle du conseil*
Henri Prade "De l’organisation hexagonale des concepts de Blanché à l’analyse formelle de concepts et à la théorie des possibilités"
RESUME. L'exposé introduit tout d’abord un cube d’oppositions qui associe le traditionnel carré des oppositions au carré dual obtenu par réciprocation (au sens de Piaget). On montre ensuite que l’extension de Blanché du carré des oppositions en une structure hexagonale conceptuelle repose toujours sur une partition abstraite à 3 éléments. Considérer des partitions à 4 éléments permet d’organiser les 16 connecteurs binaires en un tétraèdre régulier. Enfin, on montre que le cube d’oppositions, une fois interprété en termes modaux, correspond à une généralisation récente de l’analyse formelle de concepts, où des hexagones remarquables apparaissent. Cette généralisation de l’analyse formelle de concepts a été motivée par un parallèle avec la théorie bipolaire des possibilités qui est basée sur 4 fonctions d’ensembles, lesquelles, quoique graduées, peuvent être structurées de manière similaire.
Pierre Bisquert "Changement dans un système d’argumentation : suppression d’un argument"
RESUME. Cet exposé traitera d’un problème particulier du changement dans un système d’argumentation : la suppression d’un argument et de ses interactions. Nous étudierons un exemple issu du contexte juridique justifiant cette opération et nous donnerons quelques propriétés désirables.
- vendredi 1 juillet a 14h en *salle du conseil*
Martin Cooper "Tractable triangles"
ABSTRACT. We study the computational complexity of binary valued constraint satisfaction problems (VCSP) given by allowing only certain types of costs in every triangle of variable-value assignments to three distinct variables. We show that for several computational problems, including CSP, Max-CSP, finite-valued VCSP, and general-valued VCSP, the only non-trivial tractable classes are the well known maximum matching problem and the recently discovered joint-winner property.
Guillaume Escamocher "Mapping Out the Tractability of 3-Variable Forbidden Patterns"
ABSTRACT. Identifying the exact frontier between tractable and intractable classes of Constraint Satisfaction Problems (CSP) is a fundamental problem in complexity theory. Going beyond tractable classes defined by restrictions either on the language of constraint relations or on the structure defined by the set of constraint scopes, we study classes of CSP instances defined by forbidding subproblems. This approach has already led to the identification of properties defining new tractable classes, such as the broken-triangle property (BTP), which generalises tree-structured instances, and the crisp version of the joint-winner property which generalises a set of non-overlapping AllDiff constraints. As a first step in the search for new tractable classes defined by forbidden subproblems, we have begun a systematic study of the tractability of classes of binary CSP instances defined by forbidding 3-variable patterns. We present a set of possible supports for tractable patterns, which can be viewed as a necessary condition for a pattern to be tractable, and which greatly reduces the number of open cases left to study. We also give a characterization of the complexity of all (but two) patterns which satisfy some given properties on their size.
- vendredi 17 juin a 14h en salle des theses
Levan Uridia (Universidad Politecnica de Madrid) "Common Belief of Normal Agents"
ABSTRACT. We introduce the modal logic K4C2 of common belief for normal agents. We prove Kripke completeness and show that the logic has tree model property. As a main result we prove that K4C2 is the modal logic of all TD-intersection closed, bi-topological spaces with derived set interpretation of modalities. Based on the splitting translation we discuss connections with S4C2, the logic of common knowledge.
mercredi 8 juin a 14h en salle des theses
Mario Verdicchio (University of Bergamo) "Speech acts as commitment manipulation in artificial institutions"
ABSTRACT. Communication has been traditionally defined in terms of agents' mental states. From the perspective of the creation of open multiagent systems without any assumption on their implementation, mental states do not look adequate to define the semantics of communication languages. A semantic proposal oriented towards commitments between agents is put forward, within the context of a language viewed as an artificial institution comprised of an ontology, authorizations, conventions, and norms.
- vendredi 27 mai a 14h en salle du CONSEIL
Levan Uridia (Universidad Politecnica de Madrid; joint work with David Pearce) "An Approach to Minimal Belief via Objective Belief"
ABSTRACT. As a doxastic counterpart to epistemic logic based on S5 we study the modal logic KSD that can be viewed as an approach to modelling a kind of objective and fair belief. We apply KSD to the problem of minimal belief and develop an alterna-tive approach to nonmonotonic modal logic using a weaker concept of expansion. This corresponds to a certain minimal kind of KSD model and yields a new type of nonmonotonic doxastic reasoning.
- jeudi 26 mai a 15h30 en salle du CONSEIL
Andrew Jones (King's College, London) "On the characterization of emotions and trust"
paper presented at the workshop "Trust in Agent Societies" at AAMAS 2011
- vendredi 13 mai a 14h en salle des theses
Emiliano Lorini "The cognitive structure of expectation-based emotions: qualitative and quantitative aspects"
ABSTRACT. This work is aimed at providing a logical analysis of the notion of expectation and of expectation-based emotions such as hope, fear, disappointment and relief. I will first introduce a dynamic logic of knowledge, graded belief and graded goal in which the two basic components of an expectation can be formalized: the value of the goal and the strength of the belief. Then, I will provide a formal analysis of the intensity of expectation-based emotions such as the intensity of hope and fear, and the intensity of disappointment and relief.
- mercredi 11 mai 2011 a 14h en salle des theses
Tiago de Lima (CRIL, University of Artois and CNRS) "Coalition Announcement Logic with Physical Actions"
ABSTRACT: A formalism called Coalition Announcement Logic with Physical Actions (CALPA) is presented. It can be seen as an extension of Coalition Announcement Logic (CAL), proposed by Agotnes et al.. As well as CAL, CALPA has modal operators enabling to express sentences like 'there is an action A by group of agents G after which consequence P is true, in spite of what the other agents do'. The difference here, is that such action A can also be a physical action, and not only public announcements, as in CAL. In addition, a sound and complete axiomatization for CALPA is presented (which is missing in Agotnes et al.’s work). Comparisons with several logics are drawn: CALPA subsumes Public Announcement Logic with Assignment and Arbitrary Announcement Logic, and we also compare CALPA with Coalition Logic and Alternating-time Temporal Logic.
- vendredi 22 avril a 14h15 en salle 001
Nadine Guiraud "The face of emotions: a logical formalization of expressive speech acts"
SUMMARY: I will present you the article we publish in AAMAS'11, on expressive speech acts formalized in logic. In this paper, we merge speech act theory, emotion theory, and logic. We propose a modal logic that integrates the concepts of belief, goal, ideal and responsibility and that allows to describe what a given agent expresses in the context of a conversation with another agent. We use the logic in order to provide a systematic analysis of expressive speech acts, that is, speech acts that are aimed at expressing a given emotion (e.g. to apologize, to thank, to reproach, etc.).
- vendredi 8 avril a 10h en salle des theses
Valentin Goranko (Technical University of Denmark) "A framework for modeling, logical specification, analysis and synthesis of multi-agent systems"
ABSTRACT: I will present and discuss a framework for modeling of concurrent games with incomplete information in multi-agent systems over state spaces built on vectors of values of system variables for which every agent has specified rights of access and change. This framework combines and extends features of several well-studied models including interpreted systems, concurrent game structures, and reactive modules. I will argue that this framework can adequately model various situations and problems arising in distributed multi-agent systems, in particular related to information security, and will present a logical formalism for specification, analysis and synthesis of multi-agent systems.
- vendredi 25 mars a 14h
François Schwarzentruber "Trois outils pédagogiques pour l'enseignement de la logique" (durée : 45min à 1h)
RESUME :
1) SAToulouse est une interface utilisateur destinée aux étudiants afin qu'ils puissent tester la satisfiabilité de formules (basé sur le solveur SAT4J). Les applications sont mises en valeur : résoudre un sudoku, résoudre un problème de coloriage, un emploi du temps, un problème de planification, etc.
2) Panda est un outil pour construire des preuves en déduction naturelle pour la logique des prédicats. L'étudiant a accès à une série de preuves à construire. Il peut manipuler les arbres de preuves : les déplacer, les supprimer, les connecter, appliquer une règle de déduction naturelle en avant et en arrière.
3) Plaza's world est un outil pour apprendre la logique modale épistémique et les annonces publiques. Il offre des modèles de Kripke concrets sur lesquels on peut faire du model-checking.
- vendredi 4 mars a 14h en salle des theses
Daniel Sanchez (European Centre for Soft Computing, Mieres, Asturias) "Linguistic Data Description and Summarization"
ABSTRACT: In this talk I will show a particular view about the area often called "Linguistic Data Summarization" and some relationships to Data Mining and Reasoning. This view will be illustrated with techniques proposed and projects developed both at the European Centre for Soft Computing and the University of Granada.
Henry Soldano (Paris XIII) "De l'Apprentissage Artificiel à une logique modale pour l'Abstraction"
RESUME: En analyse de concepts formels (FCA) ou Galoisienne, la relation entre d'une part, les énoncés d'un langage L formant un treillis pour la relation de généralité, et, d'autre part, leur extension sur un ensemble d'instances W, est matérialisée en un treillis "intension/extension" G, dont chaque noeud représente un ensemble d'énoncés ayant même extension sur W. Ce treillis peut être réduit tout en préservant l'ordre et la structure de treillis, en définissant une extension abstraite ext'=p°ext où p satisfait certaines propriétés et est appelée une projection.
Dans la première partie de cette présentation, je remarquerai d'abord qu'à toute projection est associée un ensemble A de parties de W fermé par réunion que nous appèlerons une "abstraction", et inversement, et que ces abstractions forment elle-même un treillis pour un ordre partiel "est-plus abstrait-que". Je discuterai alors des propriétés des implications, dites abstraites, correspondant à l'inclusion des extensions abstraites, et du cas particulier où une abstraction est construite à partir d'une classification a priori des instances et d'un degré alpha d'influence de cette classification sur la granularité.
La deuxième partie de l'exposé est consacrée à la représentation en logique modale obtenue en interprétant une implication abstraite entre p et q comme une implication entre Abstrait p et Abstrait q. En particulier je caractériserai, partant du point de vue sémantique, les classes de logiques modales monotones correspondantes, et discuterait des logiques multimodales utilisant l'ordre sur les abstractions pour mener des raisonnements à plusieurs niveaux d'abstraction.
Enfin, j'évoquerai les relations avec la notion de granularité présente dans les travaux sur les ensembles approximatifs, et les perspectives en Analyse de Concepts, et en Apprentissage Artificiel, ouvertes par cette formulation.
- vendredi 25 fevrier 2011 a 14h en salle des theses
Frederic Maris "Transformation de problèmes de planification"
RESUME: La transformation de problèmes de planification est un nouveau domaine de recherche, développé par l’équipe ADRIA, qui n’a été que très peu exploré. L’objectif est de transformer un problème de planification n'ayant pas une propriété donnée en problème équivalent permettant de vérifier cette propriété. L’extension de l’expressivité des langages de planification temporelle pose le problème de la complétude des algorithmes existants. La plupart d’entre eux sont en effet incomplets et ne peuvent trouver une solution à des problèmes comportant des ensembles cycliques d'actions. Nous avons caractérisé les langages temporels qui permettent de représenter ces problèmes temporellement cycliques et développé une méthode de transformation quadratique de ces problèmes en des problèmes acycliques équivalents. L'application de ce type de transformation permet de rendre complets les planificateurs précédents pour des langages ayant un haut niveau d'expressivité. Nous avons également développé un langage temporel de haut niveau ainsi qu’une transformation quadratique qui permet de compiler les problèmes décrits au moyen de ce langage en langage PDDL. Cela permet à l’utilisateur de posséder un langage plus riche pour décrire le monde tout en ayant la possibilité d’utiliser les planificateurs basés sur PDDL. Cette approche prometteuse permet d’utiliser des algorithmes utilisant des formalismes de bas niveau, opérationnels en pratique sur des systèmes dont les ressources sont limitées, et qui ont fait leurs preuves.
- mardi 15 février a 14h à l'Auditorium de l'IRIT
Nahla Ben Amor "Modèles graphiques probabilistes et possibilistes"
Les modèles graphiques sont des outils importants pour représenter efficacement et analyser des données incertaines dans les systèmes de connaissance. Les représentants les plus éminents de ces modèles se référent à la théorie des probabilités. En particulier, les réseaux bayésiens et les réseaux de Markov ont été largement développés et utilisés dans plusieurs applications réelles. Toutefois, ces réseaux ne sont appropriés que lorsque toutes les données numériques sont disponibles, ce qui n'est pas toujours le cas. En effet, il existe certaines situations, comme le cas de l'ignorance totale, qui peuvent mettre en difficulté le raisonnement probabiliste. Par conséquent, la modélisation graphique ‘non probabiliste’ a récemment émergé comme un nouveau domaine prometteur de la recherche. En particulier, les réseaux possibilistes apparaissent comme une alternative intéressante aux réseaux probabilistes. En effet, la théorie des possibilités propose un cadre approprié pour les experts pour exprimer leurs opinions numériquement en utilisant des degrés de possibilité ou qualitativement en utilisant des pré-ordres sur l'univers du discours. Les modèles probabilistes et les non-probabilistes ne doivent pas être considérés comme concurrentiels, mais comme des outils complémentaires qui doivent être utilisés en fonction du problème et des données disponibles.
La première partie de cet exposé concerne certaines questions sur les réseaux probabilistes, à savoir l'apprentissage des réseaux bayésiens causaux en utilisant les connaissances sémantiques. Elle englobe également une application particulière des réseaux bayésiens dans la gestion des risques dans le cadre d’une approche intégrée Qualité, Sécurité et Environnement (QSE). La deuxième partie concerne les réseaux possibilistes. Une attention particulière sera accordée au problème de propagation. Enfin, nous discuterons de l'aspect décisionnel avec les réseaux possibilistes décisionnels (en particulier, les arbres de décision possibilistes et les diagrammes d'influence possibilistes.
- vendredi 1 fevrier 2011 a 14h en salle des theses
Philippe Balbiani "Deciding the word problem in pure double Boolean algebras"
ABSTRACT: Pure double Boolean algebras are algebraic structures arising from formal concept analysis. They have attracted interest both for their theoretical merits and for their practical relevance. In this talk, we will concentrate on the word problem in pure double Boolean algebras. We will show that this problem is decidable in deterministic polynomial space.
KEYWORDS : Formal concept analysis, pure double Boolean algebras, word problem, computational complexity.
%%%%%%%%%%%%%%% 2010 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- vendredi 17 dec 2010, *A 10H* en salle des theses
Francesca Poggolesi (Univ. Bruxelles) "Proof theory for S5 (and its extensions)"
ABSTRACT: Amongst the several normal systems of modal propositional logic, one of the most important and well-known is S5. From a semantic point of view, S5 is a quite peculiar system since it can be described in two different but equivalent ways. The first one is obtained by specifying some properties that the accessibility relation between worlds of a Kripke frame should satisfy: S5 is indeed valid and complete in the class of reflexive, transitive and symmetric frames (or, equivalently, in the class of reflexive and euclidean frames). A second and easier way to study S5 semantically is obtained by exploiting Kripke frames where the accessibility relation is absent, which is to say, where all the words are equivalent. This second way is evidently simpler. We can therefore conclude that, semantically, S5 happens to be a handy and flexible instrument.
Unfortunately so much cannot be said of the syntactic level; on the contrary, it turns out to be quite a challenge to give a sequent calculus for this system. The efforts in this direction are numerous and each of them presents some diffculties. Our goal in this talk is to present a method, called the tree-hypersequent method (see F. Poggiolesi, Gentzen Calculi for Modal Propositional Logic, Trends in Logic, Springer, 2010), which allows us to construct two different sequent calculi for S5 (each of which naturally reflects one of the ways for describing S5 semantically), and therefore to have even syntactically a handy and flexible instrument.
We will show that both sequent calculi are valid and complete and that they are contraction-free and cut-free. Moreover, the one which corresponds to the S5 semantic variant where the accessibility relation is absent will be unusually simple.
We will conclude the talk by conjecturing that the results explained above can be exploited to provide proof theory for Public Announcement Logic and Dynamic Epistemic Logic.
- vendredi 10 dec 2010, en salle du conseil
Philippe Besnard "Formalismes logiques et inconsistance"
Marta Abrusan "Aboutness and Presuppositions"
Abstract: Some sentences in natural language trigger inferences that survive embedding under certain operators, e.g. negation. An example is the factive inference we get from sentences containing predicates such as 'know'. E.g. (1a) and (1b) both imply that John's father is a spy.
(1) a. John knows that his father is a spy.
b. John does not know that his father is a spy.
This type of inference is called presupposition in the linguistic literature. A long-standing puzzle has been the question what property makes some sentences trigger presuppositions. This talk attempts to provide an answer with respect to presuppositions whose presence can be traced back to verbal predicates. The starting point is the intuition, dating back to Stalnaker (1974), that the information conveyed by a sentence that is in some sense independent from its main point is presupposed. The contribution of the paper presented is to spell out a mechanism for deciding what will become the main point of the sentence and how to calculate independence. It is proposed that this can be done by making reference to event times. As a very rough approximation, the main point of an utterance is what (in a sense to be defined) has to be about the event time of the matrix predicate and the information that the sentence also conveys but is not (or does not have to be) about the event time of the matrix predicate is presupposed. The notion of "aboutness" used to calculate independence is based on that of Demolombe and Farinas del Cerro (2000).
- vendredi 26 nov 2010
H. Fargier (J.M. Astensana, L. Cosserat) "Constraint-based modeling and exploitation of a vehicle range at Renault’s: a complexity study"
- vendredi 24 septembre 2010
Marie-Christine Lagasquie (avec Claudette Cayrol et Caroline Devred,
LERIA) "Comment prendre en compte en argumentation abstraite des attaques pouvant être de qualité différente"
RESUME : Nous nous plaçons dans le cadre de l'argumentation abstraite définie par Dung et notre étude porte sur le cas où les attaques entre
arguments peuvent être comparées au moins partiellement. Dans ce contexte, nous avons pris en compte divers points de vue :
1. L'acceptabilité d'un argument attaqué et défendu peut être remise cause par une attaque défensive trop faible ; on a donc une notion de
qualité de la défense par rapport à un argument donné.
2. L'étape suivante consiste à généraliser cette notion de qualité de la défense à plusieurs arguments pour pouvoir l'appliquer au calcul
d'extensions susceptibles de représenter les ensembles d'arguments les mieux défendus.
3. Il faut ensuite développer un mécanisme constructif pour identifier les preuves d'acceptabilité d'un argument dans ce nouveau contexte ;
on visera alors des preuves optimales au sens de la minimalité et au sens de la qualité des défenses utilisées.
Mots-Clés : argumentation abstraite, sémantiques de Dung, preuves en argumentation
Didier Dubois "Degrees of Truth and Epistemic States"
RESUME : In quite a few, sometimes influential, works dealing with knowledge representation, there is a temptation to extend the truth-set underlying a given logic with values expressing ignorance and contradiction. It then leads to some truth-functional many-valued logic different from the original one, but often using the same syntax. This is the case for instance with partial logic and Belnap bilattice logic with respect to classical logic. It is found again in interval-valued, and type two extensions of fuzzy sets.
This talk insists that neither ignorance nor contradiction cannot be viewed as additional truth-values nor processed in a truth-functional manner, and that doing it leads to weak or debatable uncertainty handling approaches. A similar difficulty is also found in three-valued logics of rough sets.
In fact, partial ignorance and contradiction are meta-level notions, like deduction and consistency and refer to epistemic states. When using the same language for modeling epistemic and objective notions, there is no way to tell the case of not believing a proposition from believing its contrary, not to tell the case of knowing that one among several propositions is true from the case of knowing that their disjunction is true. Modal logics have been used to handle epistemic notions in a more satisfactory way, but the Kripke semantics based on relations over possible worlds are perhaps unnecessarily complex to handle plain notions of epistemic states. A simpler semantics can be based on sets of epistemic states understood as non-empty subsets of interpretations.
We suggest that, in order to handle epistemic notions at the language level, we need two-tiered systems where one logic (typically propositional logic) describing events is encapsulated by another one (that can be many-valued) describing beliefs or testimonies. Such an approach paves the way to a general approach to logics of uncertainty, along the lines suggested by Esteva, Godo and Hajek casting probability, possibility or belief functions within a suitable multiple-valued setting, where beliefs are graded, but events remain Boolean.
- vendredi 10 septembre 2010
Pawel Zielinski "Computing robust solutions in combinatorial optimization problems with uncertain data"
ABSTRACT: In the talk, we discuss a class of combinatorial optimization problems with uncertain weights. We first consider the case when the weights in the problems are modeled as closed intervals. We show how the notion of optimality can be extended by using a concept of a deviation interval. In order to choose a solution, we adopt a robust approach. We seek a solution that minimizes the maximal regret, that is the maximal deviation from optimum over all weight realizations, called scenarios, which may occur.
We then explore the case in which the weights are specified as fuzzy intervals in the setting of possibility theory. Fuzzy weights induce a possibility distribution over the scenario set and the possibility and necessity measures can be used to extend the optimality evaluation and the min-max regret approach. We show that the use of possibility theory leads to finding robust solutions under fuzzy weights.
Finally, we discuss the discrete scenario case in which uncertainty of weights are modeled by explicitly specifying a set of all possible realizations of the weights (scenarios). To choose a solution, we adopt two robust criteria: the min-max and the min-max regret.
The complexity and approximability of all discussed problems under assumed uncertainty representations and solution concepts are explored.
- vendredi 9 juillet 2010
Cedric Degremont "Agreement theorems and dynamic epistemic logics"
- jeudi 8 juillet 2010
Sylvain Pogodalla (Chargé de Recherche, LORIA-INRIA Nancy) "L'interface syntaxe-sémantique du point de vue des Grammaires Catégorielles Abstraites"
RESUME : Partant d'une réflexion générale sur les formalismes grammaticaux et sur la nature de l'interface syntaxe-sémantique qu'ils proposent (telle que proposée par Jackendoff (2002)), nous étudierons différents encodages de formalismes (TAG, Grammaires Catéorielles, Convergent Grammar) à l'aide des Grammaires Catégorielles Abstraites (ACG, de Groote (2001)). Nous montrerons comment se traduisent les solutions adoptées par chacun de ces formalismes. La comparaison nous permettra de donner un point de vue sur cette interface, et notamment sur sa réalisation en tant que fonction ou en tant que relation.
- vendredi 2 juillet 2010 SALLE DU CONSEIL
Srdjan Vesic "On the role of preferences in argumentation"
ABSTRACT: Different proposals have been made in the literature for integrating preferences between arguments in an argumentation framework. The idea was to ignore an attack if the attacked argument is stronger than its attacker. We show that these proposals may return unintended results, in particular when the attack relation is asymmetric.
We propose a new approach for taking preferences into account. The idea is to extend existing semantics by introducing preferences on the semantics level. In case that all arguments are equally preferred or if preferences do not conflict with the attacks, the extensions of new semantics coincide with those of the basic ones. Besides, our approach allows to compare all pairs of sets of arguments contrary to existing approaches that simply separate them in extensions and non-extensions. We propose three relations that generalize respectively stable, preferred and grounded semantics. Then, we focus on stable semantics and study all possible relations that generalize this semantics. We also show that there exist a bijection between a particular case of our framework and sub-preferred theories introduced by Brewka.
F. Dupin de Saint-Cyr "Change in Abstract Argumentation Frameworks: Adding an Argument"
ABSTRACT: We address the problem of change in an abstract argumentation system. We focus on a particular change: the addition of a new argument which interacts with previous arguments. We study the impact of such an addition on the outcome of the argumentation system, more particularly on the set of its extensions. Several properties for this change operation are defined by comparing the new set of extensions to the initial one, these properties are called structural when the comparisons are based on set-cardinality or set-inclusion relations. Several other properties are proposed where comparisons are based on the status of some particular arguments: the accepted arguments; these properties refer to the evolution of this status during the change, e.g., Monotony and Priority to Recency. All these properties may be more or less desirable according to specific applications. They are studied under two particular semantics: the grounded and preferred semantics.
- vendredi 25 juin a 14h, Salle du Conseil
Renata Wassermann "Belief revision for Horn logic" (KR 2010, with Jim Delgrande)
ABSTRACT: Standard approaches to belief change assume that the underlying logic contains classical propositional logic. Recently, there has been interest in investigating approaches to belief change, specifically contraction, in which the underlying logic is not as expressive as full propositional logic.
In this talk we consider approaches to belief contraction in Horn knowledge bases. We develop two broad approaches for Horn contraction, corresponding to the two major approaches in belief change, based on Horn belief sets and Horn belief bases. We provide constructions and sets of postulates for maxichoice and partial-meet operators together with representation postulates and we show that problems arising with earlier work are resolved by these approaches.
H. Fargier "Knowledge Compilation in the Modal Logic S5" (AAAI'2010, avec M. Bienvenu et P. Marquis)
RESUME: In this paper, we study the knowledge compilation task for propositional epistemic logic S5. We first extend many of the queries and transformations considered in the classical knowledge compilation map to S5. We then show that the standard notion of disjunctive normal form DNF can be profitably extended to the epistemic case; we prove that the DNF fragment of S5, when appropriately defined, satisfies in polytime the same queries and transformations than its classical counterpart, namely, consistency, clausal entailment, conditionning, forgetting, disjunction and bounded conjunction.
We also show that no similar extension to the S5 case can be achieved for OBDD, DNNF and related fragments because Shannon expansion does not hold in this logical setting.
- vendredi 11 juin a 14h, Salle du Conseil
Leila Amgoud (avec Philippe Besnard) "Logical limits of Dung’s abstract argumentation framework"
RESUME: Dung’s abstract argumentation framework takes as input a set of arguments and a binary relation encoding attacks between these arguments, and returns different extensions of arguments. No indication is given on how to instantiate this setting, i.e., how to build arguments from a knowledge base and how to choose an appropriate attack relation. This leads in some cases to undesirable results like inconsistent extensions (i.e., the set of formulas forming an extension is inconsistent). This is due to the gap between the abstract setting and the knowledge base from which it is specified. Moreover, different acceptability semantics have been defined for evaluating arguments. It is not clear: i) whether these different acceptability semantics really make sense for concrete applications, and ii) what are the results that can be returned in a given application by each semantics.
The purpose of this paper is threefold: First it proposes to fill in the abovementioned gap by extending Dung’s framework. The idea is to consider all the ingredients involved in an argumentation problem. We start with an abstract monotonic logic which consists of a set of formulas and a consequence operator. We show how to build arguments from a knowledge base using the consequence operator of the logic. Second, we show that the choice of an attack relation is crucial for ensuring sound results, and thus should not be arbitrary. Third, we characterize the different semantics in terms of subsets of the knowledge base that are captured by each extension. We show that existing acceptability semantics as well as the corresponding concepts like defense are essentially meaningless. Indeed, extensions under any semantics amount to a random choice of some consistent subbase of a knowledge base. This means that rationality eludes these semantics. The main reason of this defect is the attack relation that features a seemingly unjustified preference among subsets of an inconsistent set of formulas.
Philippe Balbiani "Modal logics for region-based theories of space"
RESUME: The aim of this talk is to give new kinds of propositional modal logics suitable for reasoning about regions in region-based theories of space. We call them region-based propositional modal logics of space – RPMLS. The language L(?,C) of RPMLS contains Boolean variables and standard Boolean operations needed for constructing Boolean terms interpreted later on by the corresponding regions in some models of region-based theory of space. The language contains two symbols: ? for the part-of relation and C for the contact relation. Atomic formulas are of the form a ? b and aCb, where a, b are Boolean terms, and complex formulas are built from the atomic ones by means of the propositional connectives. In a sense L(?,C) is a first-order language without quantifiers, but we call it modal because many things typical of ordinary modal languages can be applied to it: relational Kripke style semantics, filtration, modal definability, p-morphisms, canonical models, etc. The relational semantics corresponds to the discrete models of the region-based theory of space, based on adjacency spaces. That is why we sometimes use the name discrete semantics. We also give a topological semantics for the language in which regions are regular closed sets in some topological space. For the logics based on the discrete semantics, we establish various modal definability results. We give axiomatization and completeness theorems with respect to both relational and topological semantics for several important RCC-like logics. We show that the relational interpretation of the language of RPMLS is also suitable for studying graphs. We study some logics suitable for describing properties of graphs like the property of colourability and connectedness.
- vendredi 4 juin a 14h
Martin Cooper (en collaboration avec Standa Zivny de l'Université d'Oxford) "Une nouvelle classe traitable de problèmes de satisfaction de contraintes valuées"
RESUME : Le VCSP (Valued Constraint Satisfaction Problem) est un problème combinatoire générique qui permet d'exprimer de nombreux problèmes issus de l'Intelligence Artificielle, la Recherche Opérationnelle, la bioinformatique, etc. Le VCSP est NP-difficile, mais pour certaines classes d'instances VCSP, il existe un algorithme de complexité polynômiale. Un défi théorique important est d'identifier toutes ces classes traitables. On obtient une classe sémantique en plaçant des restrictions sur le type des contraintes valuées (par exemple, les fonctions sous-modulaires). On obtient une classes syntactique en plaçant des restrictions sur le graphe des contraintes (par exemple, la largeur d'arbre bornée par une constante).
Une caractérisation de toutes les classes traitables d'instances VCSP doit aussi prendre en compte les classes hybrides qui sont ni sémantique ni syntactique. On peut définir des classes hybrides par rapport à des propriétés de sous-problèmes. Nous présenterons une règle simple (sur tous les sous-problèmes de taille 3) qui permet de définir une nouvelle classe traitable hybride. Un exemple d'un problème dans cette classe est l'ordonnancement de machines.
Florence Bannay (travail avec L. Amgoud présenté à ECSQARU 2009 et MFI'09) "Extraire le noyau d'un dialogue de persuasion pour évaluer sa qualité"
RESUME : Un dialogue de persuasion est un dialogue dans lequel les agents échangent des arguments à propos d'un sujet. Dans ce type de dialogue, les agents ne sont pas d'accord sur le statut du sujet et chacun essaye de persuader les autres de changer d'avis. Dans la littérature, plusieurs systèmes fondés sur la théorie de l'argumentation ont été proposés pour modéliser les dialogues de persuasion.
Il est important de pouvoir analyser la qualité de ces dialogues.
Dans ce travail, nous proposons un critère de qualité qui concerne la "concision" du dialogue. Un dialogue est concis si tous ses coups sont appropriés et utiles pour obtenir le même résultat. À partir d'un dialogue de persuasion, on calcule le dialogue ``idéal'' lui correspondant. Ce dialogue idéal est concis. Un dialogue de persuasion est considéré intéressant s'il est proche de son dialogue idéal.
- jeudi 3 juin 2010 a 17h
Joao Marcos (Univ. Federal do Rio Grande do Norte, Bresil et Univ. Technique de Vienne, Autriche) "Tableaux for multivalued modal logics"
- vendredi 28 mai de 14h a 16h
Steven Schockaert
"Fuzzy equilibrium logic: declarative problem solving in continuous domains"
RESUME : Answer set programming (ASP) is a form of logic programming which is based on the notion of stable models. In its basic form, ASP offers a purely declarative way of solving combinatorial problems at the first level of the polynomial hierarchy. Since its introduction, ASP has been generalized in a number of ways. As one of the most general "classical"' approaches, answer sets of arbitrary propositional theories can be defined as models in the equilibrium logic of Pearce. From an application point of view, this allows to tackle problems at the second level of the polynomial hierarchy.
Furthermore, due to the model-based definition of answer sets, equilibrium logic has turned out to be particularly useful for studying the semantics of programs (e.g. verifying whether particular types of equivalence hold between different programs). Another generalization of ASP is fuzzy answer set programming (FASP), which is a variant of ASP that is based on fuzzy logics. This particular use of fuzzy logics adds to ASP the capability of solving problems in continuous domains. Finally, also possibilistic answer set programming (PASP) has been proposed, by attaching to each rule a degree of certainty or priority. After giving a general introduction to ASP, equilibrium logic, FASP and PASP, I will briefly show how a fuzzy version of equilibrium logic can be obtained, generalizing at the same time equilibrium logic and FASP. To illustrate the modeling power of the resulting framework, I will focus on two application examples: finding strong Nash equilibria with continuous strategies, and finding abductive explanations in Lukasiewicz logic.
Ivan José Varzinczak (Knowledge Representation and Reasoning group, Meraka Institute, CSIR - Pretoria, South Africa) : "Pertinence Construed Modally"
RESUME : Capturing the notion of pertinence or relevance in logic is usually attempted at the meta-level. It can be induced either by specific extra information, or by general philosophical principles. In this work we pay attention to both these origins. We present a semantic modal interpretation of the idea that there are two distinct relationships between a premiss and a conclusion that are pertinent to each other: of semantic entailment in the forward direction from A to B, and of semantic constraint in the backward direction from B to A. Unpacking the notion of pertinence into these two semantic components yields a class of entailment relations with appealing.
We define an entailment relation via a modal logic, and investigate its behaviour as a viable candidate for capturing the notion of pertinence. This approach allows us to deal with a number of paradoxes of material and strict implication (e.g. positive paradox), as well as some counter-intuitive properties of classical (and modal) entailment (e.g. explosiveness and disjunctive syllogism), in a satisfactory way. Furthermore, the resulting logic is infra-modal, non-monotonic, and allows for non-trivial reasoning with inconsistencies.
Keywords: Pertinence, modal logic KT, infra-modal entailment, non-explosiveness, non-monotonicity.
(This is joint work with Katarina Britz and Johannes Heidema.)
- vendredi 21 mai a 14h
Walter Carnielli, U. Campinas, Centre de Logique, Epistemologie et Histoire des Sciences (CLE) et Departement de Philosophie : "Logiques en format polynomial"
RESUME : Nous allons montrer que beaucoup de logiques peuvent etre exprimées en format polynomial avec des coefficients sur les corps de Galois finis. Cela s'applique a tous les logiques multi-valués finis ainsi qu'aux logiques paraconsistantes, beaucoup de logiques modales et un certain fragment de la logique du premier ordre. On obtient ainsi un nouveau mode de calcul avec des propriétés intéressantes.
- jeudi 6 mai a 14h (salle 157)
Walter Carnielli, U. Campinas, Centre de Logique, Epistemologie et Histoire des Sciences (CLE) et Departement de Philosophie : "Introduction aux logiques de l'inconsistance formelle et semantiques de traductions possibles" ("Introduction to the logics of formal inconsistency and possible-translation semantics")
Juliana Bueno-Soler, Federal University of ABC - UFABC, Center for Natural and Human Sciences - CCNH, Santo André, Brazil : "Paraconsistent Multimodalities towards Description Logic"
RESUME : Recent work on paraconsistent modalities intended to expand the multimodal apparatus with the interest on developing methods to deal with paraconsistent modalities,introducing tools such as the modal possible-translations semantics.
With the aim of expanding the applicabilty of modal paraconsistent logic beyond the traditional interest on deontic paradoxes, our proposal is to have multimodal paraconsistent systems to add expressivity power to Description Logics.
In this seminar some procedures to obtain multimodal paraconsistent systems and its alternative characterization w.r.t. modal possible translations semantics will be discussed. In the sequel will also discuss how could a connection between multimodal paraconsistent logic and Description Logic be thought to give a solution to certain problems in Description Logic related to managing contradictions.
- vendredi 2 avril a 11H (salle du conseil)
Laure Vieu "On the compositionality of temporal locating adverbial modification"
- vendredi 26 mars a 14H (salle des theses)
Andreas Herzig, Nicolas Troquard "The dynamic logic of propositional control"
RESUME : Along the lines of Coalition Logic of Propositional Control (CLPC), we propose a dynamic logic of propositional control DLPC. It extends classical propositional logic by a variety of modal operators of assignment, and modal operators of transfer of control over a propositional variable. We also present an epistemic extension. We establish the relationship of these logics with the existing CLPC and with its extension by control transfer DCLPC. We study their complexity and their proof theory.
- vendredi 19 mars a 14H (salle du conseil)
Emiliano Lorini "A model of intention and plan dynamics"
Frédéric Maris "Complétude des algorithmes de planification temporellement
expressifs"
RESUME: Un des challenges actuels de la planification est la prise en compte de la dimension temporelle qui permet de mieux modéliser des problèmes issus du monde réel. Parmi ceux-ci, nombreux sont ceux dont la résolution nécessite la concurrence de certaines actions (problèmes temporellement expressifs). Cependant, les planificateurs qui peuvent résoudre ce type de problèmes sont pour la plupart incomplets car ils s'avèrent incapables de trouver une solution à une catégorie de problèmes comportant des ensembles cycliques d'actions (problèmes temporellement cycliques). Dans cet article, nous caractérisons les langages temporels qui permettent de représenter ces problèmes temporellement cycliques, puis nous proposons une méthode de transformation quadratique de ces problèmes en des problèmes acycliques équivalents. L'application de notre algorithme permet de rendre complets les planificateurs précédents.
ABSTRACT: In order to correctly model certain real-world planning problems, it is essential to take into account time. This is the case for problems requiring the concurrent execution of actions (known as temporally-expressive problems). However, we show in this paper that most existing planners which solve this type of problem are, in fact, incomplete. They cannot guarantee to find a solution to a problem involving sets of cyclically-dependent actions (which we call temporally-cyclic problems). We characterize those temporal planning languages which can express temporally-cyclic problems. We also present a polynomial-time algorithm which transforms a temporally-cyclic problem into an equivalent acyclic problem. Applying our transformation restores the completeness of existing temporal planners.
- lundi 15 mars a 14H (salle theses)
Standa Zivny (University of Oxford) "Submodularity and Valued Constraint Satisfaction Problems"
ABSTRACT: In this talk, I will present the concept of submdodularity and relate it to certain optimisation problems, which can be described as Valued Constraint Satisfaction Problems. It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. We answer the problem negatively. We also show several corollaries of this result, including the problem of which submodular functions can be minimised using the Min-Cut/Max-Flow techniques.
- vendredi 19 fevrier 2010 a 14H
Nicholas Asher "Dynamic semantics, discourse semantics and continuations"
----------- DATA MISSING -------------
- vendredi 21 sept 2007 a 14h en salle des theses
Guilin QI (joint work with Tony Hunter), "Measuring incoherence in DL-based ontologies"
Philippe Balbiani et Andreas Herzig, "Comment decrire un modele de Kripke fini par une formule modale finie"
- mardi 11 septembre a 14h en salle des theses
Guilin QI, "A model-based approach for merging prioritized knowledge bases in possibilistic logic"
Emiliano Lorini, "Grounding power on actions and mental attitudes"
- vendredi 2 mars a 14h en salle des theses
Caroline Devred (CRIL, Lens) "Fusion de systèmes d'argumentation"
- mardi 30 jan a 14h en salle des theses
Nicholas Asher "Three puzzles about modality"
Caroline THIERRY "Gestion de chaînes logistiques : Modèles et mise en œuvre pour l’aide à
la décision à moyen terme"
Claudette Cayrol et Marie-Christine Lagasquie-Schiex "Coalitions en argumentation"
- mardi 24 octobre a 14h en salle des theses
Martin Cooper "Arc cohérence virtuelle et optimale dans les problèmes d'optimisation"
Sébastien Destercke "Fusion d'opinions d'experts et théories de l'incertain"
Didier Dubois "Trois facons de voir la revision des croyances"
- mardi 3 octobre a 14h en salle des theses
Ivan José Varzinczak "On the modularity of ontologies"
Elise Bonzon "Jeux booleens et representation des preferences"
- vendredi 29 septembre a 14h
Henri Prade "Logique possibiliste multi-agent"
Leila Amgoud and Florence Bannay "Towards ACL semantics based on commitments and penalties"
Benoit Gaudou "A New Semantics for the FIPA Agent Communication Language based on Social Attitudes"
- vendredi 22 septembre a 14h
Masabumi Furuhata "Capacity Allocation with Competitive Retailers"
Carole Adam "Les emotions: une formalisation logique fidele à la psychologie"
Robert Demolombe "Belief revision in the Situation Calculus"
Mounira Kourjieh "A symbolic intruder model for hash-collision attacks"
- mardi 19 septembre a 14h
Philippe Balbiani "L'équivalence logique des modèles de la logique modale"
Alexander Nittka "A method for reasoning about an agent based on its revision history"
Emiliano Lorini "A cognitive model of surprise: from ontology to belief change"