This page is provided for those who would like to print the whole newsletter at once. It contains the concatenation of all articles of the newsletter collated in one large html file. In order to print the whole newsletter just use the print function of your browser to print this page. For the sake of ecology, we also omitted the pages corresponding to the bottom menu items.

Vol 17 n. 3, August 2004

Enrico Pontelli

Dear Logic Programmers,

Welcome to the August 2004 issue of the ALP Newsletter.

Another summer is coming to a close - rather uneventful (if we ignore Greece's victory in Euro2004...), the beginning of classes of another academic year is getting closer and closer and... conference season is here! Some of the most noteworthy LP-related events will take place between now and September, including ICLP in Saint-Malo, CP in Toronto, JELIA+CLIMA in Lisbon, and PPDP+LOPSTR+SAS+PEPM in Verona. All these events have great programs and lots of interesting things to offer. Considering that each one of us will probably be able to attend only a small subset of these wonderful events, I would like to make an invitation: if you participate to any of these events, please keep a brief diary, collect some thoughts about the conference, snap a few pics... and then send them to your favourite ALP newsletter Wink. As an example, look at the nice web page about ICLP 2003 prepared by Alexei (in the Community News Section).

Personally, I am looking forward attending the 20th ICLP conference. Along with a nice selection of papers, the program includes excellent workshops, tutorials by Simari (Defeasible LP), Niemela (ASP), and Podelski (Tree Automata  in Program Analysis), a rich poster session, and the Prolog programming competition (this year organized by Tom Schrijvers and Remko Troncon).
 And if you are still in France, you can also attend another ICLP 2004...

Regarding this issue of the newsletter, along with a nice collection of articles, we propose another instance of our new column on the new logic programming language. Please, help us in making this column a regular event by sending in your contributions - your feelings about the previously appeared proposals, your own proposal, etc.

For the future issues, I would like to seek your help for another small project of mine. I believe that it is extremely important to attract new students to the field of logic programming, and support and emphasize their endeavors. Events like Summer Schools (see the report from the entertaining Compulog/ALP Summer School held in Dallas last June) and Doctoral Consortiums (the next one planned for ICLP 2005) are great steps in this direction. I would like to start another regular column in the newsletter dedicated to doctoral dissertations (and, why not, even M.S. theses) dealing with issues relevant to logic programming. So, if you are a student, ready to defend your thesis, or if you are an advisor with students in such position, then please send me

Let's make this a success!

I would like to also draw your attention on a couple of news items:

To bring this one to closure, I would like once again to welcome your comments/critics/suggestions/... on how you would like to see the ALP Newsletter evolve in the near and not-so-near future.

           ‘till the next one.


ASPARAGUS - the Dagstuhl Initiative
Christian Anger1, Torsten Schaub1, Miroslaw Truszczynski2
1Institut fur Informatik -- Universitat Potsdam
2Department of Computer Science -- University of Kentucky

Editor: Enrico Pontelli

The PDF-version of this article can be found here.

Answer-set programming (ASP) emerged in the late 90s as a new logic programming paradigm, having its roots in non-monotonic reasoning, deductive databases and logic programming with negation as failure. Since its inception, it has been regarded as the computational embodiment of non-monotonic reasoning and a primary candidate for an effective knowledge representation tool.  This view has been boosted by the emergence of highly efficient solvers for ASP, among them smodels and dlv.

In September 2002, participants of the Dagstuhl Seminar on ``Non-monotonic Reasoning, Answer Set Programming and Constraints'' agreed that in order to foster further development of ASP, it is important to establish an infrastructure for benchmarking ASP solvers. The result is the Asparagus System, maintained at the University of Potsdam.

The principal goals of this benchmarking system are to provide an infrastructure for accumulating challenging benchmarks, and to facilitate executing ASP solvers under the same conditions, guaranteeing reproducible and reliable performance results. The system is based on a two server architecture. A public server is responsible for accessing the results of the benchmarks via the Internet, for uploading new benchmarks and servers, as well as providing a growing body of interesting benchmarking problems. A second machine is used to actually run the benchmarks in a clean, undisturbed environment. Requested runs of benchmarks are automatically executed within time and memory limits.

Though the system allows for continuous benchmarking, a comprehensive competition of the latest versions of ASP solvers is scheduled for late autumn. Potential contestants are encouraged to join in this event.

More information and the Asparagus System itself can be found at
For further questions etc., please send an email to
Mailing lists for system developers and other users are also available.

Logtalk 2.18.0

Paulo Moura
Dep. De Informatica -- Universidade da Beira Interior

Logtalk is an open source object-oriented extension to the Prolog programming language. Integrating logic programming with object-oriented and event-driven programming, it is compatible with most Prolog compilers. It supports both prototypes and classes. In addition, it supports component-based programming through category-based composition.

Highlights of the latest release

Logtalk 2.18.0 features much improved performance for most Prolog compilers. This was accomplished by applying several optimizations to the runtime translation of messages and, specially, by caching method lookups. In addition, this release includes improved configuration files for both ECLiPSe and XSB.

Logtalk major features

Logtalk objects provide plain Prolog with two essential features: encapsulation and code reuse. Plus, Logtalk adds to these two basic features the following ones: reuse through inheritance and composition; separation between interface and implementation; public, protected, and private inheritance; multi-inheritance; public, protected, and private predicates; static and dynamic object predicates; parametric objects; static and dynamic objects; support for multiple object hierarchies; support for both classes and prototypes; standard Prolog syntax with the addition of a few operators and directives for a smooth learning curve; event-driven programming; automatic generation of documentation files in XML format; and a built-in debugger.

Is Logtalk compatible with my favorite Prolog compiler?

Logtalk provides configuration files for most Prolog compilers. Currently, twenty compilers are supported: ALS Prolog, Amzi! Prolog, B-Prolog, Bin Prolog, Ciao, ECLiPSe, GNU Prolog, If-Prolog, K-Prolog, LPA Mac Prolog, LPA Win Prolog, Master Prolog, Open Prolog, Prolog II+, Qu-Prolog, Quintus Prolog, SICStus Prolog, SWI-Prolog, XSB, and YAP. This broad compatibility makes Logtalk an ideal tool for writing portable applications.

Why use objects instead of modules?

Logtalk objects, as described above, support a number of features that are simply not available with Prolog module systems. These features, resulting from a reinterpretation of both fundamental and innovative object-oriented concepts in the context of logic programming, provide a proven framework for developing large Prolog applications. Powerfull support for code encapsulation and code reuse is a most for any programming language. Prolog is no exception. Another reason to prefer objects instead of modules is portability. Not all Prolog compilers support modules. In addition, there are several compatibility problems between the modules systems of the major Prolog compilers regarding basic features such as locality of operator declarations and definition of meta-predicates. Furthermore, the ISO standard specified Prolog module system is incompatible with most of Prolog module systems in use today.

Converting Prolog code which uses modules to Logtalk objects can easily be performed by replacing module directives with object directives and by replacing declarations of exported predicates with public scope predicate directives. Logtalk objects can be defined in source files as stand-alone entities (i.e not integrated in some hierarchy), compiled, and used at runtime the same way as modules. Using Logtalk objects does not necessarily imply the use of dynamic code or forgoing the guidelines we use when developing Prolog applications. Encapsulation and code reuse are orthogonal features to the dynamic aspects of objects on traditional object-oriented languages.

Why a pre-processor implementation?

Logtalk is currently implemented as a Prolog pre-processor. This translates to a two passes compilation: first, from Logtalk to Prolog and then from Prolog to whatever format your favorite Prolog compiler uses. A pre-processor implementation allows users to take advantage of special features only available on some Prolog compilers. As such, Logtalk development can be focused on object-oriented features instead of trying to be everything for everyone. Furthermore, by being open source and implemented in Prolog, users have always the option of customizing Logtalk to better fit their needs.

How about performance?

Logtalk objects can be either static or dynamic. Static objects are defined in source files which, upon compilation, are converted to static Prolog code before being further compiled by your favorite Prolog compiler. Furthermore, static Logtalk objects may contain dynamic predicates allowing locality of database changes. The Logtalk compiler ensures that your programming choices related to first-argument indexing and tail recursion are keep on compiled code. At runtime, Logtalk caching of method lookups ensures performance levels close to what can be achieved with Prolog modules and with static binding on other object-oriented languages.

What do I get with the current Logtalk release?

The current Logtalk release contains thirty three programming examples (ranging from basic object-oriented concepts to traditional Prolog and AI applications; most of them potentially useful in a classroom context), a library of useful objects, protocols (interfaces), and categories (components for building objects), syntax-coloring configuration files for common text editors (including Emacs, Vim, Kate/KWrite, SubEthaEdit, NEdit, jEdit, and others), and integration scripts for automatic loading of Logtalk with some Prolog compilers.

How to learn more about Logtalk?

For more information on Logtalk and for downloading the latest release, please visit the Logtalk web site at

Second International Compulog/ALP Summer School
Computational Logic
(A Report)
Islam Elkabani, Omar Elkhatib, Hung Le
Department of Computer Science - New Mexico State University

Editor: Enrico Pontelli

The PDF-version of this article can be found here.

The second international summer school in Constraint and Logic Programming has been held on the campus of University of Texas at Dallas, TX. The summer school is meant for students, researchers, and programmers interested in constraints, logic programming, computational logic and its applications.
The 2nd summer school on computational logic builds on the highly successful 1st summer school in (C)LP held in Las Cruces, NM, in 1999.

The lectures have been provided by internationally renowned researchers who have made significant contributions to research. The summer school was especially directed to Ph.D. students who are just about to start research.

The summer school consisted of half day tutorials on the following topics:
Several scholarships have been made  available to the participants. About 70 students attended the summer school.

The lectures on Constraint Programming and its Applications havebeen offered by Pascal van Hentenryck (Brown University).
The first lecture on Constraint Programming took place on the first day of the Summer School (June 14), from 1:00 to 3:30.

The first class focused on the more general concepts of Constraint Programming and Constraint Logic Programming. Dr. van Hentenryck provided an overview of the field of constraint programming, illustrating the main difficulties encountered when dealing with constraint resolution. Through a number of clear examples, the instructor provided an overview of key concepts, highlighting the differences between constraint programming and more traditional search---e.g., by viewing constraint programming as a combination of branch, prune, and bound.

During the first lecture, Dr. van Hentenryck described a number of algorithms for handling some of the global constraints, such as
alldifferent and card. Furthermore, he presented the discrepancy search, which is an incomplete search algorithm that performs the following:
The second lecture on Constraint Programming took place on the  second day (Jun. 15) from 9:00 to 11:30. During this lecture, Dr. van Hentenryck presented a significant number of application problems that are NP-complete, but can be effectively handled using finite domain constraint solvers. Some of the problems presented are:


The lectures on Logical Aspects of Computer Security have been offered by Dr. Ninghui Li from Purdue University.

The first lecture took place on June 16, from 4:00 to 6:30. During the first lecture, Dr. Li provided:

The second lecture took place on June 17 from 1:00 to 3:30. During this lecture, Dr. Li offered an in-depth of security analysis for
the RT0 languages. He continued by describing how Constraint Datalog can be used as a semantic foundation for trust-management languages. He concluded his presentation by discussing some open problems in the area of trust-management as well as other possible applications of logic programming in the field of access control.


The lectures on Computational Logic and the Semantic Web have been offered by Dr. Stefan Decker, from the Digital Enterprise Research Institute, Ireland.

The first lecture took place on the first day of the Summer School (June 14) from 9:00 to 11:30. During the first lecture, Dr. Decker provided an overview of what the Semantic Web is, an what are the basic motivations that brought it into existence. Dr. Decker proceeded with an analysis of the information aspects and basic components of the Semantic Web, including a nice discussion of metadata and the Resource Description Framework (RDF).

The second lecture took place on June 15, from 4:00 to 6:30. Dr. Decker  continued his overview of the Semantic Web, focusing in particular on Ontologies. Dr. Decker introduced different formalisms for dealing with ontologies, including Description Logics, the Web Ontology Language (OWL), Description Logic Programming, and F-logic. The discussion proceeded towards applications of logic programming in reasoning about ontologies and current extensions of ontology languages. The lecture closed with a brief picture of the future of the Semantic Web.


The lectures on Tabling in Logic Programming have  been offered by Dr. David S. Warren, from SUNY Stony Brook.

The first lecture took place on June 16, from 9:00 to 11:30. In this lecture, Dr. Warren introduced the problem of non-termination in traditional Prolog systems, through some fundamental examples - such as symmetric and transitive relations.
Dr. Warren continued by showing how these problems can be effectively dealt with using tabled logic programming, and its implementation in the XSB system. The discussion highlighted how tabling can eliminated redundant computation, by storing in a table goals and their previously computed answers. In particular, all programs that do not use structures have been shown to terminate under tabled evaluation.

The second lecture on tabling took place on June 17th, from 4:00 to 6:30. In this lecture, Dr. Warren discussed the following topics:


The lectures on Answer Set Programming have been offered by Dr. Chitta Baral, from Arizona State University.

In the first lecture, Dr. Baral presented the foundations of Knowledge Representation and Reasoning (KRR), and he offered a perspective of how Answer Set Programming - and more specifically its instantiation in the AnsProlog system - can provide a very
effective solution to the key problems of KRR. In his lecture, Dr. Baral presented terminologies, syntax and semantics of AnsProlog. A rich collection of examples have been discussed to introduce AnsProlog, along with a discussion of basic techniques for declarative problem solving using AnsProlog.

During the second lecture, Dr. Baral concentrated on one of the main application of AnsProlog: reasoning about action and planning  Starting from a simple example and its solutions, Dr. Baral led the students to different and more complex problems and how they could be solved effectively using AnsProlog. In the last part, he provided an overview of the current implementations of  systems that can be used to compute answer sets - such as Smodels, DLV, and ASSAT. Dr. Baral closed the lecture with a discussion of the complexity and expressiveness of the AnsProlog* subclass.


The lectures on Inductive Logic Programming have been offered by Dr. Vitor Santos Costa, from the Federal University of Rio de Janeiro (currently at the University of Wisconsin).

During the first lecture, Dr. Santos Costa gave an overview of the different fields of machine learning and concentrated on Inductive Logic Programming. The presentation of the basic techniques in Inductive Logic Programming developed around the use of the Aleph system and its application to solve Michalski's train problem.
Dr. Santos Costa showed how the system can be used to tackle this example, and some specific techniques that have been applied in the implementation of Aleph. The discussion continued with a description of the structure of the search space in inductive logic programming and how its efficient exploration is tackled in the existing systems.
The lecture closed with the analysis of the issues of correctness and with the presentation of another system, FOIL, to discuss other inductive logic programming techniques.

During the second lecture, Dr. Santos Costa started with the principles of Inductive Logic Programming. The techniques introduced in the first lecture have been revisited in detail and in the context of both top-down and bottom-up approaches. Dr. Santos Costa introduced the principles of least generalization and refinement, and their use in some popular systems (e.g., GOLEM).
Dr. Santos Costa closed his presentation with some examples of applications of inductive logic programming,  and with an overview  of the main current research efforts in this field.

What Is TAG? - Part II
Michael Gelfond and Vladimir Lifschitz
Texas Tech University and University of Texas at Austin

Area Editor: Son Cao Tran

The PDF-version of this article can be found here.

Knowledge Representation Group at TTU

The Knowledge Representation Group at Texas Tech University (Lubbock, Texas) was created in the year 2000 and initially consisted of two faculty members, Michael Gelfond and Richard Watson, two graduate students Marcello Balduccini and Veena Mellarkod who moved to TTU from El Paso, and two other students Monica Nogueira and Mary Lynn Heidt, who stayed in El Paso. Monica and Mary successfully graduated, and later we were joined by six new student members including two PhD students. Our work is centered around two research themes:

  1. Declarative Languages for Knowledge Representation.
  2. Design and Implementation of Intelligent Agents.

Declarative Languages for Knowledge Representation

The work on declarative languages can be divided into two parts -- extensions of Answer Set Prolog and extensions of action languages. The former includes

(a) ASET -- the language which allows use of sets and aggregates in the body of a rule as well as expressions of the form ``Let p be a subset of {X:q(X)}'' in a rule head. The latter is similar but not equivalent to the choice rule of Smodels.

(b) CR-Prolog -- the language that extends ASET by allowing consistency restoring rules of the form

\begin{displaymath}head \stackrel{\,\,+}{\leftarrow}body\end{displaymath}

The rule says that the reasoner who believes the body of the rule is allowed to believe in its head if no consistent beliefs satisfying regular rules of the program are possible otherwise. The semantics of CR-Prolog can be illustrated by the following example. Consider rules

1. $p \leftarrow \; {not} \;q$
2. $q \stackrel{\,\,+}{\leftarrow}$.
3. $\neg p$.

The programs consisting of rules (1) and (1,2) have the same answer set, {p}, while the program consisting of rules (1,2,3) has the answer set $\{q,\neg p\}$. The language, expanded by a notion of "binding" preference between consistency restoring rules, allows to nicely combine deductive and abductive reasoning.

(c) P-log -- an extension of Answer Set Prolog which allows one to combine probabilistic and logical reasoning. The language, inspired by Judea Pearl's work on causality, allows one to accurately formalize subtle probabilistic and causal arguments.

The latter includes development of action languages for non-markovian domains, domains with continuous processes, non-deterministic actions, etc.

Currently we are working on the methodology of using these languages for knowledge representation, development and implementation of the corresponding reasoning algorithms, and investigation of the relationship between these and other similar extensions of Answer Set Prolog.

Design and Implementation of Intelligent Agents

In our work on design and implementation of software components of intelligent agents we concentrate on the use of answer set programming for solving sophisticated intelligent tasks such as diagnostics and testing, planning, learning, answering complex queries about the domain, etc. To test our knowledge representation methodology and reasoning methods on medium size industrial applications we developed USA Advisor -- a decision support system for the Space Shuttle flight controllers. The system consists of a knowledge base which contains a substantial amount of knowledge about the shuttle, and a planning module which uses this knowledge to find plans to perform a number of the shuttle maneuvers in the presence of multiple equipment failures. The system was originally written in A-Prolog and is now owned and maintained by the United Space Alliance -- a company responsible for day to day operations of the shuttle. The system's planning module was later expanded by some useful consistency restoring rules. This new information used by the CR-Prolog inference engine, allowed the system to first return plans of the higher quality. By replacing the planning module by a new diagnostic module we were able to find possible explanations of various unexpected events.

Our future plans include the search for a simple and mathematically precise architecture of an agent capable of combining these and other reasoning tasks with constant monitoring of an environment and a built-in reactive behavior. We also plan to better understand properties of P-log, learn to perform counterfactual reasoning, and investigate how our reasoning methods can be integrated with natural language processing.

More information about the Lubbock group can be found at its web page:


Fariba Sadri1 and Francesca Toni1,2
1Department of Computing, Imperial College, London
2Dipartimento di Informatica, Universita' di Pisa, Italy

This paper is also available in PS format for easier printing. Click here to download the PS version.


In this article we describe the SOCS project. SOCS is concerned with a computational logic model for the description, analysis and verification of global and open SOcieties of heterogeneous ComputeeS, where computees are computational entities, that is agents realised in computational logic. SOCS is funded by the European Commission under the Fifth Framework, Future and Emerging Technologies programme, within the Global Computing proactive initiative. The SOCS consortium is composed of six European partners, based in Italy, UK, and Cyprus. These are, respectively, the universities of Pisa, Bologna and Ferrara (Italy), Imperial College and City University (UK), and Cyprus University. The project is coordinated by Imperial College.
The project started in January 2002 and will finish in June 2005. Its aims are

Details of the project can be found at the project web-site:

The project aims at using Logic Programming (LP) techniques, such as Abductive Logic Programming (ALP), Constraint Logic Programming (CLP) and Logic Programming with Priorities (LPP), all appropriately extended and integrated to deal with agent problems and Global Computing challenges. We are now into the third year of the project and we have so far developed an agent model and a society model, both with computational counterparts, together with prototype implementations of both. In the final phase of the project we are currently working on formal specification and verification of properties of the models and experimentation with the prototypes.

Article overview. The remainder of this article is structured as follows. Sections 2 and 3 provide an overview of the models developed for individual computees and for societies of computees, respectively. Section 4 summarises the prototype implementations, and Section 5 concludes.


Here we briefly summarise a new model of agency called the KGP (Knowledge, Goals, Plan) model for computees. Additional details can be found in [13, 7].

This model relies upon:
The model is defined in a modular and hierarchical fashion.

Internal state. This is a tuple < KB, Goals, Plan >, where:
Syntactically, KBplan, KBreact and KBTR are abductive logic programs with constraints, KBpre is a logic program, KBGD is a logic program with priorities, and KB0 is a set of facts in logic programming, and it is (implicitly) included in all the other modules.
Goals and actions are uniquely identified by their associated time, which is implicitly existentially quantified within the whole state.
To aid revision and partial planning, Goals and Plan form a tree. The tree is given implicitly by associating with each goal and action its parent, and is augmented or revised by calls to the Goal Decision, Planning and Reactivity capabilities. Top-level goals and actions are children of the root of the tree, which, by convention, is the special symbol  $\bot$ .

Reasoning capabilities. These are:
Sensing capability. In addition to the reasoning capabilities above, the computee is equipped with a Sensing capability which links it to its environment, by allowing it to observe that properties (fluents) hold or do not hold, and that other agents have executed actions.

Transitions. The state of a computee evolves by applying transition rules, which employ capabilities and the constraint satisfaction $\models_{\cal R}$ . The transitions are:
Cycle. The behaviour of a computee is given by the application of transitions in sequences, repeatedly changing the state of the computee. These sequences are not determined by fixed cycles of behaviour, as in conventional agent architectures, but rather by reasoning with cycle theories. These are logic programs with priorities, defining preference policies over the order of application of transitions, which may depend on the environment and the internal state of a computee. This provision of a declarative control for computees in the form of cycle theories is a highly novel feature of the model, which could, in principle, be imported into other agent systems.

Computational model. The computational counterpart of the KGP model is based upon
The computational KGP model exploits the modularity of the declarative KGP model, and is proven correct with respect to it.


The SOCS social model has been conceived in the vision of open and changing environments, populated by computees or more generally by agents whose architecture may not be known a priori. Such agents will form, through interaction, an open society whose evolution is non-deterministic. While preserving the autonomy and heterogeneity of its members, the SOCS social model specifies a social knowledge which interprets and gives a social meaning to the members’ social behaviour. It supports the notion of social goal, allowing for both goal-directed and non-goal-directed societies.

For this purpose, the technologies developed so far in the area of Computational Logic provided a solid ground to build upon, starting from the specification of a declarative and an operational semantics for interactions. The advantages of such an approach are to be found in the declarative nature of the formalism used to specify societies of computees, and in the presence of an operational model, which seamlessly links specifications to implementation, and therefore verification of interaction. Using the SOCS social framework it becomes possible to verify the system based on the agents’ observable behaviour, and to detect, on the fly, the behaviour that is undesirable because it does not abide by the social protocols or semantics, or because it violates some properties (this kind of verification goes under the name of conformance check). Another noteworthy advantage is the possibility to put specifications and properties at the same level, and therefore to (formally) prove properties of protocols and societies.

The SOCS social model defines the semantics of agent interaction through logic-based integrity constraints over social events, called Social Integrity Constraints (ICS) [4]. The ideal “correct” behaviour of a society is modelled as expectations about events. ICS define the expectations stemming from a certain history of events and possibly a set of goals. Expectations and ICS are the formalisms used to define the “social semantics” of agent communication languages and interaction protocol: a semantics which is verifiable without the need for any knowledge about the agents’ internals.

The syntax of ICS and of the society in general are those of a suitably extended logic programs. The “social knowledge” is assimilated as abductive logic programs, “expected social events” are expressed as abducible predicates, and ICS are used to constrain the “socially admissible” communication patterns of computees (i.e., those which match the expectations). The society infrastructure is devoted to checking the compliance of the society members’ behaviour, with respect to its expectations.

The compliance check is based on a proof-procedure called SCIFF: an extension of Fung and Kowalski’s IFF abductive logic programming proof-procedure [10]. SCIFFprovides (with respect to the IFF) a richer syntax of abductive theories (programs and integrity constraints), caters for interactive event assimilation, supports fulfillment check and violation detection, and embodies CLP-like constraints in the ICS. SCIFF has been proven sound with respect to the declarative semantics of the society model, in its ALP interpretation. SCIFF differs from CIFF, used for the ALP components of the KGP model for individual computees (see section 2), in a number of ways, and in particular as far as its treatment of variables and the dynamic evolution of knowledge.

SCIFF has been implemented and integrated into a Java-Prolog-CHR based tool, named SOCS-SI (SOCS Social Infrastructure [3]). This implementation can be used to verify that agents comply with a Social Integrity Constraints-based specification. The intended use of SOCS-SI is in combination with agent platforms, such as PROSOCS [18], described below. In SOCS-SI, SCIFF is part of an integrated environment, endowed with interface modules to allow for such an integration, and with a graphical user interface to observe the actual behaviour of the society members with respect to their expected behaviour, and to detect possible deviations.

The main innovative contribution of the SOCS social model resides in its foundational aspects and in its direct link with its implementation, SOCS-SI. The theoretical model and SOCS-SI together constitute a framework to be used by a system designer to reason about expectations, happened events, social protocols and properties in a setting where information is partial, and where events that did not happen or that simply have not been “detected” are treated as unattended expectations. This framework paves the way for a new way of conceiving agent society engineering, driven by reasoning about properties and helped by formally grounded verification tools. Violation handling and recovery and extensive testing are matters of current and future work.


To realise the logical and computational aspects of the KGP model we have developed PROSOCS [17]. The conceptual organisation of PROSOCS is depicted in Figure 1. The figure shows a Computee, an agent equipped with reasoning capabilities allowing it to interact with its Environment, which is composed of all the other computees, a Social infrastructure to provide verification of compliance to social rules of the agent interaction, and a Medium to support inter-computee communication. Both individual computees and the social infrastructure are equipped with a Graphical User Interface (GUI).

PROSOCS allows us to deploy and test the functionality of KGP agents via the SOCSiC component of PROSOCS (see Figure 2). Deployment of KGP agents using SOCSiC is based on an agent template whose design [16] builds upon previous work in multi-agent systems, in particular, the head/body metaphor described by [19] and [11], and the mind/body architecture introduced by [5] and more recently used by [12].

In the mind part of a PROSOCS agent, the ALP-based components of the KGP model are implemented using CIFF [1] and the LPP-based components of the KGP model are implemented in Gorgias [2]. Overall, we have built the mind using SICStus Prolog [15] and the bidirectional Java-Prolog interface Jasper it provides. Jasper is used by the body to exchange information with the mind.

To implement the body of the agent we use Java on top of the Peer-to-Peer JXTA Project [20]. JXTA is suitable for the  low-level functionality of a PROSOCS agent, such as interaction with the environment, and is provided in the form of an API (Application Programming Interface). By importing this API when we instantiate specific PROSOCS agents, we enable such agents to discover bodies of other PROSOCS agents (using JXTA’s peer discovery protocols facilities for dynamic discovery in a global computing network) as well as to communicate with other agents (using JXTA’s facilities for message transport and structuring via a a pipe binding and resolver protocols).

conceptual organization of PROSOCS
Figure 1: The conceptual organization of PROSOCS

To facilitate experimentation with KGP agents we have built interfaces, which allow us to animate an agent’s behaviour while interacting with other agents in the context of a Global Computing application. The aspects of the agent’s behaviour that we animate, in the current state of the implementation, are: the computational trace in terms of the names of transitions being executed, the observations the agent makes and the actions it executes, the internal state of the agent in terms of its knowledge, goals and plans. More details of the implementation of the agent template can be found in [17].

SOCSiC is complemented by SOCS-SI which implements the Society Infrastructure (see Figure 3) of PROSOCS, and it is committed to the verification of compliance to protocols of the computees’ interactions.

The verification is performed by means of the SCIFF abductive proof procedure (see [6]).

As summarised in Section 3, the knowledge about the interaction protocols in the society is represented by an abductive logic program (composed of a logic program called knowledge base, a set of Social Integrity Constraints and a set of abducibles), while the knowledge about the agent interaction is represented as a history of events. Given a (partial) history of the agent interaction, SCIFF generates a set of abducibles (expectations) which represent a course of action that would satisfy the interaction protocols; checking the expectations against the events, the society module is able to determine fulfillment (the interaction protocols have been respected) or violation (the interaction protocols have not been respected).

The SCIFF proof procedure is implemented in SICStus Prolog [15]; the SOCS-SI GUI is implemented in Java.

implementation architecture
Figure 2: Implementation architecture of PROSOCS computee (SOCS-iC)


In this article we have outlined the SOCS project. The project has provided computational logic-based models for computees and their societies. Computees plan, pursue goals, make observations, adjust to changes in their environment and interact. Their societies may have their own goals, generate expectations for their member computees and monitor the behaviour of computees to verify whether or not the expectations are fulfilled. The declarative models are coupled with computational counterparts on the basis of which prototype implementations have been developed. The project has entered its final phase, working on specification and verification of formal properties and further development and experimentation with the prototype implementations.

Acknowledgements. This work was partially funded by the IST programme of the EC, FET under the IST-2001-32530 SOCS project, within the Global Computing proactive initiative. Francesca Toni was also supported by the Italian MIUR programme “Rientro dei Cervelli”. We thank Marco Alberti, Evelina Lamma, Kostas Stathis and Paolo Torroni for useful input to this article, and all remaining SOCS members for contributing to the work summarised in this article.

socs-si model
Figure 3: Overview of the society infrastructure architecture (SOCS-SI)


1. CIFF Web Site:, 2003.
2. Gorgias User Guide:, 2003.
3. M. Alberti, F. Chesani, M. Gavanelli, E. Lamma, P. Mello, and P. Torroni. Compliance verification of agent interaction: a logic-based tool. In J. M¨uller and P. Petta, editors, Proceedings of the Fourth International Symposium “From Agent Theory to Agent Implementation” (AT2AI-4 – EMCSR’2004 Session M), Vienna, Austria, Apr. 13-16 2004. to appear.
4. M. Alberti, M. Gavanelli, E. Lamma, P. Mello, and P. Torroni. Modeling interactions using Social Integrity Constraints: a resource sharing case study. In J. A. Leite, A. Omicini, L. Sterling, and P. Torroni, editors, Declarative Agent Languages and Technologies, First International Workshop, DALT 2003. Melbourne, Victoria, July 15th, 2003. Workshop Notes, pages 81–96, 2003.
5. J. Bell. A Planning Theory of Practical Rationality. In Proceedings of AAAI’95 Fall Symposium on Rational Agency, pages 1–4. AAAI Press, 1995.
6. A. Bracciali, N. Demetriou, U. Endriss, M. Gavanelli, A. C. Kakas, E. Lamma, P. Mancarella, P. Mello, P. Moraitis, F. Sadri, K. Stathis, G. Terreni, F. Toni, and P. Torroni. Computational model for computees and societies of computees. Technical report, SOCS Consortium, 2003. Deliverable D8.
7. A. Bracciali, N. Demetriou, U. Endriss, A. Kakas, W. Lu, P. Mancarella, F. Sadri, K. Stathis, G. Terreni, and F. Toni. The kgp model of agency for global computing: Computational model and prototype implementation. In Proceedings Global Computing Workshop, Rovereto, Italy, 2004. Springer Verlag. To appear.
8. U. Endriss, P. Mancarella, F. Sadri, G. Terreni, and F. Toni. The CIFF proof procedure for abductive logic programming with constraints. In Proceedings JELIA04. To appear.
9. U. Endriss, P. Mancarella, F. Sadri, G. Terreni, and F. Toni. Abductive logic programming with CIFF: implementation and applications. In Proceedings CILC2004, Convegno Italiano di Logica Computazionale, 2004.
10. T. H. Fung and R. A. Kowalski. The IFF proof procedure for abductive logic programming. Journal of Logic Programming, 33(2):151–165, Nov. 1997.
11. H. Haugeneder, D. Steiner, and F. McCabe. IMAGINE: A framework for building multi-agent systems. In S. M. Deen, editor, Proceedings of the 1994 International Working Conference on Cooperating Knowledge Based Systems (CKBS-94), pages 31–64, DAKE Centre, University of Keele, UK, 1994.
12. Z. Huang, A. Eliens, , and P. de Bra. An Architecture for Web Agents. In Proceedings of EUROMEDIA’01. SCS, 2001.
13. A. Kakas, P. Mancarella, F. Sadri, K. Stathis, and F. Toni. The KGP model of agency. In Proceedings ECAI2004, 2004. To appear.
14. A. C. Kakas and F. Toni. Computing argumentation in logic programming. Journal of Logic and Computation, 9:515–562, 1999.
15. SICStus Prolog user manual, release 3.8.4, 2000. Swedish Institute of Computer Science.
16. K. Stathis, C. Child, W. Lu, and G. K. Lekeas. Agents and Environments. Technical report, SOCS Consortium, 2002. IST32530/CITY/005/DN/I/a1.
17. K. Stathis, A. Kakas, W. Lu, N. Demetriou, U. Endriss, and A. Bracciali. PROSOCS: a platform for programming software agents in computational logic. In J. Muller and P. Petta, editors, Proceedings of From Agent Theory to Agent Implementation (AT2AI-4 – EMCSR’2004 Session M), pages 523–528, Vienna, Austria, 2004.
18. K. Stathis, A. C. Kakas, W. Lu, N. Demetriou, U. Endriss, and A. Bracciali. PROSOCS: a platform for programming software agents in computational logic. In J. M¨uller and P. Petta, editors, Proceedings of the Fourth International Symposium “From Agent Theory to Agent Implementation” (AT2AI-4 – EMCSR’2004 Session M), Vienna, Austria, Apr. 13-16 2004. to appear.
19. D. E. Steiner, H. Haugeneder, and D. Mahling. Collaboration of knowledge bases via knowledge based collaboration. In S. M. Deen, editor, CKBS-90 — Proceedings of the International Working Conference on Cooperating Knowledge Based Systems, pages 113–133. Springer Verlag, 1991.
20. B. Traversat, M. Abdelaziz, D. Doolin, M. Duigou, J. C. Hugly, and E. Pouyoul. Project JXTA-C: Enabling a web of things. In Proceedings of the 36th Hawaii International Conference on System Sciences (HICSS’03), pages 282–287. IEEE Press, 2003.

Community News

List of News:

Images from ICLP'03
Communicated by Alexei Morozov

Please visit our Web Site devoted to the International Conference on Logic Programming (Mumbai, India, 2003):

European Master on Language and Communication Technologies
Communicated by Enrico Franconi

The Faculty of Computer Science at the Free University of Bozen-Bolzano, Italy, and the Department of Computational Linguistics  and Phonetics (CoLi) of Saarland University, Germany, offer a distributed European Master in Language and Communication Technologies, as part of their individual Master of Science Programmes in Computer Science (Laurea Specialistica in Informatica) and Language Science and Technology (M.Sc.), respectively. Students of the European Master enroll in one of the two universities and are required to spend at least one semester at the other university; both universities adopt the ECTS credit system. In the context of the European Master Programme the Free University of Bozen-Bolzano co-operates with  ITC-irst of Trento, while the Saarland University cooperates with the German Centre for Artificial Intelligence (DFKI); these centres are connected by more than 10 years of close partnership.

Human communication is at the heart of the information society and, in a richly multilingual area such as the European Union, full participation requires multilingual facilities for creating, exchanging and accessing information across language borders, throughout Europe and beyond. During the last few years, Language and Communication Technologies have seen a rapid increase in development at both research and industrial levels due to the fast growth of the Internet, of speech-based technologies, and the success of mobile communication. This has caused an acute need for continuous
advancements in multilingual human language processing, cross-lingual information access, and multimodal human computer interaction. New expertise, skills and professional profiles are needed which can answer the growing requirements of our societies in the Human Language and Communication Technologies area.

The study programme at the Free University of Bozen-Bolzano

The European Master in Language and Communication Technologies is designed to meet the demands of industry and research in this rapidly growing area. It offers advanced courses taught by leading scientists in topical areas such as Computational Linguistics, Speech Processing, Information Retrieval, and Intelligent Interfaces. The programme is part of the Master in Computer Science (Laurea Specialistica in Informatica) and it has various strengths that make it unique amongst Italian universities:
The application deadline at the Free University of Bozen-Bolzano to the European Master in Language and Communication Technologies is the
** 27 August 2004 **.
Details can be found at

The study programme at the Saarland University

Beginning in October 2004, CoLi at the Saarland University offers a new international Masters programme in Language Science and Technology, completely taught in English, leading to the degree Master of Science (M.Sc.) in 18 months. Saarbruecken is one of the world's leading centres for language science and technology with faculty and students coming from many countries. An active program of basic, applied and cognitive research combines with state-of-the-art facilities to provide students with a rich and stimulating environment for their research. The programme cooperates closely with various departments and facilities of related disciplines, where lectures and classes are open to our graduate students. The course of studies can be personalised by setting an individual research focus. In addition to the general degree Master of Science in Language Science and  Technology, students have the option of specialising in the following areas: Computational Linguistics, Computational Psycholinguistics, Language Technology, and Phonetics and Speech Technology. Technical support facilities available to students in the programme include:
Applications at the Saarland University to the European Master in Language and Communication Technologies will be accepted starting from
the academic year 2005-2006.
Details can be found at

Free University of Bozen-Bolzano

The Free University of Bozen-Bolzano, founded in 1997, boasts modern premises in the centre of Bozen-Bolzano.  The environment is  multilingual, South Tyrol being a region where three languages are spoken: German, Italian and Ladin.  Studying in a multilingual area has shown that our students acquire the cutting edge needed in the international business world.  Many of our teaching staff hails from abroad.  Normal lectures are complemented with seminars, work placements and laboratory work, which give our students a vocational as well as theoretical training, preparing them for their subsequent professional careers.  Studying at the Free University of Bozen-Bolzano means, first and foremost, being guided all the way through the student's educational career.  South Tyrol, due to its enviable geographical position in the centre of the Dolomites, also offers our students a multitude of opportunities for spending their free-time.


The Centre for Scientific and Technological Research (ITC-irst, ) is a public research centre of the Autonomous Province of Trento, Italy.  Founded in 1976, it conducts research in the areas of Information Technologies, Microsystems, and Material Sciences. ITC-irst is one of most active and internationally renown research centres for Human Language and Communication Technologies, with more than 80 people working in this area.  The extensive lab facilities and a strong commitment to higher education render ITC-irst a dynamic research institute with all the relevant
resources to foster creativity and innovation.

New Journal: Logical Methods in Computer Science
Communicated by Jiri Adamek, Gordon D. Plotkin, Dana S. Scott, Moshe Y. Vardi

Dear Colleague:

We are writing to inform you about a new open-access, online, refereed journal: "Logical Methods in Computer Science". As an open-access publication, the journal will be freely available on the web. This new journal will be devoted to all theoretical and practical topics in computer science related to logic in a broad sense. You can find the homepage at

The journal will open to submissions on September 1, 2004.

It will be published under the auspices of The International Federation for Computational Logic:
The journal will technically be published as an overlay of the Computing Research Repository (CoRR), see

On the homepage you find a flier and a leaflet containing the basic information about the new journal. We would appreciate your posting and distributing the information, and encouraging potential authors to submit to Logical Methods in Computer Science.

You may have heard about the various developments in the past couple of years in regard to the Open Access movement, see, e.g.,:

and the link


at the jornal website. The open-access idea is that knowledge, including scientific knowledge, should be widely and readily available to society, in a stable and long-term form. The Internet and electronic publishing provides an evident means to that end. Not unrelated are concerns arising from the increasingly high prices charged commercially.

There are already a few open-access journals in Computer Science, e.g.: and

We are convinced that now is the time to start one in our area of logic and computer science.

International Master in Computational Logic
Communicated by Luis Moniz Pereira

This M.Sc. in Computational Logic is an International Master of Science Program.
It can be followed totally at Lisbon, or the student can obtain a double degree, in a
joint-cooperation between
Universidade Nova de Lisboa
, Portugal
Technische Universität, Dresden, Germany

Prospective students can apply at
or at
UNL:   Post-Graduate Secretariat

Computer Science students at DI/FCT/UNL can conclude this degree in 3+2,5 years, by way of course equivalences.

European Master in Computational Logic
The M.Sc. double degree is already being extended to other universities, namely U.P. Madrid, T.U. Vienna, F.U. Bolzano, with the same format, starting also in the Fall 2004.
An Erasmus Mundus application has been made, so that a European degree is awarded.
Scholarships will be available for certain types of student, from European (Alban, Erasmus Mundus) and from national agencies.
UNL Coordination: Professor Luís Moniz Pereira

For more information, please visit:

10th Prolog Programming Contest
Communicated by Tom Schrijvers and Remko Troncon

This year's Prolog Programming Contest will be organised at the occasion of the 20th International Conference on Logic Programming, ICLP 2004, in Saint-Malo, France.

The contest will be held on site in Saint-Malo on Tuesday 7, September 2004. Participating teams may consist of up to 3 people who share a single laptop they provide. The following major open source Prolog systems (in alphabetical ordering) are allowed: Ciao, GNU-Prolog, SWI-Prolog, Yap, XSB.

At the same time, a webcontest will be organised open to all.

More information on both events will follow. You can consult The Prolog Programming Contest website:

for all the current information of this year's contest as well as links to information on past contests (questions and winners).

Net Talk
edited by Roberto Bagnara

Being Or Not (Any Longer) Being Open-Source
From: Neng-Fa Zhou

This year marks the 10th anniversary of B-Prolog. The first version of
B-Prolog was released in Spring 1994. After more than 15 years' dedicated
efforts by the developers and after 10 years' warm embrace by the community,
B-Prolog has grown into a stable, efficient, versatile, and popular Constraint Logic Programming system.

B-Prolog is an efficient implementation of standard Prolog and several
useful extensions including [...]


B-Prolog is available for free of charge to individuals and institutions for
non-profit uses. B-Prolog is an open-source product with free upgrades to site licensees.


From: Andrzej Lewandowski
Subject: Re: The 10th Anniversary of B-Prolog

B-Prolog is not an open source Prolog according to commonly accepted definition of "open source". Source code is available only with paid site license.

Or, I don't undserstand the term "open source"...

From: Bart Demoen
Subject: Re: The 10th Anniversary of B-Prolog

Andrzej Lewandowski wrote:
> Or, I don't undserstand the term "open source"...

I think you do.
I lost interest in B-Prolog the day I (and others) had to pay for sources. Same for BinProlog.
It's such a shame - those systems that move from academic to commercial.

From: Andrzej Lewandowski
Subject: Re: The 10th Anniversary of B-Prolog

As gcc and other open source products show, their "open sourceness" is not in conflict with commercial success. I am using Prolog in commercial environment where we have nothing against using open source products, but we always purchase maintenance contracts and commercial licenses.

I was considering using B-Prolog, but despite positive technical evaluations it was rejected for business reasons. It would be unwise for us to use a product developed by single-person academic spinoff as a foundation of costly project. Situation would be different with open source product with solid maintenance and support. The likelihood that open source product gets extinct is substantially less than for product developed by in-my-basement company.

Pity that authors  of academic-gets-commercial stuff don't recognize open source movement as an opportunity....

From: Joachim Schimpf
Subject: Re: The 10th Anniversary of B-Prolog
Andrzej Lewandowski wrote:
> Pity that authors  of academic-gets-commercial stuff don't recognize
> open source movement as an opportunity....

It's not necessarily the authors, but the world they live in...

From: Andrzej Lewandowski
Subject: Re: The 10th Anniversary of B-Prolog

Not sure. Blaming "the world" for someone's failure is very convenient point of view....

Read my coments: I am not against buying commercial license and maintenance for open source produt. But I will NEVER buy anything from in-my-basement, academic-gets-commercial enterprise. This is called "business security".

Therefore, my comment was not about ECLIPSE, SICStus, Mozart-OZ, SWI, IF, Gnu Prolog, CIAO, YAP and such...

From: Oskar Bartenstein
Subject: Re: The 10th Anniversary of B-Prolog
Bart Demoen wrote:
> It's such a shame - those systems that move from academic to commercial.

Interesting opinion.
Can you (or anybody else) explain what is so bad about this pattern?

After all, some universities promote commercialization of their research results, and some people measure success in money.

From: Bart Demoen
Subject: Re: The 10th Anniversary of B-Prolog

OOskar Bartenstein wrote:
> Interesting opinion.
> Can you (or anybody else) explain what is so bad about this pattern?

You forgot an important part of what I wrote:

 >> I lost interest in [...] the day I (and others) had to pay for
 >> sources.

It's about systems that used to be free as a subject for research (which means to me "sources"), and now money is involved; or worse: one can't get the sources at all (unless by joining the company).
I don't mind people moving from academic to commercial, I don't even mind commercial people making a living thanks to academics; what I don't like is commercial people hiding things from, or putting up barriers for academics. Especially when the bariers weren't there before.
But it is a free world.

Back to top

Cross-Compiler development (MasterProlog/SWI/SICStus)
From: Christoph Quix
We have a rather complex project consisting of >100k lines of Prolog and C/C++ code. So far, we have used MasterProlog (formerly BimProlog), but it seems that the product is almost dead (correct me if I am wrong). Therefore, we are looking for a new Prolog compiler, so far I have considered, SWI and SICStus (because of local availability, but I am open for any other recommendation).

The main problem is the porting of the existing MasterProlog code to the other compilers. Unfortunately, much of the code uses some special extensions of MasterProlog (e.g. the external language interface and builtin predicates).

Are there any tools to convert source code automatically (e.g. replacing specific predicates)?

And for the future, what is the best way to maintain a project that should be portable between different Prolog compilers? I am thinking of something like a preprocessor for Prolog (enabling #ifdef and similar things in Prolog).

From: Jan Vielemaker
Subject: Re: Cross-Compiler development (MasterProlog/SWI/SICStus)


Christoph Quix wrote:
> And for the future, what is the best way to maintain
> a project that should be portable between different
> Prolog compilers? I am thinking of something like
> a preprocessor for Prolog (enabling #ifdef and similar
> things in Prolog).

Its a difficult issue. For nice and clean Prolog code, stick with ISO builtins and you should be fairly portable. You want modules (I guess). SICStus, CIAO, SWI and YAP (also GNU?) are very similar.  Libraries is a big issue.  All systems have different libraries containing different predicates.  Term-expansion and/or goal expansion are an option.  So is using an external preprocessor such as cpp, thouch cpp can easily be fooled by Prolog syntax (think of 0'a) and it doesn't make the development cycle easier (SWI-Prolog has an option to define an external preprocessor, though it is used very rarely).

From: Paulo Moura
Subject: Re: Cross-Compiler development (MasterProlog/SWI/SICStus)

GNU Prolog does not have a module system. The same goes for a number of Prolog compilers. Some potential portability pitfalls when using current module systems are meta-predicates and operators. The module systems of Quintus/SICStus use a meta_predicate directive for declaring meta-predicates. SWI-Prolog uses a module_transparent directive. At least one of the module systems for the Prolog compilers cited above does not support local operators inside modules (operators declared within modules have global scope). There is no formal (or semi-formal) specification (to the best of my knowledge; please correct me if I'm wrong) for the module system used by the Prolog compilers cited above. The Part II of the ISO Prolog standard specifies a module system which is incompatible with most module systems in use today (which, btw, pre-dates the ISO standard!!!). One of the highlights of the ISO standard is to leave to the Prolog implementer a choice between two incompatible ways of dealing with meta-predicates. I'm belief there might be valid reasons to use (today) module systems within the context of a specific Prolog compiler. Portability between a wide range of Prolog compilers is certainly not one of them.

Views on the History of Prolog Standardization
From: Bart Demoen

Flapper Billwrote:
>   Was the question of domain definitions and predicate declarations and
> io-modes debated during the drafting of the ISO definition of Prolog?
> Where is the record those debates? If these questions were addressed,
> why did the ISO decide not to include domain definitions and predicate
> declarations and io-modes in their definition of Prolog? If these
> question were not addressed, why were they not addressed, who decided
> they were not to be addressed, and where did they get the right to make
> that decision?

I think that the starting date of the ISO standardisation process for Prolog was in 1984. Roger Scowen, working for NLP in England (NLP is in the standardisation business), was looking for something to standardize. He found Prolog (he didn't >know< Prolog) and started off in England first, and with a strong kernel of DEC-10 Prolog raised academics, some of which had gone into industry by that time.

The first principle (often violated later) was that one wanted to standardize "current practice" (a term inviting to debate and often debated) and take DEC-10 Prolog as a basis.

Here are some Prolog systems similar to DEC-10 Prolog at that time:

         a Prolog by Siemens (now IF-Prolog I think)

Their intersection covers the Clocksin-Mellish book and is large enough to form the basis for a standard. The user base of these systems was considered large enough to justify the basic choice.
The main differences between these systems were in error handling, IO, modules and arithmetic. Some of these systems had industrial support, or to put it differently: companies had stakes in a standard that deviated as little as possible from their own system.

There were other systems around:

- PDC-Prolog was one of them (maybe I should say Turbo-Prolog): the company hosted a meeting of the ISO committee in Copenhagen, and they had a representative in the committee as well; he was arguing for inclusion in the standard of things like declarations and a separate string data type - which no DEC-10 like Prolog had (I think also the french were fond of that, but I am not sure - might have been another country).  The mode declarations in DEC-10 Prolog itself, were used for unsafe(!)  optimization: not checked at compile-time, neither at run-time - BIM-Prolog did run-time checks at the places of optimization - SICStus/Quintus ignored them (still does).

- another "different" system was Prolog I, Prolog II, Prolog III now Prolog IV - Marseille - with constraints that no DEC-10 Prolog system had at that time.

[there might have been more systems which differed from DEC-10, but I do not remember they had an impact on ISO]

One more principle (later often violated) was that the standardization should not design a new language or features no system currently implemented. Introducing declarations was seen as designing a new language: ISO could not just standardize on the PDC-Prolog declarations, because there was no agreement on how types/modes should be integrated (both semantics and syntax) in a logic programming language. And of course it would have been the introduction of something rather alien in DEC-10 Prolog alikes.

There is much more to be said about the history of ISO Prolog, but who cares now ?

There were so many questions from flapper. I am not sure I have addressed them. To be explicit: PDC-Prolog was involved in the ISO process - not that they got what they wanted, but declarations were considered, and not included.

To the question

> where did they get the right to make
> that decision?

I have only cynical answers :-(

The right to make an ISO decision comes from a mandate given by ISO, and the national standardisation organisations (ANSI in the USA, BIN/IBN in Belgium ...). In the end (and at intermediate stages) there is some voting going on of all the ISO member countries (this includes a lot of countries who had no representative in the ISO working group of course).

Another thing that "gives the right" to make decisions is (very unsurprisingly) brute force and power: for instance, several times in the course of the standardisation process, there was the explicit threat (from the American delegation) that ANSI (say Quintus Prolog) would just make its own standard if ISO didn't accept a particular proposal. This is all the more sad, because Quintus is not exactly alive and kicking right now. Some representatives of European countries/companies would blindly accept almost anything that was proposed by Quintus - very sad indeed.

Independent of ISO Prolog ...
From the beginning, there was the perception that Prolog is an untyped and unmoded language - no declarations. It was defined that way (or so I believe - maybe I am wrong) by its inventors.

Of course, one can see similarities between variants of Prolog and still name them Prolog. I can see a similarity between Mercury and Prolog, but I would not name Mercury a Prolog system. I think that the inventors of Mercury agree.
There is much more similarity (I think) between XSB and Prolog, than between PDC-Prolog and Prolog, but the inventors of XSB have not included Prolog in the name of their system - on purpose ! The CIAO Prolog system mentions Prolog in its name, but (I would say) it is further away from Prolog than XSB: at least, when you start XSB, you get by default a whole bunch of Clocksin-Mellish stuff, while for CIAO Prolog, it is an option (I am sure you can get that option installed as the default, but that's somehow besides the point for me).

Historically the definition of Prolog has shifted from how Marseille people invented it (syntax for instance), to what Edingburgh people made it into (synyax, builtins, semantics of common builtins ...). One might say that is injust and it is, but Marseille people do no longer complain loudly. Then again, I know people who insist on naming Wroclaw Breslau ...

Some of what I wrote (not just in this mail) might give the impression that I am against incorporating (type, mode) declarations in a logic programming language. Or that I consider the untyped Horn clause based language I name Prolog, superior to typed/moded deviations from Prolog in all aspects.

This is not true.
I have been involved in HAL - a language between Prolog and Mercury: statically typed like Mercury, more liberally moded than Mercury (at least HAL has a logic variable :-)
I defend type/mode declarations for the Next Logic Programming Language (that's a project backed up by the Association of Logic Programming).

But that does not mean I want to change my definition of what Prolog is. And it does not mean that I necessarily think that teaching Prolog by using Prolog from the start is wrong: the characteristics of Prolog open the eyes of many students and helps them form their own opinion about programming and what programming should be. I also think there is more about programming than constructing large pieces of reliable and production-quality software. Programming (and programming languages) is also about exploring ideas, rapid prototyping, execute-once code, and a vehicle to a way of thinking.

The ISO Prolog working group is very close to being dissolved or suspended or whatever the technical term is. If enough people (backed by their national bodies) feel that there should be a renewed ISO Prolog effort, they should contact Jonathan Hodgson ( who is currently the official convenor of WG17...
But I bet that there is no way a new ISO Prolog includes mandatory types/modes etc. declarations.

However, if you are willing to name that language differently (i.e. also start a new working group, making it independent of ISO Prolog), there is a chance that you end up with a language closer to PDC-Prolog. But remember: it does not take >users< to make an ISO standard, it takes national bodies and their representatives, and lots of ... patience.


The Sad Truth
From: Torkel Franzen

Jan Wielemaker wrote:
> This newsgroup is about Prolog.  Its purpose is to exchange experiences
> on this computer language.

That is only part of the purpose of the group. Among its other purposes are to vent irritation about this or that, to make snide remarks about people, to try to sell things, to babble aimlessly.

Papers to appear in TPLP and TOCL

Contents Back to top

Regular papers to appear in Theory and Practice of Logic Programming

SPECIAL ISSUE on Verification and Computational Logic

Back to top

ACM Transactions on Computational Logic (TOCL)
Accepted papers

The files below are the final versions of the papers submitted by the authors. The definite, published versions of the papers are available from the TOCL home page within the ACM Digital Library.

Volume 5, Number 2 (April 2004)

Volume 5, Number 3 (July 2004) (tentative)
Volume 5, Number 4 (October 2004) (tentative)

Future Issues (The order of the papers can change.)

Back to top

The Next Logic Programming Language
Communicated by E. Pontelli

We are continuing the discussion regarding the next logic programming language. As promised, I would like to keep this as a running section in each issue of the newsletter - thus I need your help!! What is your perspective on this issue? Do you support some of the comments appeared in this column? Do you despise them? Do you think that the next logic programming language should have a 'goto' statement? Please, let us know!

On the Next Logic Programming Language
Proposal Communicated by Alexei A. Morozov

I have become acquainted with the Prolog language in 1986 when I was a student of Moscow State Technical University. At that time I looked for computer science directions that could be interesting to spend next years of my life for their studying, and my intuition has suggested me that logic programming and object oriented programming are that directions. In that time my first impression from these areas was that one should rethink and remake a lot of things here. Unfortunately, this impression has not disappeared and it even became stronger during recent years. That is why I have decided to write this position paper and to draw attention of the community to some problems of logic programming development.

1. The aesthetics of Prolog

Probably you will agree with me that the basis of any serious programming language, that is a product of engineering approach, is certainly its aesthetics. For instance, anybody who has studied imperative languages will sense the difference between the aesthetics of Pascal (beautiful and restrictive), C (powerful and dangerous), Ada (a pompous military dinosaur), etc.

Well, my first impressions from Prolog (my first logic language was Micro Prolog, then Clocksin-Mellish Prolog, and then Turbo Prolog) were
evoked by the aesthetic of the language. I was a bit disappointed: it was an impression that nobody was engaged in the development of the syntax of the language. Prolog has an aesthetic of old interpreter like Basic. It seems that the reason of this is that Prolog was developed mainly by mathematicians, but not by the specialists in the programming languages development. Strange as it may seem, but now we have the same situation.
One can observe a confirmation of my words in syntax features of modern Prolog, in terminology that is used by logic programming society, in the problems that are attacked by logic programming society (some of them were successfully solved and/or refused in the imperative programming 10-20 years ago), and by current trends in development of logic languages.

Here is an example. As I am professional programmer (research gives no big money in Russia now), it is obvious for me that object-oriented programming (OOP) is a mean of thinking, rather than a set of syntax features of a language. Therefore, there is no point in discussing whether OOP should be supported by a logic programming language or not. Any modern programming language must be based on the principles of OOP, including its syntax and semantics. This means that the theory of logic programming should be developed to adopt/rethink the object and message notions to give them a strict logical semantics.
This means also that the meaning of this OOP notions will be inevitably changed, because they have no declarative semantics in the imperative programming. Thus, logic programming should make its contribution to the theory of OOP and there is no sense in extension of Prolog by mechanically mimic of the imperative languages syntax features.

I suppose that Next logic programming language is worthy to have modern object oriented syntax. And I believe that the future Prolog will have a fine, carefully designed syntax like Pascal and Java. It is clear also that there are a lot of novel ideas in computer sciences and software industry that could have an additional influence on the development of Prolog. For instance, the ideas of component oriented and visual programming could give some tips how the logic language should implement the principles of concurrency and meta programming that have already been present in logic programming for a long time, but have been implemented in such a way that they are absolutely out of modern programming technologies and are far away from the needs of real industrial programming.

2. Semantics of Prolog

The first thing in Prolog that I found striking was that the input/output is completely out from the ideology of the language. Probably, the origin of this problem is that logic programming was originated from the automatic theorem proving, where the input/output was (at that time) a useless and senseless thing. Unfortunately the problem is still present. A lot of people developed and used non-classical logics, etc. to reconcile destructive operations and declarative semantics (including the input/output that is a case of destructive operation in the outer world). However most researchers continue to hold the opinion that logically strict input/output in Prolog implies that Prolog should reason about the input/output and/or dynamic outer world, because Prolog is a means for logic inference. But this idea is a simple methodological mistake. To reason about the outer world and to live in the outer world are not the same things. Actually, logic language can operate in outer world without reasoning about it, i.e. Prolog can fulfill a logic inference (for instance, in classical first order logic) which is mathematically correct under the conditions of dynamic modification of input data during the logic inference. We have proven this point in the framework of the Actor Prolog project. The opposite statement also can be proven in the practical life: the current state of art in logic programming demonstrates that a logic language, even if it can reason about outer world with the help of non-classical logics, additional time arguments, continuators, monads, etc., it can be absolutely unsuitable for event oriented programming of, say, graphical user  interface.

Unfortunately, this theoretical problem is still ignored by many researches. I suppose, that this problem cannot be ignored any more, because practically any modern computer program operates in a dynamic environment (i.e., in conditions of permanent change and augmentation of input information) - the dynamic nature is intrinsical for any graphical user interface, distributed information system, Web resource, real-time control system, and so on. Actually, logic programming community has no other way except to find the solution of this problem (let us name it ``the dynamic environment problem'') or to recognize that the Prolog language does not correspond to the modern development of software engineering any more.

I vote for the first choice and propose to solve the problem on the basis of ideas that were developed and practically proved in the Actor Prolog project. One can find a brief introduction into the logical actors and repeated proving in the Getting Started into Actor Prolog
All the English papers that were published in the framework of the project are available on the Web Site.

I look forward to receiving your suggestions on the problems that I have touched in these notes.

Sincerely yours,

Alexei A. Morozov

Senior Researcher, Ph.D.
Institute of Radio Engineering and Electronics RAS

Accepted Conference Papers

List of Events:

Computational Logic in Multi-Agent Systems
September 29-30, 2004, Lisbon, Portugal

Multi-agent systems are communities of problem-solving entities that can perceive and act upon their environments to achieve their individual goals as well as joint goals. the work on such systems integrates many technologies and concepts in artificial intelligence and other areas of computing. for this reason, over recent years, the agent paradigm gained popularity in many sub-fields of computer science. a full spectrum of multi-agent systems applications have been and are being developed; from search engines to educational aids to electronic commerce and trade, e-procurement, recommendation systems, simulation and routing, to cite only some.

Although commonly implemented by means of imperative languages, mainly for reasons of efficiency, the agent concept has recently increased its influence in the research and development of computational logic based systems.

Computational logic provides a well-defined, general, and rigorous framework for studying syntax, semantics and procedures, for attending implementations, environments, tools, and standards, and for linking together specification and verification of properties of computational systems.

The purpose of this workshop is to discuss techniques, based on computational logic, for representing, programming and reasoning about multi-agent systems in a formal way.

European Conference on Logics in Artificial Intelligence
Lisbon, Portugal, September 27-30, 2004

The European Conference on Logics in Artificial Intelligence (or Journées Européennes sur la Logique en Intelligence Artificielle - JELIA) began back in 1988, as a workshop, in response to the need for a European forum for the discussion of emerging work in this field. The increasing interest in this forum and its overall technical quality has turned JELIA into a major biennial forum for the discussion of logic-based approaches to artificial intelligence.



Symposium on Logic-based Program Synthesis and Transformation
Verona, Italy, August 26-28, 2004

The aim of the LOPSTR  series is to stimulate and promote international research and collaboration on logic-based program development, and the workshop is open to contributions in logic-based program development in any language paradigm.

LOPSTR'04 will be held at the University of Verona co-located with SAS 2004 the International Static Analysis Symposium, PEPM 2004 - ACM SIGPLAN 2004 Workshop on Partial Evaluation and Semantics Based Program Manipulation, and PPDP 2004 - 6th ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming.

Past workshops were held in Manchester, UK (1991, 1992, 1998), Louvain-la-Neuve, Belgium (1993), Pisa, Italy (1994), Arnhem, the Netherlands (1995), Stockholm, Sweden (1996), Leuven, Belgium (1997), Venice, Italy (1999), London, UK (2000), Paphos, Cyprus (2001), Madrid, Spain (2002), Uppsala, Sweden (2003). Since 1994 the proceedings have been published in the LNCS series of Springer-Verlag.

LOPSTR also aims to be a lively, friendly forum for presenting and discussing work in progress, so it is a real workshop in the sense that it is also intended to provide useful feedback to authors on their preliminary research. Formal proceedings of the workshop are produced only after the workshop, so that authors can incorporate this feedback in the published papers.

Accepted Papers:

Colloquium on Implementation of Constraint Logic Programming Systems
Saint-Malo, France, September 8, 2004

This workshop aims at discussing and exchanging experience on the design, implementation, and optimization of logic, constraint (logic) programming systems, and systems intimately related to logic as a means to express computations. Experience backed up by real implementations and their evaluation will be given preference, as well as descriptions of work in progress in that direction.

Workshop Program:

Workshop on Multiparadigm Constraint Programming Languages
Saint-Malo, France, September 6-7, 2004

Multiparadigm programming languages combine different programming paradigms, such as functional, logic, imperative, constraint or concurrent ones. The idea of a multiparadigm language is to increase expressiveness and problem-solving power such that the programmer can use a wide range of styles and language features from different paradigms.

Many different approaches to the integration of programming paradigms have been explored in recent years, like the combination of functional and logic languages (e.g., Curry, Mercury, Toy), logic and concurrent languages (e.g., Oz and CHR), logic and imperative languages (e.g., Alma-0) among many other proposals.

While the integration of constraints into general-purpose programming languages has been widely investigated for the case of logic programming, interesting solutions have been obtained as well by merging constraints and languages not based on a purely logic paradigm. The integration of constraints with other programming paradigms, even if it is not that exhaustively examined, is as well promising and a topic of current research.

The aim of the workshop is to bring together people interested in multiparadigm constraint programming, language design and implementation to communicate and discuss recent developments, work in progress, and new research directions in combining constraints with languages that are not purely logic based, like functional logic, functional, imperative and object-oriented languages.

Workshop Program:

Monday, September 6th
WLPE session, 14:30-16:30

Tuesday, September 7th
MultiCPL session, 11:00 - 12:30

WLPE session, 14:30 - 17:00

Workshop on Teaching Logic Programming
Saint-Malo, France, September 8-9, 2004

Following the panel discussion at ICLP 2003 in Mumbai (India) the first international workshop on Teaching Logic Programming TeachLP 2004 will be held in Saint Malo, France. The meeting will be run as a workshop at the 2004 International Conference on Logic Programming, which will be held on September 6-10, 2004.

Logic Programming and Constraint Logic Programming (LP, CLP) are very powerful programming paradigms, but hard to learn without sufficient help. For further spreading the technology it should be taught to a broader range of computer science students. The workshop will investigate what is currently taught and how; it will also discuss what should be taught and why.

Accepted Papers:

Workshop on Logic Programming Environments
Saint-Malo, France, September 6-7, 2004

The aim of the workshop is to provide an informal meeting for the researchers working on tools for the development and analysis of logic programs. This year we want to emphasize two aspects: on one hand we want to discuss the presentation, pragmatics and experiences of such tools; on the other one, we want to extend the concept of ``logic programming'' environments to tools developed for any language based on computational logic (constraints, integration of paradigms, specification languages, ...).

Preliminary Program:

Monday, September 6th
WLPE session, 14:30-16:30

Tuesday, September 7th
MultiCPL session, 11:00 - 12:30

WLPE session, 14:30 - 17:00

Principles and Practice of Semantic Web Reasoning
Saint-Malo, France, September 8-9, 2004

The workshop on "Principle and Practice of Semantic Web Reasoning'' will be a forum for discussing various forms of reasoning that are or can be used on the Semantic Web. The workshop will address both, reasoning methods for the Semantic Web and Semantic Web applications relying upon various forms of reasoning.

Accepted Papers:

Annual Conference of the European Association for Computer Science Logic
Wroclaw University, Poland, September 20-24, 2004

Computer Science Logic (CSL) is the annual conference of the European Association for Computer Science Logic (EACSL). The conference is intended for computer scientists whose research activities involve logic, as well as for logicians working on issues significant for computer science.


Monday, September 20

Session 1: 9.00 am – 10.15 am
Invited talk: Ken McMillan, Applications of Craig Interpolation to Model Checking
Session 2: 10.45 am – 12.15 pm
Krishnendu Chatterjee, Rupak Majumdar, and Marcin Jurdzinski, On Nash Equilibria in Stochastic Games
Mikolaj Bojanczyk, A Bounding Quantifier
Hugo Gimbert, Parity and Exploration Games on Infinite Graphs
Session 3: 1.30 pm – 3.00 pm
Harald Ganzinger and Konstantin Korovin, Integrating Equational Reasoning into Instantiation-based Theorem Proving
George Metcalfe, Nicola Olivetti, and Dov Gabbay, Goal-Directed Methods for Lukasiewicz Logic
Jeremy E. Dawson and Rajeev Goré, A General Theorem on Termination of Rewriting
Session 4: 3.30 pm – 5.00 pm
Pierre Hyvernat, Predicate Transformers and Linear Logic: yet another Denotational Model
Pietro Di Gianantonio, Structures for Multiplicative Cyclic Linear Logic: Deepness vs Cyclicity
Lutz Straßburger and François Lamarche, On Proof Nets for Multiplicative Linear Logic with Units

Tuesday, September 21

Session 5: 9.00 am – 10.15 am
Invited talk: Pawel Urzyczyn, My (Un)Favourite Things
Session 6: 10.45 am – 12.15 pm
Neil Immerman, Alex Rabinovich, Tom Reps, Mooly Sagiv and Greta Yorsh, The Boundary Between Decidability and Undecidability for Transitive Closure Logics
Marcelo Arenas, Pablo Barceló, and Leonid Libkin, Game-based Notions of Locality over Finite Models
Andreas Abel and Ralph Matthes, Fixed Points of Type Constructors and Primitive Recursion
Session 7: 1.30 pm – 3.00 pm
Aleksy Schubert, On the Building of Affine Retractions
Philippe de Groote and Sylvain Salvati, Higher-order Matching in the Linear λ-calculus with Pairing
Ulrich Schöpp and Ian Stark, A Dependent Type Theory with Names and Binding
Session 8: 3.30 pm – 5.00 pm
Tjark Weber, Towards Mechanized Program Verification with Separation Logic
Roberto M. Amadio, Solange Coupet-Grimal, Silvano Dal Zilio, and Line Jakubiec, A Functional Scenario for Bytecode Verification of Resource Bounds
Roberto Giacobazzi and Isabella Mastroeni, Proving Abstract Non-Interference

Wednesday, September 22

Session 9: 9.00 am – 10.15 am
Invited talk: Dale Miller, Bindings, mobility of bindings, and the ∇-quantifier
Session 10: 10.45 am – 12.15 pm
Patrick Maier, Intuitionistic LTL and a New Characterization of Safety and Liveness
Philipp Rohde, Moving in a Crumbling Network: The Balanced Case
E. Allen Emerson and Vineet Kahlon, Parameterized Model Checking of Ring-based Message Passing Systems

Thursday, September 23

Session 11: 9.00 am – 10.15 am
Invited talk: Martin Hyland, Abstract Interpretation of Proofs: Classical Propositional Logic
Session 12: 10.45 am – 12.15 pm
Alan Skelley, A Third-Order Bounded Arithmetic Theory for PSPACE
Andrés Cordón-Franco, Alejandro Fernández-Margarit, and F. Félix Lara-Martín, Provably Total Primitive Recursive Functions: Theories with Induction
David Richerby, Logical Characterizations of PSPACE
Session 13: 1.30 pm – 3.00 pm
Lutz Schröder, The Logic of the Partial λ-Calculus With Equality
Jean Goubault-Larrecq, Slawomir Lasota, David Nowak, and Yu Zhang, Complete Lax Logical Relations for Cryptographic Lambda-Calculi
Jérôme Vouillon, Subtyping Union Types
Session 14: 3.30 pm – 5.00 pm
Margarita Korovina and Nicolai Vorobjov, Pfaffian Hybrid Systems
Yukiyoshi Kameyama, Axioms for Delimited Continuations in the CPS Hierarchy
Pawel Rychlikowski and Tomasz Truderung, Set Constraints on Regular Terms

Friday, September 24

Session 15: 9.00 am – 10.15 am
Invited talk: Albert Atserias, Notions of Average-Case Complexity for Random 3-SAT
Session 16: 10.45 am – 12.15 pm
Christopher Lynch, Unsound Theorem Proving
Alessandro Avellone, Camillo Fiorentini, Guido Fiorino, and Ugo Moscato, An Efficent Implementation of a Tableau Calculus for a Logic with a Constructive Negation
Agata Ciabattoni, Automated Generation of Analytic Calculi for Logics with Linearity

International Conference on Principles and Practice of Constraint Programming
Toronto, Canada, September 27-October 1, 2004

The CP conference is the annual international conference on constraint programming, and it is concerned with all aspects of computing with constraints, including: algorithms, applications, environments, languages, models, and systems. CP 2004 includes a technical programme, where presentations of theoretical and application papers, as well as invited talks and tutorials, aim at describing the best results and techniques in the state-of-the-art of constraint programming. Moreover, CP 2004 continues the tradition of the CP doctoral programme, in which PhD students can present their work, listen to tutorials on career and ethical issues, and discuss their work with senior researchers via a mentoring scheme. There will also be a number of workshops, where researchers will be able to meet in an informal setting and discuss their most recent ideas with their peers.


Distinguished Papers:
Paper 26: Consistency and Random Constraint Satisfaction Models with a high Constraint Tightness
Yong Gao and Joseph Culberson

Paper 68: Constraint-Based Combinators for Local Search
Pascal Van Hentenryck, Laurent Michel, and Liyuan Liu

Paper 86: Unary Resource Constraint with Optional Activities
Petr Vilim, Roman Bartak, Ondrej Cepek

Paper 176: Statistical Regimes Across Constrainedness Regions
Carla Gomes, Cesar Fernandez, Bart Selman, and Christian Bessiere

Full Papers:

Paper 9:
Theoretical Foundations of CP-based Lagrangian Relaxation
Meinolf Sellmann

Paper 13: Set Domain Propagation Using ROBDDs
Vitaly Lagoon and Peter J. Stuckey

Paper 25: Heuristic Selection for Stochastic Search Optimization: Modeling Solution Quality by Extreme Value Theory
Vincent A. Cicirello, Stephen F. Smith

Paper 32: A hybrid method for planning and scheduling
John Hooker

Paper 49: Deriving Filtering Algorithms from Constraint Checker
Nicolas Beldiceanu, Mats Carlsson, Thierry Petit

Paper 56: Constraint Satisfaction in Semi-structured Data Graphs
Nikos Mamoulis, Kostas Stergiou

Paper 60: Decomposition and learning for a real time task allocation problem
Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie Diplanche, Narendra Jussien, Yvon Trinquet

Paper 67: Leveraging the Learning Power of Examples in Automated Constraint Acquisition
Christian Bessiere, Remi Coletta, Eugene C. Freuder, and Barry O'Sullivan

Paper 72: Disjoint, Partition and Intersection Constraints for Set and Multiset Variables
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Toby Walsh

Paper 74: A Hyper-Arc Consistency Algorithm for the Soft Alldifferent Constraint
Willem Jan van Hoeve

Paper 75: Impact-Based Strategies for Constraint Programming
Philippe Refalo

Paper 77: Propagation Guided Large Neighborhood Search
Laurent Perron

Paper 78: Constraint Propagation as a Proof System
Albert Atserias, Phokion G. Kolaitis, and Moshe Y. Vardi

Paper 81: Generating Robust Schedules through Chaining
N. Policella, A. Oddi, S.F. Smith, and A. Cesta

Paper 84: A Constraint for Bin Packing
Paul Shaw

Paper 93: Completable Partial Solutions in Constraint Programming and Constraint-based Scheduling
Andras Kovacs and Jszsef Vancza

Paper 95: Symbolic Decision Procedures for QBF
Guoqiang Pan, Moshe Y. Vardi

Paper 99: Improved bound computation in presence of several clique constraints
Jean-Francois Puget

Paper 105: (Smart) Look-Ahead Arc Consistency and the Pursuit of CSP Tractability
Hubie Chen and Victor Dalmau

Paper 106: Quantified Constraint Satisfaction and 2-Semilattice Polymorphisms
Hubie Chen

Paper 109: Bounding the Resource Availability of Partially Ordered Events with Constant Resource Impact
Jeremy Frank

Paper 111: Strategies for Global Optimization of Temporal Preferences
Paul Morris, Robert Morris, Lina Khatib, Sailesh Ramakrishnan, Andrew Bachmann

Paper 112: Improved Algorithms for the Global Cardinality Constraint
Claude-Guy Quimper, Alejandro Lopez-Ortiz, Peter van Beek, Alexander Golynski

Paper 117: An Efficient Complete (Weighted) Max-SAT Solver
Zhao Xing and Weixiong Zhang

Paper 120: A Complete Characterization of Complexity for Boolean Constraint Optimization Problems
David Cohen, Martin Cooper, Peter Jeavons

Paper 121: Subproblem Substitutability by Satisfiability Encoding
Steven Prestwich

Paper 122: Controllability of Soft Temporal Constraint Problems
Francesca Rossi and Kristen Brent Venable and Neil Yorke-Smith

Paper 125: Financial Portfolio Optimisation
Pierre Flener, Justin Pearson, and Luis G. Reyna

Paper 130: A Regular Language Membership Constraint for Finite Sequences of Variables
Gilles Pesant

Paper 131: A Domain Consistency Algorithm for the Stretch Constraint
L. Hellsten, G. Pesant, P. van Beek

Paper 132: Speeding Up Constraint Propagation
Christian Schulte and Peter J. Stuckey

Paper 133: Backtrack-Free Search for Real-Time Constraint Satisfaction
J. Christopher Beck, Tom Carchrae, Eugene C. Freuder, and Georg Ringwelski

Paper 138: Monotone Literals and Learning in QBF reasoning
Enrico Giunchiglia, Massimo Narizzano, Armando Tacchella

Paper 141: The Cardinality Matrix Constraint
Jean-Charles Regin and Carla Gomes

Paper 161: ID Walk: A Candidate List Strategy with a Simple Diversification Device
Bertrand Neveu, Gilles Trombettoni, Fred Glover

Paper 169: Solving Non-clausal Formulas with DPLL search
Christian Thiffault, Fahiem Bacchus, Toby Walsh

Paper 178: New Look-Ahead Schemes for Constraint Satisfaction
Kalev Kask, Rina Dechter, and Vibhav Gogate

Paper 184: Global Constraints for Integer and Set Value Precedence
Y.C. Law and J.H.M. Lee

Paper 187: Streamlining Constraint Reasoning
Carla Gomes and Meinolf Sellmann

Paper 192: Quality of LP-based Approximations for Highly Combinatorial Problems
Lucian Leahu and Carla Gomes

Paper 197: Hybrid Set Domains to Strengthen Constraint Propagation and Reduce Symmetries
Andrew Sadler Carmen Gervet

Paper 203: Understanding Random SAT: Beyond the Clauses-to-Variables Ratio
Eugene Nudelman, Alex Devkar, Yoav Shoham, Kevin Leyton-Brown

Short Papers:

Paper 14: Solving the Crane Scheduling Problem using Intelligent Search Schemes
Andrew Lim, Brian Rodrigues, Zhou Xu

Paper 23: Concurrent Dynamic Backtracking for Distributed CSPs
Roie Zivan and Amnon Meisels

Paper 33: A General Extension of Constraint Propagation for Constraint Optimization
Xiaofei Huang

Paper 37: Algorithms for Quantified Constraint Satisfaction Problems
Nikos Mamoulis, Kostas Stergiou

Paper 38: A New Algorithm for Maintaining Arc Consistency after Constraint Retraction
Pavel Surynek, Roman Bartak

Paper 41: Computing the Frequency of Partial Orders
M.R.C. van Dongen

Paper 50: The Tractability of Global Constraints
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Toby Walsh

Paper 51: Support inference for generic filtering
Frederic Boussemart, Fred Hemery, Christophe Lecoutre, and Lakhdar

Paper 82: How much backtracking does it take to color random graph? Rigorous results on heavy tails
Haixia Jia and Cristopher Moore

Paper 114: On Tightness of Constraints
Yuanlin Zhang

Paper 127: Variable ordering heuristics show promise
J. Christopher Beck Patrick Prosser Richard J. Wallace

Paper 136: Strong Cost-based Filtering for Lagrange Decomposition Applied to Network Design
Wilhelm Cronholm and Farid Ajili

Paper 140: Improving the applicability of adaptive consistency: Preliminary results 
Marti Sanchez Pedro Meseguer Javier Larrosa

Paper 170 : On-Demand Bound Computation for Best-First Constraint Optimization
Martin Sachenbacher and Brian Williams

Paper 181: Preprocessing Techniques for Distributed Constraint Optimization
Syed Muhammad Ali, Sven Koenig, Milind Tambe

Paper 183: The Impact of AND/OR Search Spaces on Constraint Satisfaction and Counting
Rina Dechter and Robert Mateescu

International Conference on Artificial Intelligence and Symbolic Computation
Linz, Austria, September 22-24, 2004


Conferences in this series are held every two years. The previous six ones took place in
  1. Karlsruhe (Germany),
  2. Cambridge (United Kingdom),
  3. Steyr (Austria),
  4. Plattsburgh(USA),
  5. Madrid (Spain), and
  6. Marseille (France)
the first three under the name "Artificial Intelligence and Symbolic Mathematical Computing (AISMC)". The conference in the year 2004 will be held at RISC in the Castle of Hagenberg, Austria.

The AISC 2004 conference poster can be downloaded here: AISC-2004.pdf (126 KB).


Artificial Intelligence and Symbolic Computation are two views and approaches for automating problem solving, in particular mathematical problem solving. The two approaches are based on heuristics and on mathematical algorithmics, respectively. Artificial Intelligence can be applied to Symbolic Computation and Symbolic Computation can be applied to Artificial Intelligence. Hence, a wealth of challenges, ideas, theoretical insights and results, methods and algorithms arise in the interaction of the two fields and research communities. Advanced tools of software technology and system design are needed and a broad spectrum of applications is possible by the combined problem solving power of the two fields.

Hence, the conference is in the center of interest and interaction for various research communities:



International Conference on Concurrency Theory
London, England, August 30-September 4, 2004

Concur 2004, the 15th International Conference on Concurrency Theory, takes place at the Royal Society, London, from Tuesday 31 August - Friday 3 September 2004.

The purpose of the CONCUR conferences is to bring together researchers, developers and students in order to advance the theory of concurrency, and promote its applications. Interest in this topic is continuously growing, as a consequence of the importance and ubiquity of concurrent systems and their applications, and of the scientific relevance of their foundations.

Accepted Papers:

A Higher Order Modal Fixed Point Logic
  Mahesh Viswanathan, Ramesh Viswanathan
A symbolic decision procedure for cryptographic protocols with time stamps
  L. Bozga, C. Ene and Y. Lakhnech
An Extensional Spatial Logic for Mobile Processes
  Daniel Hirschkoff
Asynchronous Games 2: The true concurrency of innocence
  Paul-André Melliès
Basic Theory of Reduction Congruence for Two Timed Asynchronous Pi-Calculi
  Martin Berger
Characterizing EF and EX tree logics
  Mikolaj Bojanczyk Igor Walukiewicz
Comparing Infinite-State Systems with Their Finite-State Specifications
  A. Kucera, Ph. Schnoebelen
Compiling Pattern Matching in Join-Patterns
  Qin Ma and Luc Maranget
Deciding Probabilistic Bisimilarity over Infinite-State Probabilistic Systems
  T. Brazdil, A. Kucera, O. Strazovsky
Elimination of Quantifiers and Undecidability in Spatial Logics for Concurrency
  Luis Caires and Etienne Lozes
Extended Process Rewrite Systems: Expressiveness and Reachability
  Mojmir Kretinsky, Vojtech Rehak, Jan Strejcek
Message-Passing Automata are expressively equivalent to EMSO Logic
  Benedikt Bollig and Martin Leucker
Model Checking Timed Automata with One or Two Clocks
  F. Laroussinie, N. Markey, Ph. Schnoebelen
Model Checking Restricted Sets of Timed Paths
  N. Markey and J.-F. Raskin
Modular Construction of Modal Logics
  Corina Cirstea and Dirk Pattinson
muABC: A Minimal Aspect Calculus
  Glenn Bruns, Radha Jagadeesan, Alan Jeffrey, James Riely
On Flatness for 2-dimensional Vector Addition Systems with States
  Jérôme Leroux and Grégoire Sutre
Open maps, alternating simulations and control synthesis
  Paulo Tabuada
Parameterised boolean equation systems (extended abstract)
  Jan Friso Groote and Tim A.C. Willemse
Probabilistic Event Structures and Domains
  Daniele Varacca, Hagen Voelzer, Glynn Winskel
Resource Control for Synchronous Cooperative Threads
  Roberto M. Amadio and Silvano Dal Zilio
Reversible Communicating Systems
  Vincent Danos, Jean Krivine
Session Types for Functional Multithreading
  Vasco Vasconcelos and Antonio Ravara and Simon Gay
Symbolic Bisimulation in the Spi Calculus
  Johannes Borgström, Sébastien Briais, Uwe Nestmann
The pros and cons of netcharts
  Nicolas BAUDRU & Remi MORIN
Timed vs Time-Triggered Automata
  Pavel Krcal, Leonid Mokrushin, P.S. Thiagarajan and Wang Yi
Type Based Discretionary Access Control
  Michele Bugliesi, Dario Colazzo, Silvia Crafa
Verification by Network Decomposition
  Edmund Clarke, Muralidhar Talupur, Tayssir Touili, Helmut Veith
Verifying Finite-State Graph Grammars: an Unfolding-Based Approach
  Paolo Baldan, Andrea Corradini, Barbara Koenig

Call for Papers

List of Events:

Workshop on Deduction and Reasoning Techniques
Puebla, Mexico, November 22-23, 2004

Authors are invited to submit papers presenting original and unpublished research work in all areas related to Deduction and Reasoning. The topics of interest of the workshop include, but are not limited to:

- Logic programming and nonmonotonic reasoning
- Answer Set Programming
- Knowledge and Belief Representation
- Representation of Beliefs
- Satisfiability Problems
- Deduction Techniques
- Automated reasoning
- Non-classical logics
- Reasoning about situations and actions
- Mathematical Structures (Algebraic, Topologic, etc.)
- Natural Language Processing.
- Knowledge Discovery and Data Mining.
- AI in Education and Intelligent Tutoring Systems


Papers should be written in English, formatted according to the Springer LNCS style and should not exceed 8 pages including references and figures. Submissions in Spanish can also be considered, but we strongly encourage authors to write in English. Please visit the web page for submission details.


Paper submission: August 20th, 2004
Notification of acceptance: September 17th, 2004
Final version due: October 1st, 2004
DTS 04: November 22-23rd, 2004


Leopoldo Bertossi, Carleton University, Canada
Antonio Brogi, Universita' di Pisa, Italy
Pedro Cabalar, Universidad de Coruña, Spain
Marina De Vos, University of Bath, United Kingdom
Alfredo Gabaldón, University of Toronto, Canada
Vladik Kreinovich, University of Texas at El Paso, United States
Alessandro Provetti, Universita' di Milano, Italy
Franco Salvetti, University of Colorado-Boulder, United States


Jose Arrazola Ramirez, Benemerita Universidad Autonoma de Puebla, Mexico
Cesar Bautista, Benemerita Universidad Autonoma de Puebla, Mexico
Rogelio Davila Perez, Instituto Tecnologico y de Estudios Superiores de Monterrey - Campus Guadalajara, Mexico
Guillermo De Ita, Instituto Nacional de Astrofisica, Optica y Electronica,
Guillermo Morales, Centro de Investigacion y de Estudios Avanzados del IPN, Mexico
Mauricio Osorio, Universidad de las Americas, Puebla, Mexico


Dr. Mauricio Osorio Galindo
Department of Computer Science and Engineering
Universidad de las Americas, Puebla. México

Dr. Jose Ramon Enrique Arrazola Ramírez
Facultad de Ciencias Fisico-Matematicas
Benemerita Universidad Autonoma de Puebla, Mexico


Claudia Zepeda Cortes, Universidad de las Americas - Puebla
Magdalena Ortiz, Universidad de las Americas - Puebla

Logic-Based Agent Verification
Special Issue of the Journal of Applied Logic


The view of computational components as `agents' is widely used in contemporary software applications, such as Internet navigation, information management, autonomous process control, and e-commerce. The popularity of the agent paradigm stems not only from its intuitive and appealing nature, capturing the notions of flexibility and evolving behaviour, but also from the range of theories, tools and techniques that have been developed over recent years for agent-based systems.

However, the increasing use of agents in (business, mission, safety) critical applications, together with the development of infrastructures such as the world-wide web and wireless computing is leading to new problems. Central amongst these is that of the *trustworthiness* of agent software. Can agents be trusted to autonomously make decisions in critical areas? In addition, once large numbers of agents are present, can they work together safely?

Thus, it is important to be able to guarantee predictable behaviour for agent-based systems if these are to be used in critical applications. Verification of agent-based behaviour is a complex problem: the behaviour of individual agents must be verified; collections of agents must be shown to be able to work together effectively; and agents that communicate over wider distances and multiple sites must be shown to retain security properties. Tackling
these problems often requires a large number of diverse techniques, and many such techniques are based on formal logics, thus providing the clear semantic basis for the verification tasks.

The aim of this special issue is to bring together high-quality papers exhibiting leading edge research where a "logic-based" approach is taken to the verification of agent-based systems. We here take a broad view of logic, and consider a wide range of logical verification techniques (incorporating theorem-proving, model checking, algebraic, abstract machines, etc.).


The Journal of Applied Logic (Elsevier) publishes papers in areas of logic which can be applied in other disciplines as well as application papers in those disciplines, the unifying theme being logics arising from modelling the human agent.


Submission deadline: 15th October 2004
Author notification: 15th February 2005
Revised papers due: 15th April 2005


The topics of interest of this special issue include (but are not limited to)


We invite submission of full (typically, 20-40 pages) high-quality research papers for this special issue. These should neither have been previously published in their full form, nor be under review elsewhere. Submissions consisting of the paper (preferably PDF or Postscript via email but, alternatively, five hard-copies) including an abstract in which the role of logic in the particular approach used is clarified, should be sent to Michael Fisher (address given below) to arrive no later than 15th October 2004. Formatting instructions can be found at the journal's web site.

Queries concerning this special issue should be directed to any of the guest editors. Up-to-date information will also be available from


Department of Computer Science,
University of Liverpool, Liverpool L69 7ZF, UK
email: url:

Department of Computer Science,
North Carolina State University, Raleigh, USA
email: url:

Department of Computer Science,
University of Wyoming, Laramie, USA
email: url:

Department of Computer Science,
University of Liverpool, Liverpool L69 7ZF, UK
email: url:

1st World Congress and School on Universal Logic
Montreux, Switzerland, March 26-April 3, 2005

This event will focus on:

  1. Techniques that can be used for a general theory of logics (Labelled deductive systems, Kripke structures, Logical matrices, etc.) ;
  2. Studies  of classes of logics (Substructural logics, Non monotonic logics, Paraconsistent logics, etc.)
  3. Scope of validity and domain of application of fundamental theorems of logic (Completeness, Deduction, Cut-elimination, etc.)
  4. Philosophical considerations about the nature of logic and the universality of some logical laws or axioms

The school is intended for advanced students and young researchers. There will be about 20 tutorials on many subjects: combination of logics, multiple conclusion logic, combinatory logic, logics and games,  abstract model theory, logic as language vs. logic as calculus,  category theory for logics, etc.

Invited speakers of the congress will include A.Avron, D.Batens, J.Corcoran, M.Dunn, D.Gabbay, R.Jansana, A.Koslow, Paiva, K.Segerberg.

Contributed papers for the congress can be submitted before October 30, 2004.

More information on the website:

International Conference on Applications of Declarative Programming and Knowledge Management
 (INAP 2005)
Waseda University, Japan, October 1-3, 2005

You are invited to propose sessions and other contributions to the 16th International Conference on Applications of Declarative Programming and Knowledge Management, INAP2005, Oct 1-3 2005, Waseda University, Japan.

October 1-3, 2005
Waseda University, Kitakyushu, Japan
Program Co-Chair:
Masanobu Umeda, Kyushu Institute of Technology, Japan
Program Co-Chair:
Armin Wolf,	Fraunhofer FIRST, Germany
Local Organization:
Osamu Yoshie, Waseda University, Japan
Conference Chair:
Oskar Bartenstein, IF Computer Japan, Japan
Constraints Track Chair:
Ulrich Geske, Fraunhofer FRIST, Germany
Knowledge Management Track Chair:
Dietmar Seipel, Universitaet Wuerzburg, Germany
Application Track Chair:
Osamu Takata, Kyushu Institute of Technology, Japa

Suggestions may include any topic of scientific and practical interest. Focus is as with the previous events in Berlin 2004 and Tokyo 2001 on the use of logic programming methods for industrial, commercial, societal applications.

For information on past conferences see

Please address suggestions to Oskar Bartenstein or any other member of the INAP community.

Oskar Bartenstein

Seventh International Symposium on Practical Aspects of Declarative Languages
(PADL 2005)
Long Beach, California, January 10-11, 2005

[Co-located with ACM POPL, January 12-14, 2005]

Declarative languages build on sound theoretical foundations to provide attractive frameworks for application development. These languages have been successfully applied to a wide array of different real-world situations, including database management, active networks, software engineering, decision support systems, or music composition.

New developments in theory and implementation have opened up new application areas. At the same time, the application of declarative languages to novel problems raises numerous interesting research issues. Well-known questions include designing for scalability, language extensions for application deployment, and programming environments. Thus, applications often drive the progress in the theory and implementation of declarative systems, and benefit from this progress as well.

PADL is a forum for researchers and practioners to present original work emphasizing novel applications and implementation techniques for all forms of declarative concepts, including, functional, logic, constraints, etc. Topics of interest include:
PADL 05 welcomes new ideas and approaches pertaining to applications and implementation of declarative languages, and is not limited to the scope of the first six PADL symposia (past proceedings can be found in Springer Verlag LNCS, numbers 1551, 1753, 1990, 2257, 2562, and 3057).

In this occasion PADL is co-located, as traditionally, with ACM POPL, which will be held immediately following PADL, January 12-14.

Paper Submission: September 10, 2004
Notification: October 10, 2004
Camera-ready: November 10, 2004
Symposium: January 10-11, 2005

Authors should submit an electronic copy of the full paper (written in English) in Postscript (Level 2) or PDF. Submission should be completed using the electronic procedure available at the conference website. Papers must be no longer than 15 pages, written in 11-point font and with single spacing. Since the final proceedings will be published as Lecture Notes in Computer Science by Springer Verlag, authors are strongly encouraged to use the LNCS paper formatting guidelines for their submission.

Each submission must include on its first page the paper title; authors and their affiliations; contact author's email and postal addresses, telephone and fax numbers, abstract, and three to four keywords. The keywords will be used to assist us in selecting appropriate reviewers for the paper. If electronic submission is impossible, please contact the program chairs for information on how to submit hard copies.

A cash prize of US$500 will be awarded to the submission that is judged by the program committee to be the best in terms of practicality, originality, and clarity of presentation. The program committee may choose not to make an award; or may make multiple awards, in which case the award money will be evenly divided.

Please visit the conference web site:
for further information.
For additional information about papers and submissions, please contact the Program Chairs:

Manuel Hermenegildo (1,2), or
Daniel Cabeza (2)
1 Departments of Computer Science and Electrical and Computer Engineering
   The University of New Mexico,
   Albuquerque, NM 87131, U.S.A.

2 Facultad de Informatica,
   Universidad Politecnica de Madrid
   28660-Boadilla del Monte,
   Madrid, Spain

For additional information about the conference please contact the General Chair:

Gopal Gupta
Department of Computer Science
University at Texas at Dallas,
Dallas, TX, U.S.A.

16th International Conference on Rewriting Techniques and Applications
Nara, Japan, April 19-21, 2005

The 16th Int. Conf. on Rewriting Techniques and Applications (RTA'05)  will collocate with the 7th International Conference on Typed Lambda Calculi and Applications (TLCA'05) as part of the Federated Conference on Rewriting, Deduction and Programming (RDP'05).

Deadline for electronic submission of title and abstract:
Nov    12, 2004
Deadline for electronic submission of papers:
Nov    19, 2004
Notification of acceptance of papers:
Jan    14, 2005
Deadline for final versions of accepted papers:
 Feb     4, 2005
Apr 19-21, 2005
RTA is the major forum for the presentation of research on all aspects of rewriting. Typical areas of interest include (but are not limited to):

Invited talks will be given at RTA'05 by:

An award of 100,000 Yen will be given to the best paper or papers as decided by the PC.


Submissions must be original and not submitted for publication elsewhere. Submission categories include regular research papers and system descriptions. Also problem sets and submissions describing interesting applications of rewriting techniques will be very welcome. The page limit is 15 pages (10 pages for system descriptions).
As usual, accepted papers will appear in the Springer-Verlag Lecture Notes in Computer Science series. More information about paper submission is available at the RTA'05 web page.

The conference takes place in Nara park, which is one of the most important cultural sights of Japan with some of the oldest and most impressive temples and shrines. Airfares from Europe or the US to Japan are not expensive in mid-April and the conference will offer reasonably priced accommodation and low registration fees.

Juergen Giesl
LuFG Informatik II
RWTH Aachen
Ahornstr. 55
52074 Aachen

Hitoshi Ohsaki

6th International Conference on Verification, Model-checking, and Abstract Interpretation
Paris, France, January 17-20, 2005

VMCAI provides a forum for researchers from the communities of Verification, Model Checking, and Abstract Interpretation, facilitating interaction, cross-fertilization, and advancement of hybrid methods that combine the three areas. With the growing need for formal methods to reason about complex, infinite-state, and embedded systems, such hybrid methods are bound to be of great importance.

The program of VMCAI'05 will consist of invited tutorials, refereed papers, invited lectures on -Perspectives in Program Verification- and invited demonstrations of -Tools for Program Verification-.

Papers are solicited reporting new results as well as experimental evaluation and comparisons of existing techniques. Topics include but are not limited to:
Submissions can address any programming paradigm, including concurrent, constraint, functional, imperative, logic and object-oriented programming.

Papers must describe original work, be written and presented in English, and must not substantially overlap with papers that have been published or that are simultaneously submitted to a journal or a conference with refereed proceedings.

Submission instructions:

All submissions must be performed electronically at (use of this page requires a recent, script-enabled HTML browser). Submitted papers should be at most (LNCS style) 15 pages excluding bibliography and well-marked appendices. Program committee members are not required to read the appendices, and thus papers should be intelligible without them.

The proceedings will be published by Springer in the Lecture Notes in Computer Science series (see the LNCS Author's Instructions ). Thus, adhering to that style already in the submission is strongly encouraged. Papers should be
submitted either in PostScript or PDF format and they should be interpretable by Ghostscript or Acrobat Reader. Papers must be printable on either A4 paper or US letter, and preferably on both.

Journal Special Issue:
Selected papers will be invited to a Journal Special Issue.

Best Paper Award:
Starting this VMCAI'05, the program committee may select papers accepted to the conference as VMCAI Best Papers.

Important dates:
Deadline for submissions :
September 6, 2004, 19:00 UTC/GMT
Notification of acceptance or rejection: 
October 11, 2004
Deadline for reception of the final versions :
November 8, 2004
The conference : 
January 17-20, 200

Program Committee:

Agostino Cortesi Università Ca'Foscari di Venezia (I)
Radhia Cousot CNRS / École Polytechnique (F)
E. Allen Emerson University of Texas, Austin (USA)
Roberto Giacobazzi Università degli Studi di Verona (I)
Chris Hankin Imperial College (UK)
Warren A. Hunt University of Texas, Austin (USA)
Ken McMillan Cadence Berkeley (USA)
David Monniaux CNRS / École Normale Supérieure (F)
Amir Pnueli Weizmann Institute of Science (IL)
Andreas Podelski Max-Planck-Institut für Informatik (G)
Francesco Ranzato Università di Padova (I)
Hanne Riis Nielson Technical University of Denmark (DK)
Shmuel Sagiv Tel-Aviv University (IL)
Bernhard Steffen Universität Dortmund (G)
Reinhard Wilhelm Universität des Saarlandes (G)

Program Chair:

Post: Radhia Cousot
École Polytechnique - STIX, 91128 Palaiseau cedex, France
Fax: + 33 (0)1 69 33 30 50
Phone: + 33 (0)1 69 33 45 95

VMCAI Steering Committee:

Agostino Cortesi Università Ca'Foscari di Venezia (I)
E. Allen Emerson University of Texas, Austin (USA)
Giorgio Levi Università di Pisa (I)
Thomas W. Reps University of Wisconsin-Madison (USA)
Andreas Podelski Max-Planck-Institut für Informatik (G)
David A. Schmidt Kansas State University (USA)
Lenore Zuck New York University (USA)

Constraint Solving and Programming
track at ACM Symposium on Applied Computing
Santa Fe, New Mexico, March 13-17, 2005


Constraints have emerged as the basis of a representational and computational paradigm that draws from many disciplines and can be brought to bear on many problem domains.


The track is concerned with all aspects of computing with constraints including algorithms, applications, environments, languages, models, and systems. Contributions are welcome from any discipline concerned with constraints, including artificial intelligence, combinatorial algorithms, computational logic, concurrent computation, databases, discrete mathematics, operations research, programming languages, and symbolic computation. We also solicit papers from any domain employing constraints, including computational linguistics, configuration, decision support, design, diagnosis, graphics, hardware verification, molecular biology, planning, qualitative reasoning, real-time systems, resource allocation, robotics, scheduling, software engineering, temporal reasoning, vision, visualization, and user interfaces. Papers that bridge disciplines or combine theory and practice or discuss novel reasoning methods are especially welcome. A special attention is focused around the use of constraint technologies in the networking, wireless and internet fields.


We would like to invite authors to submit papers on research on constraint solving and programming, with particular emphasis on assessing the current state of the art and identifying future directions.

Preliminary guidelines

Submissions should be properly anonymized to facilitate blind reviewing: papers being submitted should not list the authors, affiliations or addresses on the first page and authors are also encouraged to take care throughout the entire document to minimise references that may reveal the identity of the authors or institution. The body of each paper should not exceed 4,000 words. Papers failing to comply with length limitations risk immediate rejection.

At least three reviewers will be assigned to each submission to the track. Accepted papers are published by ACM in both printed form and CD-ROM; they are also available on the Web through the ACM Digital Library. Once accepted, papers must fit within five (5) two column pages (please check the author kit on the main SAC website: the format is usually the format used in the ACM templates), with the option (at additional expense) to add three (3) more pages.
A second set of selected papers, which did not get accepted as full papers, will be accepted as posters and will be published as extended 2-page abstracts in the symposium proceedings.

Authors of accepted papers must be prepared to sign a copyright statement and must pay the registration fee and guarantee that their paper will be presented at the conference.

Paper submissions should be sent (as an attached PDF file) to:

The body of the email should include the title of the paper, the author(s) name(s) and affiliation(s), and the address (including e-mail, telephone, and fax) to which correspondence should be sent.
The subject of the email should be "SAC2005 constraint track submission"

We strongly suggest to use for submission the available camera ready templates, and adhere to the 5 page limitation.

Registration is required for paper and poster inclusion in the Conference Proceedings, and for event attendance. (please see Registration Page)

Important Dates

The proposed schedule of important dates for the track is as follows:

Paper Submission deadline August 31, 2004
Notification of acceptance October 18, 2004
Camera-ready version deadline November 2, 2004
Track Dates March 13-17, 2005

Organising Committee

Stefano Bistarelli (Primary Contact)
Dipartimento di Scienze
Università degli studi "G. D'Annunzio" di Chieti-Pescara, Italy
Istituto di Informatica e Telematica
C.N.R. Pisa, Italy

Eric Monfroy
University of Nantes,France

Barry O'Sullivan
Cork Constraint Computation Centre
Department of Computer Science
University College Cork, Ireland

International Conference on Automated Planning and Scheduling
Monterey, California, June 5-10, 2005

The International Conference on Automated Planning & Scheduling (ICAPS) is the premier forum for researchers and practitioners in Intelligent Planning & Scheduling and related fields. Topics include all aspects of planning and scheduling theory and practice, including a wide spectrum of applications. The ICAPS 2005 main conference will be accompanied by a program of tutorials and workshops, a doctoral consortium, and demonstrations of planning and scheduling systems. As a novelty, the first International Competition on Knowledge Engineering for Planning will be held at the conference.

ICAPS 2005 will be take place in Monterey, California, U.S.A. between June 5 and 10 at the Hyatt Regency Monterey Resort and Conference Center

Upcoming Deadlines
Papers due on 15 November, 2004
Workshop proposals due on 1 October, 2004
Tutorial proposals due on 15 December, 2004

Software demos due on 21 March, 2005

International Symposium on Principles of Database Systems
Baltimore, Maryland, June 13-15, 2005

The symposium invites papers on fundamental aspects of data management. Original research papers on the theory, design, specification, or implementation of data management tools are solicited. Papers emphasizing new topics or foundations of emerging areas are especially welcome. The symposium will be held in Baltimore, in conjunction with the ACM SIGMOD International Conference on Management of Data (SIGMOD'05).
Suggested topics  include the following  (this list is  not exhaustive and the order does not reflect priorities):

  • Access Methods & Physical Design,
  • Active Databases,
  • Complexity & Performance Evaluation,
  • Data Integration & Interoperability,
  • Data Mining,
  • Data Models,
  • Data Stream Management,
  • Database Programming Languages,
  • Databases & Information Retrieval,
  • Databases & Workflows,
  • Deductive Databases & Knowledge Bases,
  • Distributed Databases,
  • Information Processing on the Web,
  • Logic in Databases,
  • Multimedia Databases,
  • Object-oriented Databases,
  • Query Languages,
  • Query Optimization,
  • Real-time Databases,
  • Security & Privacy,
  • Semistructured Data & XML,
  • Spatial & Temporal Databases,
  • Theory of recovery,
  • Transaction Management,
  • Views & Warehousing,
  • Web Services & Electronic Commerce,
  • XML Databases
All submissions must be done electronically. See webpage for details.
Important dates:
Paper abstracts due: December 1, 2004 (8:59pm PST)
Full papers due:
December 8, 2004 (8:59pm PST)
February 23, 2005
Camera-ready due: 
March 22, 2005