Rules and Strategies for Contextual Specialization of Constraint Logic Programs

We address the problem of specializing a constraint logic program w.r.t. a constrained atom which specifies the context of use of the program. We follow an approach based on transformation rules and strategies. We introduce a novel transformation rule, called contextual constraint replacement, to be combined with variants of the traditional unfolding and folding rules. We present a general Partial Evaluation Strategy for automating the application of these rules, and two additional strategies: the Context Propagation Strategy which is instrumental for the application of our contextual constraint replacement rule, and the Invariant Promotion Strategy for taking advantage of invariance properties of the computation. We show through some examples the power of our method and we compare it with existing methods for partial deduction of constraint logic programs based on extensions of Lloyd and Shepherdson's approach.     

Practical Handling of Exception-Tainted Rules and Independence Information in Possibilistic Logic

This paper provides a survey of possibilistic logic as a simple and efficient tool for handling nonmonotonic reasoning, with some emphasis on algorithmic issues. In our previous works, two well-known nonmonotonic systems have been encoded in the possibility theory framework: the preferential inference based on System P, and the rational closure inference proposed by Lehmann and Magidor which relies on System P augmented with a rational monotony postulate. System P is known to provide reasonable but very cautious conclusions, and in particular, preferential inference is blocked by the presence of irrelevant properties. When using Lehmann's rational closure, the inference machinery, which is then more productive, may still remain too cautious, or on the contrary, provide counter -intuitive conclusions. The paper proposes an approach to overcome the cautiousness of System P and the problems encountered by the rational closure inference. This approach takes advantage of (contextual) independence assumptions of the form: the fact that is true (or is false) does not affect the validity of the rule normally if then . The modelling of such independence assumptions is discussed in the possibilistic framework. Moreover, we show that when a counter-intuitive conclusion of a set of defaults can be inferred, it is always possible to repair the set of defaults by adding suitable information so as to produce the desired conclusions and block unsuitable ones.     

Cooperation and Competition in ALIAS: A Logic Framework for Agents that Negotiate

This paper presents ALIAS, an agent architecture based on intelligent logic agents, where the main form of agent reasoning is abduction. The system is particularly suited for solving problems where knowledge is incomplete, where agents may need to make reasonable hypotheses about the problem domain and other agents, and where the raised hypotheses have to be consistent for the overall set of agents. ALIAS agents are pro-active, exhibiting a goal-directed behavior, and autonomous, since each one can solve problems using its own private knowledge base. ALIAS agents are also social, because they are able to interact with other agents, in order to cooperatively solve problems. The coordination mechanisms are modeled by means of LAILA, a logic-based language which allows to express intra-agent reasoning and inter-agent coordination. As an application, we show how LAILA can be used to implement inter-agent dialogues, e.g., for negotiation. In particular, LAILA is well-suited to coordinate the process of negotiation aimed at exchanging resources between agents, thus allowing them to execute the plans to achieve their goals.     

Web-Based Adaptive Tutoring: An Approach Based on Logic Agents and Reasoning about Actions

In this paper we describe an approach to the construction of adaptive tutoring systems, based on techniques from the research area of Reasoning about Actions and Change.This approach leads to the implementation of aprototype system, having a multi-agent architecture,whose kernel is a set of rational agents,programmed in the logic programminglanguage DyLOG. In the prototype that weimplemented the reasoning capabilities of theagents are exploited both to dynamically buildstudy plans and to verify the correctness ofuser-given study plans with respect to thecompetence that the user wants to acquire.     

Atom-Aid: Detecting and Surviving Atomicity Violations

Hardware can play a significant role in improving reliability of multithreaded software. Recent architectural proposals arbitrarily group consecutive dynamic memory operations into atomic blocks to enforce coarse-grained memory ordering, providing implicit atomicity. The authors of this article observe that implicit atomicity probabilistically hides atomicity violations by reducing the number of interleaving opportunities between memory operations. They propose Atom-Aid, which creates implicit atomic blocks intelligently instead of arbitrarily, dramatically reducing the probability that atomicity violations will manifest themselves.     

Normative autonomy and normative co-ordination: Declarative power, representation, and mandate

In this paper we provide a formal analysis of the idea of normative co-ordination. We argue that this idea is based on the assumption that agents can achieve flexible co-ordination by conferring normative positions to other agents. These positions include duties, permissions, and powers. In particular, we explain the idea of declarative power, which consists in the capacity of the power-holder of creating normative positions, involving other agents, simply by proclaiming such positions. In addition, we account also for the concepts of representation, namely the representatives capacity of acting in the name of his principal, and of mandate, which is the mandatees duty to act as the mandator has requested. Finally, we show how the framework can be applied to represent the contract-net protocol. Some brief remarks on future research and applications conclude this contribution.     

ANTS: Agents on Networks, Trees, and Subgraphs

Efficient exploration of large networks is a central issue in data mining and network maintenance applications. In most existing work there is a distinction between the active ‘searcher’ which both executes the algorithm and holds the memory and the passive ‘searched graph’ over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavily-loaded, call for a different paradigm, in which a noncentralized group of one or more lightweight autonomous agents traverse the network in a completely distributed and parallelizable way. Potential advantages of such a paradigm would be fault tolerance against network and agent failures, and reduced load on the busy nodes due to the small amount of memory and computing resources required by the agent in each node. Algorithms for network covering based on this paradigm could be used in today’s Internet as a support for data mining and network control algorithms. Recently, a vertex ant walk () method has been suggested [I.A. Wagner, M. Lindenbaum, A.M. Bruckstein, Ann. Math. Artificial Intelligence 24 (1998) 211–223] for searching an undirected, connected graph by an a(ge)nt that walks along the edges of the graph, occasionally leaving ‘pheromone’ traces at nodes, and using those traces to guide its exploration. It was shown there that the ant can cover a static graph within time nd, where n is the number of vertices and d the diameter of the graph. In this work we further investigate the performance of the method on dynamic graphs, where edges may appear or disappear during the search process. In particular we prove that (a) if a certain spanning subgraph S is stable during the period of covering, then the method is guaranteed to cover the graph within time nd_s, where d_s is the diameter of S, and (b) if a failure occurs on each edge with probability p, then the expected cover time is bounded from above by nd((logΔ/log(1/p))+((1+p)/(1−p))), where Δ is the maximum vertex degree in the graph. We also show that (c) if G is a static tree then it is covered within time 2n.     

Agents, grids, and middleware

Agents, grids, and middleware are more closely related. We develop software architecture for two software projects: one involves infrastructure for distributed, pervasive computing; the other involves partitioning huge data sets across data grids consisting of thousands of PCs. On the surface, these projects seem very different, but there are similarities and lessons we can learn from comparing them that have implications for agents, grids, Web services, pervasive computing, and middleware.     

Logic,topology, and integration

The central notion presented is that of closeness of (or difference between) two theories. In the first part, we give intuitive arguments in favor of considering topologies on the set of theories, continuous logics, and the average difference between two logics (i.e., the integral of their difference). We argue for the importance of the difference between theories in a wide range of applications and problems. In the second part, we give some basic definitions and results for one such type of topology. In particular, separation properties and compactness are discussed and examples given. The techniques employed for constructing the topology are also used for defining a -algebra of measurable sets on the set of theories, leading to the usual definition of the Lebesgue integral and a precise definition of the average difference of two logics.     

Sisl: Several Interfaces, Single Logic

Modern interactive services such as information and e-commerce services are becoming increasingly more flexible in the types of user interfaces they support. These interfaces incorporate automatic speech recognition and natural language understanding and include graphical user interfaces on the desktop and web-based interfaces using applets and HTML forms. To what extent can the user interface software be decoupled from the service logic software (the code that defines the essential function of a service)? Decoupling of user interface from service logic directly impacts the flexibility of services, or how easy they are to modify and extend. To explore these issues, we have developed Sisl, an architecture and domain-specific language for designing and implementing interactive services with multiple user interfaces. A key principle underlying Sisl is that all user interfaces to a service share the same service logic. Sisl provides a clean separation between the service logic and the software for a variety of interfaces, including Java applets, HTML pages, speech-based natural language dialogue, and telephone-based voice access. Sisl uses an event-based model of services that allows service providers to support interchangeable user interfaces (or add new ones) to a single consistent source of service logic and data. As part of a collaboration between research and development, Sisl is being used to prototype a new generation of call processing services for a Lucent Technologies switching product.     

Normative design of project-based organizations-Part III: modeling congruent, robust, and adaptive organizations

In Parts I and II of this paper, we presented a three-phase iterative optimization process to design normative organizations. Such organizations are mission-based in that they are organized to perform a given task and then are dissolved. The objectives of the present paper are to 1) define and classify the processes of strategy and structural adaptation in organizations in response to mission and environmental changes, 2) extend our three-phase design methodology to construct robust and adaptive organizations, and 3) analyze the effects of mission parameters on their performance. We investigate the performance of organizations through internal workload and external coordination measures for individual DMs, as well as workload distribution as the overall organizational measure.     

A Critical Reexamination of Default Logic, Autoepistemic Logic, and Only Knowing

Fifteen years of work on nonmonotonic logic has certainly increased our understanding of the area. However, given a problem in which nonmonotonic reasoning is called for, it is far from clear how one should go about modeling the problem using the various approaches. We explore this issue in the context on two of the best–known approaches, Reiter's default logic and Moore's autoepistemic logic, as well as two related notions of "only knowing," due to Halpern and Moses and to Levesque. In particular, we return to the original technical definitions given in these papers and examine the extent to which they capture the intuitions they were designed to capture.     

Belief, Logic, and Partial Truth

Contrary to some interpretations of "impossibility theorems," belief models exist which are both truth-functional and give equal credibility to all equivalent formulas. This combination of features can be useful, e.g., in case-based reasoning. That such models exist casts doubt on theories which try to restrict the applications of belief calculi based upon the supposed incompatibility of the features. One prominent theory attempts to divorce partial truth, described as the province of fuzzy logic, from probabilistic reasoning. Nevertheless, ordinary logic and cumulative probability exactly restate the inferences of the usual fuzzy logic.     

Introduction: Logic programming, non-monotonicreasoning and reasoning about actions

On November 5, 1995, a special symposium on logic programming, non-monotonic reasoning and reasoning about actions, in honor of the 50th birthday of Professor Michael Gelfond, was held in El Paso, Texas. It was the first symposium of the El Paso Shell Oil Symposium series, jointly sponsored by the Shell Oil Company and by the University of Texas at El Paso. Overall, 16 talks were presented by researchers from the USA (New Mexico State University, Southern Methodist University, Stanford University, Syracuse University, University of Texas at Austin, and University of Texas at El Paso), Canada, and Finland. This issue contains the (peer-refereed) proceedings of this symposium. We are happy to present this collection to our readers, and we want to thank all those without whom this publication would not be possible: Shell Oil and the University of Texas at El Paso for generous support; the authors and all the participants of the symposium for their contributions; the referees for their tireless work; Martin Golumbic, the Editor-in-Chief of the Annals of Mathematics and Artificial Intelligence, for the opportunity to publish the proceedings as an issue of this journal; and, last but not the least, Michael Gelfond for being a wonderful person, a brilliant researcher, a good friend, and an inspiring teacher. This revised version was published online in June 2006 with corrections to the Cover Date.