Skip to main content

Über dieses Buch

This book is dedicated to Marek Sergot, Professor in Computational Logic at Imperial College London, on the occasion of his 60th birthday. Professor Sergot’s scientific contributions range over many different fields. He has developed a series of novel ideas and formal methods bridging areas including artificial intelligence, computational logic, philosophical logic, legal theory, artificial intelligence and law, multi-agent systems and bioinformatics. By combining his background in logic and computing with his interest in the law, deontic logic, action, and related areas, and applying to all his capacity to understand the subtleties of social interaction and normative reasoning, Professor Sergot has opened up new directions of research, and has been a reference, an inspiration, and a model for many researchers in the fields to which he has contributed. The Festschrift includes several reminiscences and introductory essays describing Professor Sergot's achievements, followed by a series of articles on logic programming, temporal reasoning and action languages, artificial intelligence and law, deontic logic and norm-governed systems, and logical approaches to policies.



Marek Sergot: A Memoir

Marek Sergot: A Memoir

This short memoir will recall some memories of Marek as a colleague, mentor, friend and external examiner.
Trevor Bench-Capon

The Scientific Contribution of Marek Sergot

Marek Sergot’s technical contributions range over different subjects. He has developed a series of novel ideas and formal methods bridging different research domains, such as artificial intelligence, computational logic, philosophical logic, legal theory, artificial intelligence and law, multi-agent systems and bioinformatics.
By combining his background in logic and computing with his interest in the law, deontic logic, action, and related areas, and applying to all his capacity to understand the subtleties of social interactions and normative reasoning, Marek has been able to open new directions of research, and has been a reference, an inspiration, and a model for many researchers in the many fields in which he has worked.
Steve Barker, Andrew J. I. Jones, Antonis Kakas, Robert A. Kowalski, Alessio Lomuscio, Rob Miller, Stephen Muggleton, Giovanni Sartor

Part I: Logic Programming

Teleo-Reactive Abductive Logic Programs

Teleo-reactive (TR) programs are a variety of production systems with a destructively updated database that represents the current state of the environment. They combine proactive behaviour, which is goal-oriented, with reactive behaviour, which is sensitive to the changing environment. They can take advantage of situations in which the environment opportunistically solves the system’s goals, recover gracefully when the environment destroys solutions of its goals, and abort durative actions when higher priority goals need more urgent attention.
In this paper, we present an abductive logic programming (ALP) representation of TR programs, following the example of our ALP representation of the logic-based production system language LPS. The operational semantics of the representation employs a destructively updated database, which represents the current state of the environment, and avoids the frame problem of explicitly reasoning about the persistence of facts that are not affected by the updates. The model-theoretic semantics of the representation is defined by associating a logic program with the TR program, the sequence of observations and actions, and the succession of database states. In the semantics, the task is to generate actions so that all of the program’s goals are true in a minimal model of this associated logic program.
Robert A. Kowalski, Fariba Sadri

Semi-negative Abductive Logic Programs with Implicative Integrity Constraints: Semantics and Properties

We propose a novel semantics for semi-negative abductive logic programs (i.e. where the only negative literals are abducibles) with implicative integrity constraints (i.e. in the form of implications). This semantics combines answer set programming (with the implicative integrity constraints) and argumentation (for relevant explanations with the logic program, supported by abducibles). We argue that this semantics is better suited than the standard semantics to deal with applications of abductive logic programming and prove some properties of this semantics. We motivate our approach in an agent-based access control policy scenario.
Paolo Mancarella, Francesca Toni

What Is Negation as Failure?

An equational approach is used to give semantics to negation as failure. We offer an Equational Calculus and in it we define a new completion for programs with negation as failure in the body of clauses. This approach is compared with other approaches in the literature and a connection is established with argumentation theory.
Dov M. Gabbay

Part II: Temporal Reasoning and Action Languages

The Importance of the Past in Interval Temporal Logics: The Case of Propositional Neighborhood Logic

In our contribution, we study the effects of adding past operators to interval temporal logics. We focus our attention on the representative case of Propositional Neighborhood Logic (\(\mathsf{A \overline A}\) for short), taking into consideration different temporal domains. \(\mathsf{A \overline A}\) is the proper fragment of Halpern and Shoham’s modal logic of intervals with modalities for Allen’s relations meets (future modality) and met by (past modality). We first prove that, unlike what happens with point-based linear temporal logic, \(\mathsf{A \overline A}\) is strictly more expressive than its future fragment A. Then, we show that there is a log-space reduction from the satisfiability problem for \(\mathsf{A \overline A}\) over ℤ to its satisfiability problem over ℕ. Compared to the corresponding reduction for point-based linear temporal logic, the one for \(\mathsf{A \overline A}\) turns out to be much more involved. Finally, we prove that \(\mathsf{A \overline A}\) is able to separate ℚ and ℝ, while A is not.
Dario Della Monica, Angelo Montanari, Pietro Sala

Argumentation and the Event Calculus

We study how the problem of temporal projection can be formalized in terms of argumentation. In particular, we extend earlier work of translating the language \(\mathcal{E}\) for Reasoning about Actions and Change into a Logic Programming argumentation framework, by introducing new types of arguments for (i) backward persistence and (ii) persistence from observations. The paper discusses how this extended argumentation formulation is close to the original Event Calculus proposed by Kowalski and Sergot in 1986.
Evgenios Hadjisoteriou, Antonis Kakas

Reactive Event Calculus for Monitoring Global Computing Applications

In 1986 Kowalski and Sergot proposed a logic-based formalism named Event Calculus (EC), for specifying in a declarative manner how the happening of events affects some representation (the state) of the world. Since its introduction, EC has been recognized for being an excellent framework to reason about time and events. Recently, with the advent of complex software systems decomposed into sets of autonomous, heterogeneous distributed entities, EC has drawn attention as a viable solution for monitoring them, where monitoring means to represent their state and how events dynamically affect such state.
In this work we present the fundamentals of a reactive and logic-based version of EC, named REC, for monitoring declarative properties, while maintaining a solid formal background. We present some results about its formal as well as practical aspects, and discuss how REC has been applied to a variety of application domains, namely BPM, SOC, CGs and MAS. We also highlight some key issues required by the monitoring task, and finally discuss how REC overcomes such issues.
Stefano Bragaglia, Federico Chesani, Paola Mello, Marco Montali, Paolo Torroni

Reasoning about the Intentions of Agents

In this paper we further develop the formal theory of intentions suggested by C. Baral and M. Gelfond in 2005. In this work the authors formalized the behavior of an agent intending to execute a sequence of actions. The resulting axioms for intentions written in Knowledge Representation language Answer Set Prolog allowed to easily express such properties of intentions as persistence and non-procrastination. This paper expands this work to allow reasoning with intentions in the presence of unexpected observations, and intentions to achieve goals. The theory is formulated in the extension of Answer Set Prolog, called CR-Prolog.
Justin Blount, Michael Gelfond

Symbolic Model Checking for Temporal-Epistemic Logic

We survey some of the recent work in verification via symbolic model checking of temporal-epistemic logic. Specifically, we discuss OBDD-based and SAT-based approaches for epistemic logic built on discrete and real-time branching time temporal logic. The underlying semantical model considered throughout is the one of interpreted system, suitably extended whenever necessary.
Alessio Lomuscio, Wojciech Penczek

GOAL Agents Instantiate Intention Logic

Various theories of cognitive or rational agents that use formal logic to define such agents have been proposed in the literature. Similarly, a range of more computationally oriented frameworks have been proposed for engineering rational agents. It remains interesting to explore the relation between these logical theories and existing computational agent frameworks that are used to program agents. First of all, by establishing a formal relation between agent logics and computational agent frameworks, agent logics may become a practical tool for reasoning about computational agents. Secondly, a formal relation may provide new insights into the kinds of agents that can be built using a particular computational agent framework. It may in particular highlight some of the assumptions built into logical as well as computational approaches.
In this paper, we explore the relation between Intention Logic and the agent programming language Goal. This is a natural choice because Intention Logic and Goal use the same set of basic concepts to define agents, namely declarative beliefs and goals. We discuss various assumptions and identify some subtle differences between the two systems. We show that agent programs written in Goal can be formally related to specifications written in a fragment of Intention Logic. It follows that a weakened version of Intention Logic can be used to prove properties of Goal agents. In this sense, such agents can be said to instantiate Intention Logic.
Koen V. Hindriks, Wiebe van der Hoek, John-Jules Ch. Meyer

Part III: AI and Law

Open Texture and Argumentation: What Makes an Argument Persuasive?

Although Marek Sergot’s contribution to Artificial Intelliegnce and Law is mainly associated with the formalisation of legislation as a logic program, he also wrote on an approach to the treatment of open textured concepts in law, using argumentation. That paper posed the question what makes an argument persuasive? This short paper considers the ideas of that paper and discusses developments in AI and Law over the subsequent 25 years, focusing on the progress made in answering this question in that domain.
Trevor Bench-Capon

Irrationality in Persuasive Argumentation

Much of the formal treatment of argumentation process in AI has analyzed this in terms of proof methodologies grounded in non-classical, especially non-monotonic, logics. Yet one can claim that such approaches, while sufficing to describe the fluid nature of so-called “real-world” debate, e.g. in appeal determination for legal scenarios, ignore one significant component which figures in persuasive debate, i.e. that an argument may be deemed acceptable not because of what constitutes the case put forward but rather because of how this case is advanced. In particular the perceived merits of a case may be coloured by, what are at heart irrational and emotionally driven, responses to its style and presentation rather than its content. In this overview we examine a range of contexts in which tempering emotional appeal in the presentation of an issue may influence the audience to which it is addressed and briefly consider how such situations may formally be modelled, embodied, and exploited within multiagent debates.
Paul E. Dunne

Some Reflections on Two Current Trends in Formal Argumentation

This paper discusses two recent developments in the formal study of argumentation-based inference: work on preference-based abstract argumentation and on classical (deductive) argumentation. It is first argued that general models of the use of preferences in argumentation cannot leave the structure of arguments and the nature of attack and defeat unspecified. Then it is claimed that classical argumentation cannot model some common forms of defeasible reasoning in a natural way. In both cases it will be argued that the recently proposed ASPIC  +  framework for structured argumentation does not suffer from these limitations. In the final part of the paper the work of Marek Sergot on argumentation-based inference will be discussed in light of the preceding discussion.
Henry Prakken

Part IV: Deontic Logic and Norm-Governed Systems

On the Representation of Normative Sentences in FOL

Rules, regulations and policy statements quite frequently contain nested sequences of normative modalities as in, for example:
  • The database manager is obliged to permit the deputy-manager to authorise access for senior departmental staff.
  • Parking on highways ought to be forbidden. [24]
Accordingly, a knowledge-representation language for such sentences must be able to accommodate nesting of this kind. However, if—as some have proposed—normative modalities such as obligatory, permitted, and authorised are to be interpreted as first-order predicates of named actions, then nesting appears to present a problem, since the scope formula of obligatory in “obligatory that it is permitted that a” (where a names an action) is not a name but a sentence.
The ‘disquotation’ theory presented in Kimbrough (“A Note on Interpretations for Federated Languages and the Use of Disquotation”, and elsewhere) may provide a candidate solution to this FOL problem. In this paper we rehearse parts of that theory and evaluate its efficacy for dealing with the indicated normative nesting problem.
Andrew J. I. Jones, Steven O. Kimbrough

Why Be Afraid of Identity?

Comments on Sergot and Prakken’s Views
The paper discusses the views held by Sergot and Prakken [22] on the import, or non-import, of the identity principle for conditional obligation within a preference-based semantics. This is the principle \(\bigcirc (A/A)\). The key point is to understand and appreciate what unconditional obligations the principle allows us to detach, and from what premises. It is argued that it does not license the move from A to \(\bigcirc A\), which would amount to committing a breach of Hume’s law: no ‘ought’ from ‘is’. It is also shown that the most that is licensed is the move from □A to \(\bigcirc A\) − a move that appears to be harmless, and (above all) compatible with the idea that obligations are essentially violable entities. An existing pragmatic theory can be used to explain it. Objections based on the definition of the unconditional obligation operator are countered.
Xavier Parent

Deon  + : Abduction and Constraints for Normative Reasoning

Deontic concepts and operators have been widely used in several fields where representation of norms is needed, including legal reasoning and normative multi-agent systems.
In the meantime, abductive logic programming (ALP for short) has been exploited to formalize societies of agents, commitments and institutions, taking advantage from ALP operational support as (static or dynamic) verification tool.
Nonetheless, the modal nature of deontic operators smoothly fits into abductive semantics and abductive reasoning, where hypotheses can be raised at run-time on the basis of the specified formulas.
In recent works, a mapping of the most common deontic operators (obligation, prohibition, permission) to the abductive expectations of an ALP framework for agent societies has been proposed. This mapping was supported by showing a correspondence between declarative semantics of abductive expectations and Kripke semantics for deontic operators.
Building upon such correspondence, in this work we introduce Deon  + , a language where the two basic deontic operators (namely, obligation and prohibition) are enriched with quantification over time, by means of ALP and Constraint Logic Programming (CLP for short). In this way, we can take into account different flavors for obligations and prohibitions over time, i.e., existential or universal. We also discuss how to address consistency verification of such deontic specifications by a suitable ALP proof procedure, enriched with CLP constraints.
Marco Alberti, Marco Gavanelli, Evelina Lamma

Contrary-To-Duties in Games

The aim of the paper is to bring to the realm of game theory the well-known deontic notion of contrary-to-duty (CTD) obligation, so far not investigated in relation to optimality of strategic decisions. We maintain that, under a game-theoretical semantics, CTDs are well-suited to treat sub-ideal decisions. We also argue that, in a wide class of interactions, CTDs can used as a compact representation of coalitional choices leading to the achievement of optimal outcomes. Finally we investigate the properties of the proposed operators.
Paolo Turrini, Xavier Parent, Leendert van der Torre, Silvano Colombo Tosatto

Part V: Logical Approaches to Policies and Authorization

Logical Approaches to Authorization Policies

We show how core concepts in access control can be represented in axiomatic terms and how multiple access control models and policies can be uniformly represented as particular logical theories in the axiom system that we introduce. Authorization policies are represented in our framework by using a form of answer set programming. We describe the motivations for our approach and we consider how properties of policies can be proven in our scheme.
Steve Barker

Decentralized Governance of Distributed Systems via Interaction Control

This paper introduces an abstract reference model, called interaction control (IC), for the governance of large and heterogeneous distributed systems. This model goes well beyond conventional access control, along a number of dimensions. In particular, the IC model has the following characteristics: (1) it is inherently decentralized, and thus scalable even for a wide range of stateful policies; (2) it is very general, and not biased toward any particular type of policies; thus providing a significant realization of the age-old principle of separation of policy from mechanism; and (3) it enables flexible, composition-free, interoperability between different policies.
The IC model, which is an abstraction of a mechanism called law-governed interaction (LGI), has been designed as a minimalist reference model that can be reified into a whole family of potential control mechanisms that may support different types of communication, with different performance requirements and for different application domains.
Naftaly H. Minsky

Managing User-Generated Content as a Knowledge Commons

In the era of mass-participation content creation (MPCC) through social networking and pervasive computing, a different approach to intellectual property regarding user-generated content is required. One possible approach is to consider the intellectual property rights of MPCC from the perspective of a knowledge commons. Management of knowledge as a commons can then be based on the socio-economic principles of self-governing institutions for common pool resources, and formalised as a self-organising dynamic multi-agent system. In this paper, we describe a testbed for representing MPCC as a knowledge commons, and formalise three management principles, using the Event Calculus, for regulatory compliance, conflict resolution, and collective choice arrangements. Although a preliminary description of work in progress, we believe this approach has potentially significant impact on the use of collective intelligence and knowledge sharing to address systemic problems which threaten the sustainability of institutions and physical infrastructure.
Jeremy Pitt


Weitere Informationen