Abstract Modelling the interactions and reasoning processes of multiple agents in a dynamic environment presents a significant challenge, requiring tools that effectively capture diverse interaction types (such as persuasion and deliberation) while supporting agents in decision-making and consensus-building. We extend the Timed Concurrent Language For Argumentation (TCLA) to support the specification of agents equipped with local argument memories and private knowledge reasoning. This extension enables the full formalization of Symmetric Strategic Argumentation Dialogues and Multi-Agent Decision Making with Privacy Preserved problems within TCLA, for which we also introduce general translation functions to automatically obtain TCLA programs. To demonstrate practical applications of TCLA, we provide examples that model the two studied problems and make use of the translation functions.

Abstract The timed concurrent language for argumentation (tcla) is a framework to model concurrent interactions between communicating agents that reason and take decisions through argumentation processes, also taking into account the temporal duration of the performed actions. Time is a crucial factor when dealing with dynamic environments in real-world applications, where agents must act in a coordinated fashion to reach their own goals. However, modelling complex interactions and concurrent processes may be challenging without the help of proper languages and tools. In this paper, we discuss the use of tcla for practical purposes and provide a working implementation of the language, endowed with a user interface available online, that serves the dual purpose of aiding the research in this field and facilitating the development of multi-agent systems based applications.

Abstract Time is a crucial factor in modelling dynamic behaviours of intelligent agents: activities have a determined temporal duration in a real-world environment, and previous actions influence agents’ behaviour. In this paper, we propose a language for modelling concurrent interaction between agents that also allows the specification of temporal intervals in which particular actions occur. Such a language exploits a timed version of Abstract Argumentation Frameworks to realise a shared memory used by the agents to communicate and reason on the acceptability of their beliefs with respect to a given time interval. An interleaving model on a single processor is used for basic computation steps, with maximum parallelism for time elapsing. Following this approach, only one of the enabled agents is executed at each moment. To demonstrate the capabilities of the language, we also show how it can be used to model interactions such as debates and dialogue games taking place between intelligent agents. Lastly, we present an implementation of the language that can be accessed via a web interface.

In the last years almost all families of programming languages, from imperative to functional, logic, object-oriented and machine code, have been subject to static analysis by abstract interpretation. The use of a principled approach to static analysis based on the theory of abstract interpretation provided mathematical tools to reason about program properties and allowed for the rigorous and incremental design of precise and scalable static analyzers, ensuring soundness by construction. The large variety of abstract domains for many different programming languages, the ability to combine and refine them with standard abstract interpretation tools and the availability of mature abstract domain libraries allowed easily porting, reusing and experimenting with techniques born in a specific family to other programming languages and properties.

Abstract Sharing analysis is used to statically discover data structures which may overlap in object-oriented programs. Using the abstract interpretation framework, we show that sharing analysis greatly benefits from linearity information. A variable is linear in a program state when different field paths starting from it always reach different objects. We propose a graph-based abstract domain which can represent aliasing, linearity, and sharing information and define all the necessary abstract operators for the analysis of a Java-like language.

Reasoning on a complex system in the abstract interpretation theory starts with a formal description of the system behavior specified by a collecting semantics. We take the common point of view that a collecting semantics is a very precise semantics from which other abstractions may be derived. We elaborate on both the concepts of precision and derivability, and introduce a notion of adequacy which tell us when a collecting semantics is a good choice for a given family of abstractions. We instantiate this approach to the case of first-order functional programs by considering three common collecting semantics and some abstract properties of functions. We study their relative precision and give a constructive characterization of the classes of abstractions which are adequate for the collecting semantics.

We present an operational semantics for time-aware business processes, that is, processes modeling the execution of business activities, whose durations are subject to linear constraints over the integers. We assume that some of the durations are controllable, that is, they can be determined by the organization that executes the process, while others are uncontrollable, that is, they are determined by the external world. Then, we consider controllability properties, which guarantee the completion of the execution of the process, satisfying the given duration constraints, independently of the values of the uncontrollable durations. Controllability properties are encoded by quantified reachability formulas, where the reachability predicate is recursively defined by means of constrained Horn clauses (CHCs). These clauses are automatically derived from the operational semantics of the process. Finally, we present two algorithms for solving the so called weak and strong controllability problems. Our algorithms reduce these problems to the verification of a set of quantified integer constraints, which are simpler than the original quantified reachability formulas, and can effectively be handled by state-of-the-art CHC solvers.

Abstract We propose a timed and soft extension of Concurrent Constraint Programming. The time extension is based on the hypothesis ofbounded asynchrony: The computation takes a bounded period of time and is measured by a discrete global clock. Action prefixing is then considered as the syntactic marker that distinguishes a time instant from the next one. Supported by soft constraints instead of crisp ones,tellandaskagents are now equipped with a preference (or consistency) threshold, which is used to determine their success or suspension. In this paper, we provide a language to describe the agents' behavior, together with its operational and denotational semantics, for which we also prove the compositionality and correctness properties. After presenting a semantics using maximal parallelism of actions, we also describe a version for their interleaving on a single processor (with maximal parallelism for time elapsing). Coordinating agents that need to take decisions on both preference values and time events may benefit from this language.

Abstract Program transformation is an appealing technique which allows to improve run-time efficiency, space-consumption, and more generally to optimize a given program. Essentially, it consists of a sequence of syntactic program manipulations which preserves some kind of semantic equivalence. Unfolding is one of the basic operations used by most program transformation systems and consists of the replacement of a procedure call by its definition. While there is a large body of literature on the transformation and unfolding of sequential programs, very few papers have addressed this issue for concurrent languages. This paper defines an unfolding system for Constraint Handling Rules programs. We define an unfolding rule, show its correctness and discuss some conditions that can be used to delete an unfolded rule while preserving the program meaning. We also prove that, under some suitable conditions, confluence and termination are preserved by the above transformation.

Constraint Handling Rules (CHR) is a committed-choice declarative language that has been originally designed for writing constraint solvers and is nowadays a general purpose language. CHR programs consist of multiheaded guarded rules which allow to rewrite constraints into simpler ones until a solved form is reached. Many empirical evidences suggest that multiple heads augment the expressive power of the language, however no formal result in this direction has been proved, so far. In the first part of this article we analyze the Turing completeness of CHR with respect to the underlying constraint theory. We prove that if the constraint theory is powerful enough then restricting to single head rules does not affect the Turing completeness of the language. On the other hand, differently from the case of the multiheaded language, the single head CHR language is not Turing powerful when the underlying signature (for the constraint theory) does not contain function symbols. In the second part we prove that, no matter which constraint theory is considered, under some reasonable assumptions it is not possible to encode the CHR language (with multi-headed rules) into a single headed language while preserving the semantics of the programs. We also show that, under some stronger assumptions, considering an increasing number of atoms in the head of a rule augments the expressive power of the language. These results provide a formal proof for the claim that multiple heads augment the expressive power of the CHR language.

Abstract We study the decidability of termination for two CHR dialects which, similarly to the Datalog like languages, are defined by using a signature which does not allow function symbols (of arity > 0). Both languages allow the use of the = built-in in the body of rules, thus are built on a host language that supports unification. However each imposes one further restriction. The first CHR dialect allows onlyrange-restrictedrules, that is, it does not allow the use of variables in the body or in the guard of a rule if they do not appear in the head. We show that the existence of an infinite computation is decidable for this dialect. The second dialect instead limits the number of atoms in the head of rules to one. We prove that in this case, the existence of a terminating computation is decidable. These results show that both dialects are strictly less expressive1than Turing Machines. It is worth noting that the language (without function symbols) without these restrictions is as expressive as Turing Machines.

Constraint Handling Rules (CHR) is a committed-choice declarative language which has been originally designed for writing constraint solvers and which is nowadays a general purpose language.

Constraint Handling Rules (CHR) is a committed-choice declarative language which has been designed for writing constraint solvers. A CHR program consists of multiheaded guarded rules which allow to rewrite constraints into simpler ones until a solved form is reached. CHR has received considerable attention, both from the practical and from the theoretical side. Nevertheless, due the use of multiheaded clauses, there are several aspects of the CHR semantics which have not been clarified yet. In particular, no compositional semantics for CHR has been defined so far. In this article we introduce a fix-point semantics which characterizes the input/output behavior of a CHR program and which is and-compositional, that is, which allows to retrieve the semantics of a conjunctive query from the semantics of its components. Such a semantics can be used as a basis to define incremental and modular analysis and verification tools.

Program transformation is an appealing technique which allows to improve run-time efficiency, space-consumption and more generally to optimize a given program. Essentially it consists of a sequence of syntactic program manipulations which preserves some kind of semantic equivalence. One of the basic operations which is used by most program transformation systems is unfolding which consists in the replacement of a procedure call by its definition. While there is a large body of literature on transformation and unfolding of sequential programs, very few papers have addressed this issue for concurrent languages and, to the best of our knowledge, no one has considered unfolding of CHR programs.

Constraint Handling Rules (CHR) are a committed-choice declarative language which has been designed for writing constraint solvers. A CHR program consists of multi-headed guarded rules which allow one to rewrite constraints into simpler ones until a solved form is reached.CHR has received a considerable attention, both from the practical and from the theoretical side. Nevertheless, due the use of multi-headed clauses, there are several aspects of the CHR semantics which have not been clarified yet. In particular, no compositional semantics for CHR has been defined so far.In this paper we introduce a fix-point semantics which characterizes the input/output behavior of a CHR program and which is and-compositional, that is, which allows to retrieve the semantics of a conjunctive query from the semantics of its components. Such a semantics can be used as a basis to define incremental and modular analysis and verification tools.

A temporal logic is presented for reasoning about the correctness of timed concurrent constraint programs. The logic is based on modalities which allow one to specify what a process produces as a reaction to what its environment inputs. These modalities provide an assumption/commitment style of specification which allows a sound and complete compositional axiomatization of the reactive behavior of timed concurrent constraint programs.

In [5] we introduced a Timed Linda language (T-Linda) whic hwas obtained by a natural timed interpretation of the usual constructs of the Linda model and by including a simple primitive for specifying time-outs. Here we define a denotational model for T-Linda which is based on timed reactive sequences. The correctness of this model is proved w.r.t a notion of observ ables which include finite traces of actions and input/output pairs.

A temporal logic is presented for reasoning about the correctness of timed concurrent constraint programs. The logic is based on epistemic modalities which express either what a process knows at a certain time or what a process believes about the results of the other processes. In terms of these epistemic modalities of knowledge and belief a compositional axiomatization is given of the reactive behaviour of timed concurrent constraint programs.

We introduce a transformation system for concurrent constraint programming (CCP). We define suitable applicability conditions for the transformations that guarantee the input/output CCP semantics is also preserved when distinguishing deadlocked computations from successful ones and when considering intermediate results of (possibly) nonterminating computations.The system allows us to optimize CCP programs while preserving their intended meaning: In addition to the usual benefits for sequential declarative languages, the transformation of concurrent programs can also lead to the elimination of communication channels and of synchronization points, to the transformation of nondeterministic computations into deterministic ones, and to the crucial saving of computational space. Furthermore, since the transformation system preserves the deadlock behavior of programs, it can be used for proving deadlock-freeness of a given program with respect to a class of queries. To this aim, it is sometimes sufficient to apply our transformations and to specialize the resulting program with respect to the given queries in such a way that the obtained program is trivially deadlock-free.

In this paper we study some first-order formulas, called resultants, which can be used to describe in a concise way most of the relevant information associated to SLD-derivations. We first extend to resultants some classical results of logic programming theory. Then we define a fixpoint semantics for Prolog computed resultants, i.e. those formulas which are obtained by considering the leftmost selection rule. Suitable abstractions of such a semantics are then used to model call patterns and partial answers. Finally we show how these results can be generalized to a larger class of selection rules.

In this paper we define a compositional semantics for a generalized composition operator on logic programs. Static and dynamic inheritance as well as composition by union of clauses can all be obtained by specializing the general operator. The semantics is based on the notion of differential programs, logic programs annotated with declarations that establish the programs' external interfaces.