---

Contents

Vol 17 n. 4, November 2004

---

---

---

Editorial

Enrico Pontelli

---

---

---

ALP Elections

David Scott Warren

Editor: Enrico Pontelli

---

The ALP is administered by the ALP President and advised by the ALP Executive Committee.  The President is elected by the ALP membership for a term of two years, and the Executive Committee has seven members, each elected by the ALP membership for a term of four years. Every two years we hold an election to replace the members whose terms are expiring.  We will be holding elections within the next month.

The current ALP President is Veronica Dahl.  Our current Executive Committee members are:

• Bart Demoen
• Maurizio Gabbrielli
• Manuel Hermenegildo
• Vladimir Lifschitz
• Gopal Gupta
• Sandro Etalle
• Mirek Truszczynski
  

Veronica has been president for four years, the term limit imposed by our constitution, and will be stepping down.  We heartily thank her for her wonderful service to our community these past four years.

The terms of four Executive Committee members are ending, those of Bart Demoen, Maurizio Gabbrielli, Manuel Hermenegildo, and Vladimir Lifschitz.  We very much appreciate the time and work they have put in to support the ALP over their terms of service.

The ALP Elections subcommittee, consisting of Gopal Gupta, Sandro Etalle, and myself, with the advice of the full Executive Committee, have put together a slate of nominees to stand for election to the vacant positions.  The nominees are listed below, along with a link to a "position" statement each nominee has been asked to provide.  These statements should give you more information about each nominee and allow you to be a better informed elector.

Nominee for ALP President:

Manuel Hermenegildo
	URL: ?????

Nominees for the ALP Executive Committee:

Mireille Ducasse
	http://www.irisa.fr/lande/ducasse/alp-statement.html
Francois Fages
	http://contraintes.inria.fr/~fages/positionALP.html
John Gallagher
	http://www.ruc.dk/~jpg/alp_statement.html
Maria Garcia de la Banda
	http://www.csse.monash.edu.au/~mbanda/
Dale Miller
	http://www.lix.polytechnique.fr/Labo/Dale.Miller/alp-statement.html
Ilkka Niemela
	http://www.tcs.hut.fi/~ini/alp.html
Enrico Pontelli
	http://www.cs.nmsu.edu/~epontell/alpec
Kostis Sagonas
	http://user.it.uu.se/~kostis/ALP/position.shtml
Peter Szeredi
	http://www.cs.bme.hu/~szeredi/alp/
Francesca Toni
	http://www.doc.ic.ac.uk/~ft/ALP-statement.html

The election will be carried out through a website to be set up shortly.  You will be emailed the location of the website and a personal ID and password to use to login and vote.  We will be using the Australian preference voting system, so you will be able to rank the Executive Committee nominees in your order of preference.  The four most-preferred nominees will be elected to four-year terms.

We hope you will take the time to familiarize yourself with the nominees and then to go to the website and vote.

---

---

Summary of the Minutes of the ALP Plenary Meeting

David Scott Warren

Editor: Enrico Pontelli

---

The Plenary Meeting of the Association for Logic Programming took place on September 8th, 2004, during the 2004 International Conference on Logic Programming.
The following is a brief summary of the main points addressed during the meeting:

1. In the upcoming year, four members of the Executive Committee will complete their term. Elections are being planned. An Election Committee has been assembled, chaired by D.S. Warren.
2. Maurice Bruynooghe reported a number of interesting news regarding the Theory and Practice of Logic Programming journal. These include [ for more details, please see Maurice Bruynooghe's message in the Community News section of this newsletter ]
   
• TPLP has been incorporated in the ISI Science Citation Index, with an impact factor greater than one;
• TPLP's papers are openly accessible through the CoRR archive;
• currently, TPLP has a backlog of 3.5 issues for regular papers;
  
• starting in January 2006, TPLP will have a new Editor-in-Chief (Annalisa Bossi);
• a number of changes have occurred in the areas and in the area editors.
3. Gopal Gupta reported on the future sites for ICLP. ICLP 2005 (co-chaired by Maurizio Gabbrielli and Gopal Gupta) will take place in Barcelona, Spain (in early October 2005); ICLP 2006 will be part of the Federated Logic Conference (FLoC) in Seattle, WA. A call for proposals for sites for ICLP 2007 is expected to be issued soon.
4. Gopal Gupta reported also on the successful Summer School held in Dallas over the Summer 2004. A Summer School is planned for 2006; a subcommittee has been established to explore the organization of the school (including the possibility of organizing a summer school targeting high school girls).
   
5. The Executive Committee has discussed the approved uses of the ALP mailing list. The mailing list will be employed exclusively for the distribution of the Newsletter and for the Executive Committee elections. A decision was made to automatically add to the mailing list the participants to the ICLP conference.
   
6. Pat Hill reported on the financial status of the Association.
7. Enrico Pontelli reported on the status of the Newsletter, including the new initiative to publicize logic programming PhD dissertations.
   

---

---

Trust in Global Computing

Marco Carbone¹, Mogens Nielsen¹, Vladimiro Sassone^2
1BRICS, University of Aarhus
²Dept. of Informatics, University of Sussex

Editor: Frank Valencia

---

PDF Version of this article is available HERE.


1. Introduction
In this note we briefly summarise some work on formal models of trust in Global Computing scenarios, focusing on ideas reported in [1] and [2]. The work is part of IST-FET projects SECURE and MyThS.

A GC system is composed of entities which are autonomous, decentralised, mobile, dynamically configurable, and capable of operating under partial information. For such systems, as e.g. the Internet, traditional security mechanisms have severe limitations, as they are often either too weak to safeguard against the actual risks, or so stringent to impose unacceptable burdens on the effectiveness and flexibility of the infrastructure. Trust management systems, whereby safety critical decision are made based on trust policies and their deployment in the presence of partial knowledge, have been proposed as an alternative in the GC setting.

The idea is basically to transfer ideas of trust as a concept in human behaviour to GC scenarios. However, it is important to realize, that there are major differences between the informal notion of trust explored in the social sciences and the kind of formality needed for GC. GC models need in the end to be operational, so as to be implementable as part of GC systems. Also, as with all formal models, they should provide a formal understanding of how trust is formed from complex interactions between individuals, and support reasoning about properties of trust-based systems.

In our approach, we think of a trust management system as consisting of a “trust engine” and a “risk engine" coupled together as part of a “principal.” The trust engine is responsible for updating trust information based on direct and indirect observations or evidence, and to provide trust information to the risk engine as input to its procedures for handling requests. The risk engine will use the trust information in assessing the likelihood of various “outcomes” associated with the range of possible responses to requests, see [3] for more details. Abstracting over this point of view, we single out as central issues for our trust model the aspects of trust formation, evolution, and propagation. The latter is particularly important in our intended application domain, where the set of active principals is large and open-ended, and centralised trust and ad-hoc methods of propagation of its variations make little sense. An important propagation mechanism is referencing, whereby principals cooperate to implement complex, intertwined “global” trusting schemes.

In the following we briefly report on work towards a formal model for declarative trust policy languages with referencing [1], and some work towards an operational trust model in the form of a process calculus for trust management [2].

2. A Computational Trust Model
Principals form a set P ranged over by a, b, c, . . . and p. We assume an abstract set T of trust values whose elements represent degrees of trust. These can be simple values, such as {trusted, distrusted}, or also structured values, e.g. pairs where the first element represents an action, say access a file, and the second a trust level associated to that action. As pointed out in the introduction, we model principals’ mutual trust as a function which associates to each pair of principals a trust value t in T:

Function m applied to a and then to b returns the trust value expressing a's trust in b. Note, however, that in a GC scenario a's trust values may depend on other principals' trust. For instance, a may wish to enforce that its trust in c is dependent on b's trust in c. This mechanism of relying on third-party assessments, known as referencing, is fundamental in all scenarios involving cooperation, including computational paradigms such as GC.

So, we refine our view of a principal's trust, assuming that principal defines its trust with a policy. According to such a view, each principal has a local policy which contributes to form the global trust m. A policy expresses how the principal computes trust information given not just his own beliefs (experience), but also other principals' beliefs. It follows that a's policy has the type below, whose first argument represents the knowledge of third principals' policies that a needs to evaluate (in [1] we introduce a relevant example of language for describing policies).

By collecting together the individual policies, we obtain a function whose type is (isomorphic to)

To interpret this collection of mutually recursive local policies as a global trust function m, we assume T to be equipped with a complete partial order and taking to be continuous, we define the global trust as , the least fixpoint of .

Now the question is how to choose . We maintain that it cannot be the order which measures the degree of trust. Let T be the CPO , and consider a policy which refers to b the degree of trust to assign to c. In this setup, a will assign low trust to c when it is not able to gather information about c from b. This however would be an erroneous conclusion, as the interruption in the flow of information does not bear any final meaning about trust, its most likely cause being a transient network delay that will soon be resolved. The right conclusion for a to draw is not to distrust c, but to acknowledge that it does not know (yet) whether or not to trust c. In other words, if we want to model dynamic networks, we cannot allow confusion between ``don't trust'' and ``don't know'' the latter only means lack of evidence for trust or distrust, the former implies a trust-based, possibly irreversible decision. We thus consider approximate trust values which embody a level of uncertainty as to which value we are actually presented with. Specifically, beside the usual trust value ordering, we equip trust values with a trust information ordering. While the former measures the degree of trustworthiness, the latter measures the degree of uncertainty present in our trust information, that is its information content. We will assume that the set T of (approximations of) trust values is a CPO with an ordering relation . Then means that t' ``refines'' t, by providing more information than t about what trust value is being approximated. With this understanding the continuity of is a very intuitive assumption: it asserts that the better determined the information from the other principals, the better determined is value returned by the policy.

Having pointed out the need for trust structures equipped at the same time with an information and a trust ordering, we focus on the triples , which we call trust structures. Preliminary investigations of general properties of such structures can be found in [5]. Here we illustrate a particular generic way of constructing such structures from lattices of trust values, and some of its useful properties.

When defining a trust management system, it is natural to start off with a set D of trust values, or degrees. On top of that, we are likely to need ways to compare and combine elements of D so as to form, say, a degree which comprehends a given set of trust values, or represents the trust level common to several principals. This amounts to start with a complete lattice , where those combinators can be considered as taking lubs or glbs of sets of values. To account for uncertainty, we define an operator I to extend a lattice to a trust structure . The set T consists of the set of intervals over D which, besides containing a precise image of D--viz. the singletons--represent naturally the notion of approximation, or uncertainty about elements of D.

Given a complete lattice and nonempty subsets we say that if and only if and [7]. Clearly, is not a partial order on the subsets of D, as the antisymmetry law fails. We get a partial order by considering as usual the equivalence classes of . It turns out that the intervals over D are a set of representatives of such classes.

From [1] we have that the lattice structure on is lifted to a lattice structure on intervals, i.e. is a complete lattice.

At same time, we can define an ordering on intervals which reflects their information contents: as the interval [d₀, d₁] expresses a value between d₀ and d₁, the width of the interval represents the uncertainty. This leads directly to the following definition.

As for the previous ordering, we have that [1] is a CPO.

Example 1 (Intervals in [0,1]). Let R stand for the set of reals between 0 and 1, which is a complete lattice with the usual ordering , and let us consider the set I(R) of intervals in R. It follows from the previous results that is a complete lattice and is a complete partial order. The trust domain so obtained is particularly interesting, as it allows us to express complex policies. In particular, it is related to the uncertainty logic [4], where an interval [d₀, d₁] in I(R) is seen as a pair of numbers where d₀ is called belief and 1 - d₁ disbelief. A a formal comparison with Josang's logic is currently under investigation

We conclude this section by noticing that the trust structures defined above enjoy a number of nice properties, e.g. the relation is continuous with respect to and, conversely, relation is continuous with respect to [1]. Furthermore, continuity of operators on lifts to continuity on , and a number of useful theorems can be proven relating the trust and the information ordering, including theorems showing the correctness of certain protocols for ``proof carrying requests''.

3. An Operational Trust Model
In order to focus on the operational mechanisms of trust evolution and propagation in a distributed setting, in [2] we introduce a calculus for trust management where principals' behaviour is accounted for. The approach is in the style of process algebras. Each principal is identified by a triple , where a is the principal's name, P the behaviour which models its actions, and its trust policy, described in a logical language such as datalog. The dynamics of the calculus consists of interactions between principals, as for instance in:

Such interactions are granted according to the involved principals' policies, i.e. is a predicate which must be satisfied by policy in order for communication to happen. Any message received implies an update of the policy, done by using the update function upd(). The overall idea here is that policy updates are informed during a's evolution in time by its history of (un)successful interactions with other principals.

Our current work on such extended framework attempts to capture the evolutionary aspects of trust in dynamic networks, together with the study of properties and related analysis techniques of systems based on trust in such networks. In [2] we define equivalence relations for comparing policies, behaviour principals and networks of principals. In an example we show how it is possible to get two kind of networks (web of trust) and associate one network the specification of the problem (done in a classical centralized way) and the other network to a possible implementation as a way of proving that the latter is correct and sound with respect to a specific property.

Conclusion
The models introduced above build on basic ideas from trust management systems and relies on domain theory to provide a semantic model for the interpretation of trust policies in trust-based security systems. This is not the end of the story, and there are still many issues to be faced in the area. We remark that the interval construction illustrated here can be understood in abstract (categorical) terms, as done in [5]. Moreover in [8], intervals are substituted by a more pragmatical model, i.e. event structures. The problem of implementing distributed computations of the least fix-point has been studied in [6] which provides a distributed algorithm for computing efficiently a partial global trust function, indipendetly by the set T adopted. Finally, we have also investigated ways for expressing and studying security properties of systems based on dynamic trust evolution and propagation, such as those above. Among the many approaches to checking of security properties, behavioural equivalences are particularly appealing. A valid alternative could be designing a logic for expressing trust related behavioural properties of principals.

Bibliography

[1]  M. Carbone, M. Nielsen, and V. Sassone. A formal model for trust in dynamic networks. In Proc of SEFM, pages 54-61, IEEE Computer Society Press, 2003.

[2]  M. Carbone, M. Nielsen, and V. Sassone.
A calculus for trust management.
To appear in Proc. of FSTTCS, 2004.

[3]  V. Cahill et al.
Using trust for secure collaboration in uncertain environment.
IEEE Pervasive Computing Journal, 2003.

[4]  A. Josang.
A logic for uncertain probabilities.
Fuzziness and Knowledge-Based Systems, 9(3), 2001.

[5]  K. Krukow.
On foundations for dynamic trust management.
Unpublished PhD Progress Report, available at: http://www.brics.dk/~krukow/, 2004.

[6]  K. Krukow and A. Twigg.
Distributed approximation of fixed-points in trust structures.
Technical Report RS-04-16, BRICS, University of Århus, September 2004.

[7]  U. W. Kulish and W. L. Miranker.
Computer Arithmetic in Theory and Practice.
Academic Press, 1981.

[8]  M. Nielsen and K. Krukow.
On the formal modelling of trust in reputation-based systems.
In J. Karhumäki, H. Maurer, G. Paun, and G. Rozenberg, editors, Theory Is Forever: Essays Dedicated to Arto Salomaa, volume 3113, pages 192-204. Springer Verlag, 2004.

---

---

Report on the CICLOPS 2004 CoLogNET Workshop

Manuel Carro and Jose F. Morales
Technical University of Madrid

Editor: Enrico Pontelli

---

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

CICLOPS 2004 and ICLP 2004
The CICLOPS 2004 workshop was held in St.-Malo, France, as a workshop associated to the International Conference on Logic Programming, ICLP 2004, and under the sponsorship of the Computational Logic Network, CoLogNET.

From a CoLogNET point of view, CICLOPS 2004 closed a tour which drove the CoLogNet-sponsored implementation workshops through SAS and LOPSTR (Madrid, 2002) and Formal Methods (Pisa, 2003), all of which were very rewarding experiences.

Outline of the Workshop
Researchers and practitioners interested in the implementation of constraint and logic systems were invited to submit papers to CICLOPS and to get together in a friendly ambient.  The program committee decided to discard some of the submitted papers, despite their quality.

Seven regular talks and an invited speaker filled in interesting sessions which were attended by a reputedly very knowledgeable and relevant audience, where opinions to sparkled.  A final open session was held, in which, besides retaking some of the topics presented during the talk, the discussion drifted towards more general issues in Logic Programming.  The discussion session can perhaps be summarized as ``What should the next step in logic programming language design and implementation be?''.

We will give a short account of the talks delivered, starting by the invited one.


K. Shen (IC-Park, London) gave the invited talk, entitled On Benchmarking Constraint Logic Programming Platforms.  He made a tour de force through several flaws and incoherences to be avoided when benchmarking complex programming systems such as constraint logic platforms, in a broad sense.  It was full of enlightening examples taken from real-life experience which vividly show how careful should one be when trying to measure the effectiveness of such complex systems.  The talk was in fact very much enjoyed by all of the audience.

E. Pontelli gave the talk entitled Towards a CLP System for Reasoning about Answer Sets, coauthored by himself, O. Elkhatib, and T. Cao Son.  The aim of this work is to devise a framework to allow Prolog and Answer Set systems to interact (à la foreign language interface, but trying to respect the declarative semantics as much as possible), so that every language is enriched with the capabilities of the other.

N. Angelopoulos  (On the implementation of MCMC proposals over Stochastic Logic Programs}, coauthored with J. Cussens) presented a design proposal for the implementation of logic programs where predicate clauses have a probability distribution.

P. Tarau described in the paper Orthogonal Language Constructs for Agent Oriented Logic Programming the set of tools available within the Jinni logic programming system to write agents able to react to the environment and to easily communicate with the final user.  This trip lead from object-oriented LP, featuring inheritance, to the creation of independent computations as first-order citizens, and to a set of facilities to connect and exchange data with external entities.

F. Drejhammar presented the work Implementation Strategies for Single Assignment Variables, written jointly with C. Schulte.  He introduced the Flow Java language, which features constrained, single-assignment variables in a concurrent setting, and the paper examines different implementation strategies to efficiently support aliasing, monotonicity, and synchronization.

J.J. Cook presented the paper Optimising P#: Translating Prolog to More Idiomatic C#, in which he introduced a new version of his Prolog to C# compiler.  The innovation introduced is trying to generate a C# code which would be compiled more efficiently by (current) C# compilers, trying to perform a smarter variable liveness analysis and also trying to generate code which performs last call optimization in more cases than it was possible before.

M. Ferreira gave the talk Comparing Alternative Approaches for Coupling Logic Programming with Relational Databases, a joint work with R. Rocha and S. Silva.  He
described and evaluated different interfaces, at several levels, to make the communication between a relational database and a Prolog system possible.  These approaches have been tested using the YAP Prolog system.

P. Tarau presented A Logic Programming Framework for Semantic Interpretation with WordNet and PageRank, coauthored with R. Mihalcea and E. Figa.  The paper examined the application of the PageRank ranking algorithm, of Google's fame, to the disambiguation of natural language sentences.  The prototype is mainly written in Jinni (a Prolog's variant), with some parts developed in Java.

Registration for and attendance to the workshop was in the line of other workshops simultaneously held at ICLP 2004 (and notably higher than some of them).  The relaxed ambient fostered the formulation of relevant questions which eventually derived into interesting discussions, especially in the last session.

Further Information
Information about the CICLOPS 2004 workshop, along with the accepted papers, can be found at the workshop web site, and information about the series of workshops can be found at CoLogNET ITCLS Workshop homepage.  ITCLS 2003 was organized by Manuel Carro (UPM) and José F. Morales (UPM). The program committee included, additionally:

Ricardo Lopes	Universidade do Porto (Portugal)
Enrico Pontelli	New Mexico State University (USA)
Vítor Santos Costa	Universidade Federal do Rio de Janeiro (Brazil)
Tom Schrijvers	Katholieke Universiteit Leuven (Belgium)
Christian Schulte	Royal Institute of Technology (Sweden)
Paul Tarau	University of North Texas (USA)
Neng-Fa Zhou	The City University of New York (USA)

Besides the WWW-based repository, all the papers accepted at the workshop are collected in a 96-page volume which was handed to the people who registered for the workshop.  The proceedings were published by the Computer Science School of the Technical University of Madrid (UPM) as a Technical Report.

The workshop organizers want to thank the organization of ICLP 2004 for the facilities given for the celebration of the workshop, and also the following institutions for their support:

• Computational Logic Network (CoLogNET)
• Association for Logic Programming (ALP)
• Computer Science School of the T. U. Madrid (FI-UPM)
• Technical University of Madrid (UPM)
• Institut National de Recherche en Informatique et en Automatique
  

---

---

The 10th Prolog Programming Contest

Tom Schrijvers and Remko Troncon

---

The 10th Prolog Programming contest was organised at the occasion of the 20th ICLP conference. In total, 10 teams participated on site at the Palais du Grand Large in Saint-Malo, while 8 teams participated in the parallel web contest. The object of the contest was to solve as many of the 5 problems as possible in a limited amount of time, using one of the major open-source Prolog systems.

The winning team of the Prolog Programming Contest was:

• Bart Demoen
• Kostis Sagonas
• Peter Stuckey

who used SWI-Prolog to solve 3 questions correctly. Congratulations to the past Prolog Programming Contest organiser and his team (who are no newcomers in winning the contest).

The winning team of the 2004 Prolog Programming Web Contest was:

• Pierre Alexandre Favier
• Jean Michel Leconte

who used GNU Prolog. Congratulations to the team that not only managed to solve all questions, but also produce the shortest solution to the Turtle problem.

Full details, including pictures taken during the contest, are available on the contest website.

Thanks to all teams for participating in the contest, and we hope to see you again next year for more Prolog Programming Fun!

the organisers,
Tom Schrijvers & Remko Tronçon

---

---

International Conference on Logic Programming:
an Informal Travel Report

Editor: Enrico Pontelli

---

The 20th International Conference on Logic Programming (ICLP) took place on Sept. 6-10, 2004. The selected location for this annual event was Saint-Malo, France. Saint-Malo is a nice town on the north coast of France, with beautiful beaches and a gorgeous town center full of history (and good restaurants... ).
Reaching Saint-Malo turned out to be a very interesting experience in itself. Trusting my ever creative travel agent, I secured a flight all the way to Saint-Malo. Little I know, I had the pleasure of making a flight connection on the island of Guernsey (beautiful Channel island), along with the new experience of being the only passenger on a plane.
The conference site was a nice meeting facility (Palais du Grand Large -- it's the building to the left of the old city walls in the picture). Upon arrival in Saint-Malo, I immediately felt at home -- there were logic programmers walking around everywhere . Seriously, it was nice to meet all the good old friends.
The conference opened on Monday morning. Mireille Ducassè, the General Chair of ICLP 2004, offered a wealth of information about the organization and the activities associated to the conference. Following, Bart Demoen and Vladimir Lifschitz provided an overview of the conference program and of the selected papers. The conference program included:
Regular Papers Sessions -- organized by topics (Analysis, Constraints, Alternative Paradigms, Implementations, Answer Set Programming)
Invited Talks -- by Gerard Huet, Michael Gelfond, Nachum Dershowitz
Tutorials -- by Illka Niemela, Guillermo Simari, and Andreas Podelski (the last one unfortunately canceled)
Posters.
The first event of the conference was the invited talk by Gerard Huet; Gerard wore his professor's hat and led the audience in an adventure about non-determinism and Sanskrit. The presentation was entertaining and interesting -- leaving also the realm of logic programming and crossing into other declarative frameworks.
The rest of the morning was dedicated to the session on Analysis, with presentations by J. Gallagher, Jan Smaus, and Alexander Serebrenik.
The lunch, each day of the conference, was organized by the conference and took place in a dining room of the conference center, with a gorgeous view of the beach and the sea.
Monday's afternoon session was dedicated to Constraint Programming, with presentations by Enrico, Peter Stuckey, Gregory Duck, and Tom Schrijvers. Particularly interesting the work by Tom and David Warren - exploring the combination of CHR and XSB - which received the ICLP 2004 Best Paper Award.
The first day of the conference closed with the long awaited Prolog Programming Contest. The contest had been organized by Tom Schrijvers and Remko Troncon - and they an outstanding job. 10 teams competed, under a format slightly different than usual. Teams were expected to provide their own computers and no feedback was provided upon submission of the solutions. These added some additional thrills to the event - e.g., I had the opportunity to work on a borrowed laptop with French keyboard, which made writing Prolog code really fun
Please see the contest report from Tom and Remko in this issue of the newsletter.
Tuesday opened with a tutorial from Ilkka Niemela, dedicated to foundations and implementations of Answer Set Programming. I truly enjoyed this tutorial, presented with enthusiasm and just at the right level for everyone in the audience.
The rest of the morning was dedicated to the session on Alternative Paradigms.
After lunch, I skipped the Implementation session to attend the nice first session of the combined MultiCLP and WLPE workshop. This session included a very interesting invited talk by David S. Warren.
The rest of the afternoon was dedicated to the poster session. In parallel with the poster session, an interesting event took place: Daniel Cabeza (from UPM Madrid) successfully defended his PhD dissertation. Congratulations Dr. Cabeza Gras!!
The day closed with the conference banquet. In parallel with good food and good wine, we enjoyed an entertaining keynote presentation by Herve Gallaire (a nice historical perspective on logic programming), the award ceremony, and a plethora of traditional dances. The award ceremony was particularly exciting. Along with the "usual" awards - best paper award, to Tom Schrijvers and David S. Warren, and the programming contest awards - the team composed of Peter Stuckey, Kostis Sagonas, and Bart Demoen - the ALP assigned awards to some of the most representative papers published in the last 20 years - the receipients that were present at the event included Jean-Louis Lassez, Michael Gelfond, and Vladimir Lifschitz.

Wednesday morning started with the invited talk by Michael Gelfond - focused on the use of Answer Set Programming in the development of intelligent agents (with very interesting references to the use of ASP in the diagnosis of systems of the Space Shuttle).
While the main conference continued in the morning with the first session on Answer Set Programming, I moved next door to attend the CICLOP workshop. The workshop opened with a very interesting invited talk by Kish Shen, dedicated to the problem of benchmarking CLP systems (a very thought-provoking talk). The workshop continued throughout the day, with various talks on implementation of ASP, Stochastic Logic Programs, Agent-oriented languages, compilation techniques, database interfaces, and compilers to C#.
The day closed with the ALP General Assembly (please see the extract from the minutes of the meeting, in this issue of the newsletter).
And this was all for my trip to ICLP 2004. I had to miss the last day (call of duty - had to come back and teach...), but I left Saint-Malo with a great experience and new ideas.

---

---

The Early Days of Prolog in Hungary - a personal account

Peter Szeredi
Budapest University of Technology and Economics
http://www.cs.bme.hu/~szeredi/english

Editor: Enrico Pontelli

---

Below is a somewhat lengthy letter written around 1992 to Peter Van Roy, when he asked me for material for his JLP paper on Prolog implementations [PVR1994].


Background
In early seventies there was no specialised computer science education at the Hungarian universities. The demand for computer specialists was mostly covered by employing people who graduated in mathematics or engineering.

I graduated in 1972 as a mathematician, my thesis was in mathematical logic.  I had also been programming computers for six years by that time.

My first encounter with computers and programming was in 1966 when I was 17. I was quite lucky to find a place, the Computer Center of the Ministry of Heavy Industries (NIM IGÜSZI), where I got a friendly reception and given access to computers. I worked there part-time during my studies and had done quite a bit of hacking in systems programming. I also was active in the Algol 68 group: we first translated the Algol 68 report to Hungarian and then started to work on an Algol 68 implementation (which has never been finished). [A sidetrack: during implementation I managed to discover an inconsistency in the type (mode) system of Algol 68 which was later named "incestuous unions".]

I joined (full time) the software department at NIM IGÜSZI in 1972. I worked in a group producing various system programs for a new Hungarian computer.  For our development work we used a relatively unknown language CDL (Compiler Definition Language) designed by C. H. A. Koster of Nijmegen University.  We got acquainted with Koster through our work on Algol 68 as he was one of the authors of the Algol 68 report. Koster invented a variant of van Wijngaarden's two level grammars called affix grammars, and designed a language based on this type of grammar, which was CDL.

Here is a piece of code in CDL:


If you replace the affixes (+id) with parenthesised arguments, delete the local variable declaration (-n1) and replace the ':' with ':-' you get exactly Edinburgh Prolog notation (all this in 1970/71, some two years before Prolog and six years before the Edinburgh notation was invented). Of course, CDL is an imperative language, with destructive assignment, and also there is no backtracking, but otherwise the notation and the control is surprisingly similar to that of Prolog.

CDL is actually an open ended language, i.e. it lacks any primitive operations. These (such as the equal, make, subtr, ...  operations above) have to be supplied in the target language (most of the time the assembly language of the target computer, or sometimes a higher level language, such as C). CDL is thus more like a recursive macro language.

In early seventies computerisation was one of the buzzwords in Hungary, and there was quite a bit of government money for R&D work in computer software.  From this money another group at NIM IGÜSZI (the "Logic in Computer Science" group), led by István Németi, got a grant for developing an interactive, semi-automatic verification system for a simple algorithmic language. The verification system contained a structure sharing Boyer-Moore type theorem prover. We managed to convince Németi's group to use CDL as the implementation language. Because of this, and also because of my earlier interest in logic I myself got interested in this work.  I remember looking at the theorem prover working on small theorems in algebra, and realising that it wasn't able to go much beyond toy problems.

Besides program verification, Németi's group was interested in all kinds of interactions between logic and computer science. A particular goal of theirs was to study and develop logic based declarative programming languages such as Prolog. They had seminars on declarative programming languages (e.g. on logic programming) during 1973 and they corresponded with the department of Computational Logic in Edinburgh which led to Németi's visiting Edinburgh in 1974.

The first Hungarian Prolog
Németi had research contacts in Edinburgh and visited Scotland several times.  From there he brought the news and some papers about a theorem prover (?) called Prolog. I was quite taken aback by the fact that there was a theorem prover that could do something useful: calculate the factorial of a number!  Németi brought the Marseille interpreter as a deck of cards from Edinburgh together with a brief description of built-ins (on a line printer listing) entitled Epilog[400,400] and copies of slides of David Warren's talk entitled "What is Prolog?".

Porting of the Marseille Fortran interpreter to the ICL 1903A computer of NIM IGÜSZI was included into our research contract for 1975. A member of Németi's group, Péter Tóth, who was given this task, encountered unexpected problems due to the different word and character size (ICL 1900 had 24 bit words and 6 bit characters). While he was struggling with the porting, I decided to try to write my own Prolog interpreter in CDL. I actually had never had a look at the Marseille Prolog itself, I based the implementation on the last three slides of David Warren's above mentioned talk, entitled 'Example to illustrate how Prolog is implemented'. This showed three snapshots in the execution of the (naive) rev(a.b.X, a.b.X) goal. The structure of the (single) stack was quite apparent from these slides, and this, together with my earlier encounter with a structure sharing unification algorithm was enough to get me started. CDL proved to be a very convenient implementation tool, especially suited for parsing, so the tokeniser and parser were written in CDL, rather than in Prolog (as was the case for the Marseille interpreter).

I succeeded in producing a working Prolog interpreter in a few weeks, just in time for the usual yearly out of town gathering of NIM IGÜSZI software developers where Prolog was the main topic that year. The availability of a working interpreter gave a big boost to that meeting. Several people got rather excited about Prolog, including Ferenc Darvas who worked on projects for drug-industry, Iván Futó, who worked in simulation, Zsuzsa Márkusz, an architect, Miklós Szõts, a civil engineer turned computer scientist.  (Both Zsuzsa Márkusz and Miklós Szõts were students of Németi.) In a few weeks after the meeting Miklós Szõts produced the very first application of the Hungarian Prolog: a program for planning of a one level workshop building using prefabricated panels. Ferenc Darvas also came back with a number of application proposals, where he believed Prolog to be of good use, such as predicting drug interactions and various other programs in drug design.

Very active months and years followed, with various applications projects going on, which demanded various language extensions, ports to other computers, debugging facilities, etc. Through this fruitful interaction between implementors and application developers the Prolog interpreter grew from a toy to a usable system.

This system (which is often confused with MProlog, the second Hungarian Prolog, see later) had no name in itself. It used the Marseille syntax, but the built-ins had English names (although some, which could pass as English, at least for me, remained the same as in the Marseille Prolog, e.g. univ, egalf, etc.). Here is an example:


It was a batch-oriented system, as most of the computers in Hungary at that time were mainframes without interactive access. It provided a selective exhaustive trace and backtrace services. It had a number of new built-ins over the Marseille functionality, such as undoable input and undoable database predicates.

Undoable input was implemented using a a circular buffer in the tokeniser to store the tokens read in. Token and term input predicates trailed the value of the current token pointer of this circular input buffer before the actual input was made. If such an input predicate was backtracked over, its side effect was undone by moving the current token pointer back to its original position (of course, this backtracking capability was limited by the size of the buffer). Subsequent input predicates read the tokens from the buffer, and switched back to ``real'' input only when the sequence of unread tokens was exhausted.

The second half of seventies there was thus a boom for Prolog in Hungary. Several pilot application projects were started, mostly with the help of government grants, though. The Prolog was ported to the Siemens BS2000 computer, the first widely used interactive implementation.

[You asked for anecdotes, so here is one. One of the first, very popular, interactive demo programs (written by my younger brother János) was a Hungarian natural language question-answer system, which could parse and remember simple facts and rules about people and itself (the program) and answer questions about these. It rejected statements from which one could deduce some negative fact about the program itself.  E.g. after the rule 'If one is nice, he is stupid' had been entered, it refused to accept the statement 'You are nice', and actually gave an explanation why. One night a big shout was heard at the terminal room, where two students were playing with this program: I managed to tell the computer that he is stupid - shouted one of them - simply by spelling it stoopid (it is even easier to misspell the Hungarian equivalent of stupid).]

The Hungarian Prolog arouse the interest of LP researchers fairly soon. I've dug up a letter from David Warren dated February 1976, and from Bob Kowalski dated July 1976 in which they inquire about our Prolog. Bob Kowalski actually visited us for a few days on his way back from vacation in Poland in the summer of 1976. David Warren came in June 1977 for a two-week visit.  [It turned out at that time that David was influenced in his design of the Edinburgh syntax by his earlier work in Algol 68, thus explaining similarities with CDL.]  In 1978 there was symposium on Logic in Programming in Salgótarján, with several logic programmers present. In 1980 the Logic Programming Workshop was held in Debrecen.

Unfortunately by the end of seventies the steam started to run out for Prolog applications in Hungary. The biggest problem was the price of computer time.  To run Prolog one needed to purchase computer time on one of the big western made mainframes, and this was much more expensive than employing people to do the same task by hand (the labour price being much more cheap than in the West). Thus in Hungary, in late seventies, natural intelligence proved to be much cheaper than the artificial one.

MProlog - the second Hungarian Prolog
Catching the last wave of big government grants for software, the development of a new Prolog implementation was started in 1978. This implementation, later called MProlog, was based on the three stack Warren model of 1977. It was written in CDL2, a successor to CDL.

The MProlog system offered two paths for program execution. During development, the Program Development SubSystem (PDSS) provided an interactive environment for writing and testing programs. For application delivery the Production System was offered, which used the traditional translate-link-execute model.

PDSS was a comprehensive environment for the development of MProlog programs providing support for program entry, editing, execution, tracing, saving, etc.  PDSS was implemented in MProlog itself. For the programs entered, the system retained the source (without layout), including variable names. PDSS stored  the program as a syntax-tree, which was always presented to the user in a standard, pretty-printed format.

In the Production System MProlog source modules were first converted into a compact internal format using the pretranslator. The translation process included syntactic and semantic analysis (such as variable classification), and produced a binary module containing Prolog code in a format suitable for interpretation or further compilation.  Pretranslated modules could be linked---in MProlog terminology, consolidated---into an executable program by the consolidator program.  The Consolidator also had the capability of consolidating several binary modules into a single new binary module. MProlog also has a native code compiler for certain architectures (IBM 370, M68000, VAX, Intel 386), as well as a byte-code compiler. The compiler transformed a pretranslated module to a compiled module, with the resulting module also amenable to consolidation.  The compiler encompassed a number of important improvements over the original structure sharing compiler model, including techniques similar to those used in the WAM.

The binary program resulting from consolidation was executed by the interpreter. Unlike some other Prolog implementations, in MProlog the interpreter was the core of the system. It was written in CDL2 and in addition to interpretation proper, it served as the run-time system (i.e. memory management, etc.) for the compiled code.

MProlog extended the usual Edinburgh Prolog language in a number of respects. It had a (name based) module concept, user-controlled multi-level indexing, exception handling, a rich set of built-ins, including the undoable ones inherited from the first Hungarian Prolog. For more details on MProlog, see [Far1994].
  
Although the development of MProlog was started at NIM IGÜSZI, most of the people involved gradually moved to SZKI, a big computer company set up a
few years before. I myself moved to the Theoretical Laboratory, the department responsible for advanced research within SZKI in 1979. This Lab was led by Bálint Dömölki, who helped a lot in keeping the logic programming R&D alive. In SZKI I met Péter Köves and Zsuzsa Farkas, who, in the following years were leading the development of various sub-projects for MProlog. All in all, SZKI provided an environment much more appreciative than NIM IGÜSZI for the results achieved.

MProlog was being developed on the Siemens machine of SZKI. It was demonstrated at the Debrecen workshop in June 1980, using a terminal connected to the mainframe in Budapest. The Hungarian-made terminal was very awkward to handle, one had to enter each message off-line, surroundedwith special control characters showing which part of the screen to transmit, and then press a special 'send' button to do the actual transmission. As I recall, only Lew Baxter from Canada was brave enough to tackle this terminal, successfully running his version of the who-owns-the-zebra (five houses) puzzle.  Strangely enough, four years later he was recruited as the main Prolog expert for Logicware, the company set up in Toronto to market MProlog in North America.

The announcement of the Japanese Fifth Generation Project gave a big boost to the MProlog work. It was decided that MProlog will be made into a product marketed in the West. A user documentation was produced in English. One of the problems characteristic of the contemporary Hungarian environment was that it was very difficult to find a way of printing it out on a printer capable of producing lower case letters.

MProlog was ported to IBM CMS in 1981 and to VAX VMS in 1982. A problem with the latter port was that officially there were no VAXes in Hungary due to COCOM restrictions. In reality there were a few ones smuggled in, but they were very difficult to access. The initial, partly successful port to VAX was done at Nijmegen. Later we managed to get some limited access to a VAX in Hungary. Epsilon GmbH in West Berlin, formed from the developers of CDL2 also helped a lot by porting MProlog to computers not available in Hungary.

The first sale of MProlog was in September 1982, in France. In the subsequent years a number of European sales followed, in part through Epsilon. In 1983 a Japanese distributor was appointed and, after a version supporting Japanese characters was developed, several copies of the system were sold.

In early 1984 a Hungarian born Canadian entrepreneur established a company named Logicware to market MProlog in North America. The main goal of Logicware was to enter Prolog into the data processing departments of big companies.  MProlog had the advantage of being available on mainframes as well as minicomputers, workstations and PCs. Logicware management decided that the biggest obstacle in widespread acceptance of (M)Prolog was the inappropriateness of the terminology and notation, as well as the lack of educational tools.  Therefore big efforts went into redesigning the terminology and the language. For example the term 'clause' was replaced by the term 'statement', 'predicate' by 'definition', 'term' by 'expression', the new terms being thought to be more acceptable for data processing people. The built-in predicates were re-structured, and the names changed according to the new terminology. E.g. the predicate 'clause' became 'matching_statement' where the word 'matching' indicated that the built-in enumerated its multiple solutions on backtracking.

A group previously working on CDL2 itself, led by Tamás Langer joined SZKI late 1983. In its height there were about 15 people working full time on MProlog.

We switched from using the CDL2 compiler to the CDL2 Lab, a sophisticated program development environment.  The Lab, with its powerful inter-module code-generation scheme, helped a lot in efficient porting of MProlog to a wide range of architectures.

A new version of the compiler was designed and implemented. The first version of the compiler, which was a fairly straightforward adaptation of the Warren 1977 compiler was not really successful, as the code was only 5-7 times faster than the (fast) interpreted one (and speedups were even worse if lots of built-ins were invoked). The new compiler had various features taken over from the WAM as well as further extensions, some of which are described in a paper in the proceedings of the workshop on Implementations of Logic Programming Systems of ICLP93.

A special 16-bit version of MProlog was designed and implemented on IBM PCs. With the appearance of 386 processors a 32-bit version was also ported to the PC.  Further ports included workstations (e.g. SUN), Macintosh, IBM MVS, etc.

Significant effort was spent on tuning MProlog. The most often used code in the interpreter was rewritten to assembly language of the target computer, resulting in a fairly fast interpreter. In mid 1980-s even a special piece of hardware was designed and prototyped, to support efficient execution of MProlog (but this experiment did not go any further than the prototype).

The PDSS went through several stages of development gradually achieving the functionality outlined above. Various extensions, user interface tools were also developed.

A tutorial supported by an appropriate educational software tool was also produced.

In addition to MProlog development work, efforts were made to produce libraries, tools, and concrete applications of MProlog.

Unfortunately the business plans of Logicware didn't materialise, and the company gradually went out of business. SZKI continued the maintenance and support of MProlog with the help of European distributors in Germany and Italy.

In 1990 a new company, named IQSOFT, has been formed from the Theoretical Lab of SZKI. IQSOFT maintained and used MProlog in early 1990-s, but mostly for internal purposes.

Other Hungarian Prolog implementations
Iván Futó and his group developed an extension of the first Hungarian Prolog, called T-Prolog, for discrete simulation purposes. One of the interesting features of T-Prolog was its coroutining control, which was initially implemented using (double) interpretation. In MProlog special built-ins for handling continuations were included, and a T-Prolog implementation avoiding double interpretation was constructed. In mid-eighties an independent Prolog implementation, called CS-Prolog, was developed by Futó's group.

The line of T-Prolog, CS-Prolog etc. languages is described in  detail in Futó's invited talk at ICLP93 [Fut1993].


References

[Far1994] Zs. Farkas., P. Köves, P. Szeredi: MProlog: an Implementation Overview. In Evan Tick and Giancarlo Succi (editors): Implementations of Logic Programming Systems. Kluwer Academic Publishers, 1994, 103-117

[Fut1993] I. Futó: Prolog with Communicating Processes: From T-Prolog to CSR-Prolog (Invited paper), In: D. S. Warren (Ed.): Logic Programming, Proceedings of the Tenth International Conference on Logic Programming, MIT Press, 3-17.

[PVR1994] P. Van Roy: 1983-1993: The Wonder Years of Sequential Prolog Implementation. Journal of  Logic Programming 19/20: 385-441 (1994)

---

---

The History Page of the Association of Logic Programming

Robert A. Kowalski
Imperial College

Communicated by: Bart Demoen

---

Note of the Editor: the History page of the ALP has just been recently added to the ALP Web Site. Here below I am reproducing it to draw your attention. Please keep an eye on the official page in the ALP site for possible future additions.

The ALP was founded in 1986 at the 3rd ICLP conference, held at Imperial College. One of its main purposes was to oversee the profits of the London meeting and to organise future meetings of ICLP. However, it was also sparked by the appearance of another logic programming group in North America. This group, which organised the IEEE Symposium on Logic Programming (SLP) at Atlantic City in 1984 and Boston in 1985, was formed in response to the Japanese Fifth Generation Computer Systems Project.

The announcement of the FGCS Project in 1981 triggered reactions all over the world. It gave rise to the Alvey Programme in the UK, to the joint research institute ECRC in Munich and to a similar institute MCC in Austin Texas. It may even have been one of the main triggers for the European Union research programme, ESPRIT.

Logic Programming was virtually unknown in mainstream Computing at the time, and most of its research activity was in Europe. So it came as a big shock - nowhere more so than in North America - when it eventually became obvious that logic programming was to play a central, unifying role in the FGCS Project.

There had already been a number of workshops, most notably at Imperial College in 1976, Debrecen Hungary in 1980, Syracuse University and Los Angeles in 1981. But the FGCS Project prompted a change of gear. The First International Conference on Logic Programming was held in Marseille in 1982, followed by the Second ICLP in Uppsala in 1984. So the Third ICLP in London presented the first opportunity for the mainly European research community in logic programming to address the challenge of its North American rival, SLP.

The main organisers of the SLP at that time were unknown to the logic programming research community, and did not include the few logic programmers working in North America, most notably at Syracuse University and the University of Waterloo. So the purpose of the foundation of ALP was, not only to promote logic programming, but also to safeguard its identity.

Following the formation of ALP, with Keith Clark as its first President, discussions were held with the SLP group, which by this time included a number of distinguished logic programmers. The discussions focussed at first simply on co-ordinating the SLP and ICLP conferences, and later on bringing the SLP under ALP auspices. The first Joint ICLP and SLP, which resulted from these discussions and marked the beginning of cooperation, was held in Seattle in 1988. By this time, the truly international character of ALP had been firmly established, with the first meeting of ICLP outside of Europe, at Melbourne in 1987.

The main activity of the ALP has been the organisation of its conferences, primarily ICLP and NACLP, the North American Conference on Logic Programming, which took over from SLP. In addition, a number of national and regional logic programming organisations, in North America, Italy, France, Germany and the United Kingdom, affiliated with the ALP and organised their own meetings under ALP auspices.

The ALP also published its own newsletter. The founding editor, Luis Pereira in Lisbon, invented the logo, for the newsletter, which later became the logo of the ALP as a whole. Luis was followed as editor by Chris Moss and then Andrew Davison at Imperial College. It became an electronic newsletter when the editorship passed to Sandro Etalle at the University of Twente and then Enrico Pontelli at New Mexico State University.

Not all logic programming related activities since the founding of the ALP have been carried out under its auspices. Among the most notable of these were the series of Prolog Application Conferences initiated by Al Roth in the UK, the similar series of conferences organised by IF-Prolog in Japan, the logic programming conferences in Japan, the European Community Compulog Network of Excellence, and Compulog North America, and more recently the annual Symposium on Practical Aspects of Declarative Languages (PADL).

The Journal of Logic Programming (JLP), which was founded by Alan Robinson and published by Elsevier Science, was set up independently of ALP before its foundation. It was eventually adopted as the official journal of the ALP. During the term of Krzysztof Apt as president and Maurice Bruynooghe as the Editor-in-Chief, the complete Editorial Board of the JLP collectively resigned and founded a new journal, Theory and Practice of Logic Programming (TPLP) with the Cambridge University Press. TPLP is substantially less expensive than the JLP and is now the official journal of the ALP.

These activities were overseen by a succession of Presidents, supported by an Executive Committee: Keith Clark at Imperial College from 1986 to 1990, Herve' Gallaire at ECRC from 1990 to 1993, David Scott Warren at Stony Brook from 1993 to 1997, Krzysztof Apt at CWI in Amsterdam from 1997 to 2001, and Veronica Dahl at Simon Fraser University in Vancouver from 2002 to the present.

For many years, the ALP was administered at Imperial College in London. Bob Kowalski was the Secretary, and Frank McCabe, Fariba Sadri and Francesca Toni were the successive Treasurers. Cheryl Anderson-Deakon was the Administrative Secretary. This arrangement changed in the late 90s, when the administration became distributed. David Scott Warren in Stony Brook became the Secretary-Director, and Pat Hill in Leeds became the Treasurer.

Robert A. Kowalski October 2004

---

---

Frogs and Pigeons

Editor: Paolo Baldan
Department of Computer Science
University Ca' Foscari of Venice

---

Q1. The frog Froggy lives in a small pond (A). One day Froggy decides to move to a different pond (B) to meet some friends. Unfortunately, on the way from (A) to (B) there are several dangerous holes, one every n inches (one at n, the next at 2·n an so on), which Froggy must avoid. You have to know also that Froggy is a very precise frog: any jump is exactly an integer number of inches long (and no jump has length 0).

After thinking a while, Froggy says proudly: "I found a set of n jumps which I can perform in any order, and which, in any case, will lead me safely to my friends'!"

Do you think that Froggy is right?

Answer. Well, it seems that Froggy made a mistake. In fact, let l₁, ..., l_n be the lengths of the jumps Froggy decided to do (l_i > 0 for any i). Then, the fact that these jumps can be performed safely in any order, means that for any non-empty subset I of { 1, ..., n }, the total length of the jumps with index in I will not bring to a hole (i.e., such length is not k ·n for some k). More precisely, if for integers i, j, and a subset I of { 1, ..., n }

• i mod j denotes the remainder of the quotient of i by j,
• Len(I) denotes the sum of the lengths of the jumps with index in I, i.e., Len({ i₁, ..., i_j }) = l_i1 + ... + l_ij and
• mod(I, i) is a shortcut for Len(I) mod i

then we have that for any non-empty subset I of { 1, ..., n }

mod(I,n) <> 0

This is not possible. In fact, take the n sets I_i = { 1, 2, ..., i } for i = 1,..., n. Under the above assumption 0 < mod(I_i,n) < n for any i, and thus, by the Pigeon Hole Principle, it follows that there are j, k such that mod(I_j,n) = mod(I_k, n). Assume, without loss of generality, that j < k. Then, if we define I_j,k = { j + 1,..., k } it is trivial to see that

mod(Ij,k,n) =

= Len(Ij,k) mod n =

= (Len(Ik) - Len(Ij)) mod n =

= ((Len(Ik) mod n) - (Len(Ij) mod n)) mod n

= (mod(Ik,n) - mod(Ij,n)) mod n

= 0

and thus I_j,k contradicts the hypotheses.

Q2. We explain the above reasoning to Froggy which promptly replies: "I see, but your formalisation is not convincing: I can jump forward and backward, and, actually, your reasoning correctly applies also to the case in which some of the l_i's are negative (assuming that there is a hole also at 0, i.e., at the start of the path). But you forgot to take into account the fact that only sequences of jumps which stay always within the path from (A) to (B) are acceptable. For instance, starting from (A), my first move cannot be a backward jump since in this way I would exit from the path ...".

Uhmm, this looks more complicated ... maybe Froggy is right this time? What do you think? Well, let us try to formalise Froggy's statement. The claim is that there is a set of integer numbers { l₁,..., l_n } such that

1. the sum of the jumps leads from (A) to (B), hence it is positive
   Len({1, ..., n}) = d > 0
2. any sequence of such jumps which stays within (A)-(B) is safe, i.e., for any permutation i₁,..., i_n of 1,..., n, such that for any h = 1,..., n it holds that 0 <= Len({ i₁, ..., i_h }) <= d, we have that for any h

   mod ({ i1,..., ih }, n) <> 0

Answer. Well, we must admit that Froggy was right ... with the above constraints it can be that any sequence of jumps is safe. Take, for instance, n = 3 and l₁ = +7, l₂ = -3 and l₃ = +7 (hence d= 7-3+7 = 11). The only two valid sequences are l₁, l₂, l₃ and l₃, l₂, l₁, which are both safe. The reasoning in Q1 applied to I = { 1, 2, 3 } would give the set I_1,2 = { l₂ } which does not correspond to a valid sequence of jumps.

---

---

Community News

---

List of News:

• TPLP Free On-line
• News from Theory and Practice of Logic Programming
  
• The TPTP Problem Library
  
• Proceedings of RTA'04 Online
• 10th Estonian Winter School in Computer Science
  
• Parma Polyhedra Library 0.6.1
• VisiRule: a New Graphical Business Rules Tool from LPA
  
• LOGTalk 2.20.0 Available
• EASST and its Newsletter
• PhD or PostDoc Position at HU Berlin
  

---

Theory and Practice of Logic Programming Free On-Line
Communicated by K. Apt, M. Bruynooghe, B. Demoen

---

If you are a TPLP author who might recall that the Cambridge University Press has agreed that the accepted versions of the TPLP submissions are posted in the Computing Research Repository (CoRR),

We are happy to inform you that thanks to this provision we now have a free online version of TPLP that also includes all book reviews published in TPLP, at the following URL:

This URL can be reached through the home page of the Association for Logic Programming in Leuven,

We would like to thank Qiu Jiang, a student at the National University of Singapore, for creating the website and adding to CoRR the accepted versions of the `missing' papers.
We hope that this small contribution of the logic programming community will inspire others in promoting a free access to scientific literature.

We plan to maintain this free online version of TPLP and appeal to prospective TPLP authors to keep helping us in this endevour.

Krzysztof Apt
Maurice Bruynooghe
Bart Demoen

---

News from Theory and Practice of Logic Programming
Communicated by Maurice Bruynooghe

---

The transition period from JLP to TPLP has been successfully completed by the incorporation of TPLP in the 2003 ISI Science Citation Index. Its impact factor is 1.045. TPLP is indebted to SPARC, the Scholarly Publishing and Academic Resources Coalition for advise and support in preparing and submitting our application to ISI.

Another innovation is that all TPLP research papers are archived in The Computing Research Repository (CoRR) (http://xxx.lanl.gov/archive/cs/intro.html) and all TPLP material can be reached from the ALP website (http://www.cs.kuleuven.ac.be/~dtai/projects/ALP/TPLP/)

The Editor-in-Chief was appointed for a period of 5 years. After 10 years being E-i-C for JLP and 5 year for TPLP, I have insisted that it was time for a new E-i-C. The executive committee of ALP together with the area editors of TPLP have proposed Annalisa Bossi as new E-i-C to the publisher. She will take over the journal on January 1 2006.

Appointments for the editorial board were for an initial period of three years. A revision of the board is in progress. The revision of the areas and editors has been completed. The new list is below. Most noticeable are new areas for the emerging fields of Inductive Logic Programming and Multi-relational Data Mining (editor Luc De Raedt) and for Specification, Analysis and Verification of Systems (editor Michael Leuschel). After many years of high quality service for JLP and TPLP, Joxan Jaffar, Kazunori Ueda, Manuel Hermengildo and Veronica Dahl are leaving the board of area editors. They all deserve many thanks from the community, especially Joxan who handled over 200 submissions. As new editors we also welcome David S. Warren, Gopal Gupta and Catuscia Palamidessi.

The board of editorial advisors serves several purposes. It contains a number of distinguished scientists from our field or closely related ones, whom, by their presence are a guarantee of the high academic standards of the journal. On the other hand, the board should also be representative for the active leading researchers in the field and be a pool for future area-editors. Revision of the board of Editorial Advisors is in progress and any suggestions for members are welcome.

Finally, the quality of the journal depends on the quality of its submissions. The content of the journal should reflect the main research activities in the field. The editors are soliciting submissions. New submissions should be directed to the area-editor you consider most appropriate for the topic of the paper with a cc to the E-i-C.

 Areas and Editors:
 
 Constraints
 Peter J. Stuckey
 University of Melbourne 
 pjs@cs.mu.OZ.AU
 
 Databases and Semantic Web  Reasoning
 Michael Kifer
 Stony Brook University
 kifer@cs.stonybrook.edu
  
 Design, Analysis and Implementation of Languages
 David S. Warren 
 Stony Brook University
 warren@cs.sunysb.edu

 Inductive Logic Programming and Multi-relational Data Mining
 Luc De Raedt
 Albert-Ludwigs-Universit\"at Freiburg
 deraedt@informatik.uni-freiburg.de
 
 Knowledge Representation and Nonmonotonic Reasoning 
 Michael  Gelfond
 Texas Tech. University
 mgelfond@cs.ttu.edu
 
 Logic Programming Methodology & Applications
 Gopal Gupta 
 The University of Texas at Dallas
 gupta@utdallas.edu

 Specification, Analysis and Verification of Systems
 Michael Leuschel 
 University of Southampton
 mal@ecs.soton.ac.uk

 Theory
 Giorgio Levi
 Universit\'a di Pisa
 levi@di.unipi.it

 Technical Notes
 Catuscia Palamidessi
 INRIA Futurs and LIX
 catuscia@lix.polytechnique.fr
  
 Programming Pearls
 Lee Naish  
 University of Melbourne
 lee@cs.mu.oz.au 
 and  
 Bart Demoen 
 Katholieke Universiteit Leuven
 Bart.Demoen@cs.kuleuven.ac.be
 
 Book reviews
 Krzysztof Apt
 National University of Singapore 
 apt@comp.nus.edu.sg

---

The TPTP Problem Library, Release v2.7.0
Communicated by Geoff Sutcliffe and C. Suttner

---

The TPTP  (Thousands  of Problems  for Theorem  Provers)  Problem Library  is a library of test problems for automated theorem proving (ATP) systems.  The TPTP
supplies the ATP community with:

• A comprehensive library of the ATP test problems that are available today, in order to provide an overview and a simple, unambiguous reference mechanism.
• A comprehensive list of references and other interesting information for each problem.
• New generalized variants of problems whose original presentation is hand-tailored towards a particular automated proof.
• Arbitary size instances of generic problems (e.g., the N-queens problem).
• A utility to convert the problems to existing ATP systems' formats.
• General guidelines outlining the requirements for ATP system evaluation.
  

The principal motivation for this project is to move the testing and evaluation of ATP  systems from the previously  ad hoc situation onto a firm footing. This became necessary,  as results being published do  not always accurately reflect the  capabilities of  the ATP  system being  considered.  A common  library  of problems  is necessary  for meaningful  system evaluations,  meaningful  system comparisons,  repeatability  of testing,  and the  production of  statistically significant results. The TPTP is such a library.

TPTP v2.7.0 is now available at:

The TPTP-v2.7.0.tar.gz file contains the library, including utilities and basic documentation. Full documentation is online at:

The TPTP  is regularly updated with new problems,  additional information,  and enhanced utilities.  If you would like to register as a TPTP user,  and be kept informed of such developments, please email Geoff Sutcliffe.

---

Proceedings of RTA'04 On-Line
Communicated by Vincent van Oostrom

---

Dear all,

The proceedings of RTA'04, LNCS 3091, are now available online.
You can find information about it at
or access the online version at

kind regards,
Vincent van Oostrom

---

10th Estonian Winter School in Computer Science
Communicated by Tarmo Uustalu

---

Background and objectives
EWSCS is a series of regional-scope international winter schools held annually in Estonia. EWSCS are organized by CIDEC, a joint initiative of Institute of Cybernetics (Tallinn), Tallinn University of Technology and University of Tartu for the advancement of higher education in computer science and information technology. EWSCS'05 is the tenth event of the series.

The main objective of EWSCS is to expose Estonian, Baltic, and Nordic graduate students in computer science (but also interested students from elsewhere) to frontline research topics usually not covered within the regular curricula. The subject of the schools is general computer science, with a bias towards theory, this comprising both algorithms, complexity and models of computation, incl. cryptography, and semantics, logic and programming theory. The working language of the schools is English.

Programme
The schools' scientific programme consists of short courses by renowned specialists and a student session. The course list for EWSCS'05 is the following:

Olivier Danvy (University of Aarhus, Denmark:
      A Vade Mecum to Continuations

Kurt Mehlhorn (MPI Saarbrücken, Germany):
      Implementing Algorithms

Peter Bro Miltersen (University of Aarhus, Denmark:
      Universal Methods for Derandomization

Greg Morrisett (Harvard University, Cambridge, MA, USA):
      Topics in Language-Based Security

Benny Pinkas (HP Labs, Haifa, Israel):
      Privacy-Preserving Data Mining

The purpose of the student session is to give students an opportunity to present their work (typically, thesis work) and get feedback. Registrants are invited to propose short talks (20 min) or posters. The selection will be based on abstracts of 150-400 words.
The social programme consists of an excursion and a conference dinner.

Venue
Palmse is a small settlement 80 kms to the east from Tallinn in the county of Lääne-Viru. It is renowned for a large manor that used to belong to the von Pahlen family, today hosting the visitors' center of the Lahemaa National Park, a museum, and a hotel.

Tallinn, Estonia's capital, is famous for its picturesque medieval Old Town, a UNESCO World Heritage site. There are direct flights to Tallinn from London, Paris, Milan, Amsterdam, Brussels, Frankfurt, Munich, Hamburg, Berlin, Prague, Warsaw, Moscow, Kiev, Copenhagen, Oslo, Stockholm, Gothenburg, Helsinki, Vilnius, Riga, ferries from Stockholm and Helsinki. From Vilnius, Riga, the Eurolines coach service is the practical travel option.

Registration and cost
The deadline for registration and submission of abstracts is 14 January 2005. All registrants will be notified of acceptance to school and acceptance of their talks/posters by 28 January 2005. The participation fee 4000 EEK (260 EUR) includes course materials, full boarding at Palmse, transportation from Tallinn to Palmse, excursion and conference dinner. For some students, we can partially waive the fee.

Programme committee / organizing committee
Tarmo Uustalu (IoC) (chair), Monika Perkmann (IoC) (secretary), Helger Lipmaa (Helsinki U. of Techn.), Peeter Laud (U. of Tartu), Jaan Penjam (IoC), Heli Uibo (U. of Tartu), Jüri Vain (Tallinn U. of Techn.), Varmo Vene (U. of Tartu)

Sponsors
Centers of Excellence in Research Programme of Ministry of Education and Research of Estonia, FP5 IST project eVikings II

Further information
Details on the submission of abstracts, registration procedure and cost, application for fee waiver are available from the school webpage, http://www.cs.ioc.ee/yik/schools/win2005/. Questions should be sent to ewscs05@cs.ioc.ee.

---

Parma Polyhedra Library 0.6.1
Communicated by Roberto Bagnara

---

We are very happy to announce the availability of PPL 0.6.1, the latest release of the Parma Polyhedra Library, a modern library for the manipulation of convex polyhedra especially targeted at static analysis and verification of complex software and hardware systems.

The main focus of this release is on complete support for powersets of polyhedra.  This includes the customizable framework for the definition of widening operators we have proposed at this year's VMCAI conference.  Then there is support for summary dimensions as proposed by Denis Gopan and colleagues in their TACAS 2004 paper.  We have started adding demo programs to the library.  One of them, `ppl_lcdd', is actually useful and is competitive with similar programs available out there.  Many other improvements have been performed: documentation, performance, portability and the configuration machinery have all been improved.  A handful of bugfixes complete the picture.

For more information, visit the PPL web site at

The PPL development team:

---

Logtalk 2.20.0 Available
Communicated by Paulo Moura

---

Logtalk 2.20.0 is now available for downloading from the Logtalk web site:

    http://www.logtalk.org/

This release adds a new uses/2 predicate directive, improves installation instructions for Windows users, adds new Windows JScript scripts for automating loading of Logtalk with selected Prolog compilers, and contains new, improved scripts for converting XML documenting files to PDF files and (X)HTML files.


From the release notes:

• Added support for the uses/2 predicate directive (whose semantics is similar to C++ using-declarations). Updated the uses/1 entity directive to accept as argument a single object identifier.
• Improved installation instructions for Windows users.
• Added four new sample bash shell scripts and Windows JScript scripts for converting XML documenting files to PDF, HTML, and XHTML using several XSL processors.
• Added missing namespace to XSL files in order to generated valid (X)HTML files with recent versions of XSLT processors.
• Updated the User Manual documentation on converting XML documenting files to other formats.
• Removed the texml.xsl XSLT file as the TeXMLatte application it depends on is no longer available.
• Added Windows JScript script for copying the Logtalk examples, library, and xml directories to the user directory.
• Added Windows JScript scripts for easy integration of Logtalk with ECLiPSe, SWI-Prolog, SICStus Prolog, and YAP.
• Added missing extension for source metafiles to the SWI-Prolog hook file.
• Corrected a bug in the lgtxhtml.xsl XSLT file where a wrong reference to the Logtalk CSS file is being used in the xml-stylesheet tag.
• The iso_initialization_dir/1 compiler option is now a read only flag, defined in the configuration files.

Happy logtalking!

Paulo

---

VisiRule: a New Graphical Business Rules Tool from LPA
Communicated by Clive Spenser

---

London -- August 2004
LPA today announced VisiRule, a graphical charting tool which lets you draw, test and generate business-rules applications and/or components.
VisiRule allows developers to design and deliver commercial rule-based systems, expert systems, and knowledge-based systems on the PCs and Internet without writing any code. You simply draw the decision logic using a point-and-click paradigm and state the conditional logic to use at the relevant branching points.

This means that you no longer have to be a sophisticated AI programmer to build decision support systems which may involve complex and interconnected logic. VisiRule allows you to rapidly produce accurate charts which you can share and discuss with non-technical collegaues who understand the business process at hand.
VisiRule generates applications thru its delivery of Flex KSL code. Flex is a hybrid Expert System development toolkit based in Prolog and used in many commercial knowledge-based systems. Prolog is a logic-based AI language which includes support for theorem proving.

Basic features of VisiRule include:

• simple point and click drawing interface
• interactive editing of decision charts
• layout tools for alignment of boxes and links
• export to meta-file facility for using charts in Word etc
• logic-based syntax analyser to detect typos
• logic-based semantic analyser to check for completeness and consistency

VisiRule runs on all version of Windows and requires 128 Mb memory.
The LPA web-site contains an overview of VisiRule on:

The LPA web-site contains a suite of interactive Flex demos on:

LPA is a leading supplier of Prolog compilers, AI and Expert System tools. Based in London, LPA was formed in 1981 and is a well respected Artificial Intelligence company with customers throughout the world.

For further information contact:

---

EASST and its Newsletter
Communicated by Julia Padberg

---

EASST is a European non-profit Association that aims at promoting research, development and applications in the  area of systematic and rigorous engineering of software and systems.

Software and Systems Engineering does not receive the public recognition it deserves as one of the most advanced  technologies with a great impact on Europe`s economic and societel prosperity. This is due to a large extent to the  low degree of visibility of the community. Especially research is scattered around a rather large number of communities, meetings in different conferences and workshops.

When joining us you enter a larger community and you will help to strengthen a new association that is aiming at a  better visibility and recognition of your work.When joining us you will benefit from a cross-fertilisation between a  number of subcommittees in joint initiatives, meetings and activities.When joining us you will have easy access to  consolidated information collected from scattered sources.

All information is  easily accessible by a number of electronic services. Membership is for free.
Visit our Web-Site: http://www.easst.org/

The EASST-Newsletter is distributed electronically (PDF) twice annually (June and December) and serves as a forum for topics related to EASST. Previous issues can be found on our Web-Site: http://www.easst.org/

Three focus areas for EASST have been given special colums. If you have a contribution, that seems to be fitting for one of the columns, please send it to the corresponding column editor until November 15, 2004.

The columns are:

THE CONTINUOUS LEARNING COLUMN by Herbert Weber (email : herbert.weber@isst.fhg.de)
Topics of interest for this column are :
academic as well as vocational education within the area of IT, European curriculae for software engineering at universities, research on e-teaching/e-learning as well as the harmonization of IT teaching in general, web-based support for informal learning strategies, and others.
Other kinds of contributions concerning continuous learning are welcome too:  calls for papers or participation for workshops and conferences; reports on past workshops and conferences; summaries of final project reports; book reviews.

THE SOFTWARE ARCHITECTURE COLUMN by Michel Wermelinger (email : mw@di.fct.unl.pt)
Software Architecture (SA) column seeks contributions reporting on theoretical or applied research, or industrial experience in any subject related to SA. Topics of interest include, but are not restricted to, the following: architectural description languages and formalisms; architectural patterns and styles; product-line and domain specific architectures; architecture extraction, analysis and transformation; SA education; SA economics and process. Descriptions of publicly available case studies and tools are also welcome. Other kinds of contributions are also possible, as long as they are related to SA: calls for papers or participation for workshops and conferences; reports on past workshops and conferences; summaries of final project reports; book reviews.

THE TOOL COLUMN by Tiziana Magaria (email : Tiziana.Margaria@cs.uni-dortmund.de)
We consider tools to be the reification of concepts, and as such the right dissemination medium to reach practitioners who are interested in using the results of research without necessarily accessing research literature. The concrete character of tools, which allows direct experimentation, makes them attractive for application engineers in the field in search of solutions for concrete problems.
Contributions are welcome in form of descriptions or presentations of concepts or tools, discussion themes, position papers, experience reports, and tool/environment demonstrations, but also software development environments with comparable goals. Additionally, conferences and workshop announcements, and presentation of initiatives are welcome too.

THE VISUAL MODELING COLUMN by R. Heckel (email: reiko@uni-paderborn.de)
Both in software engineering and in the more classical engineering disciplines, the use of visual notations, e.g., for documentation of requirements or communication with customers, has a long tradition. Driven by the increasing complexity of the problems such notations have become more elaborate and evolved towards visual modeling techniques with their own methodology and tool support. The reasons for the success of visual modeling techniques are manyfold. Visual representations are direct and intuitive, simplifying the communication between developers and their customers. They are extremely effective at delivering useful abstractions of industrial-scale systems. This is evidenced by the success of the UML and its paradigm of model-driven development. The Unified Modeling Language with its many sub-languages and dialects is, indeed, one of the two main foci for the research in this project, as well as graph- and net-based modeling techniques like graph transformation, high-level or timed Petri nets, flow diagrams, or domain-specific net-like notations.
Rather than ad-hoc solutions, a discipline of language engineering is required to support the definition and implementation of modeling languages with respect to their abstract syntax and well-formedness rules, operational and denotational semantics, consistency and refinement relations, and model transformations.

---

PhD or PostDoc Position at HU Berlin
Communicated by Martin Grohe

---

Applications are invited for a two or three year research position in Theoretical Computer Science at the Humboldt-University at Berlin. The position is within the research project "The complexity of constraint satisfaction problems" (http://www.informatik.hu-berlin.de/logik/forschung/csp-en.html).

Candidates are required to a have a degree in Mathematics or Computer Science. Both post-doc and pre-doc applications are welcome; it will be possible to work towards a doctoral degree.  Excellent knowledge of Theoretical Computer Science and Mathematics is expected.

Applications should be sent to the following address until 30. November 2004:
      Prof. Dr. Martin Grohe
      Humboldt-Universitaet zu Berlin
      Institut fuer Informatik
      Unter den Linden 6
      10099 Berlin
      Germany

Informal enquiries may be addressed to grohe_at_informatik.hu-berlin.de.

---

---

Logic Programming Doctoral Dissertations

Editor: Enrico Pontelli

---

---

Daniel Cabeza Gras
An Extensible, Global Analysis Friendly Logic Programming System
Universidad Politecnica de Madrid, September 2004

---

The goal of this PhD Thesis is to design and develop a next-generation multi-paradigm programming system, which is based on a Logic Programming kernel and is amenable to global analysis.

The Logic Programming paradigm has proved particularly useful for developing complex applications, such as those which appear in Artificial Intelligence, including knowledge based systems, intelligent agents, expert systems, etc.

In the context of Logic Programming, much progress has been made in the area of global program analysis (mainly based on abstract interpretation), which is used for inferring information at compile-time on the run-time behavior of programs.  The inferred information has been shown to be useful not only to produce optimized code, but also in program verification and error detection/diagnosis.

However, while global analysis of logic programs is at this point relatively well understood from a theoretical point of view, little attention has been given to developing a practical logic programming system (i.e., providing at least a complete Prolog implementation with modules) which incorporates such analysis.  This thesis fills this gap by proposing a language design and system implementation that makes global analysis practical and scalable.

Another objective of the system developed is to serve as a workbench for developing new extensions to Logic Programming. The system includes techniques which allow extending the kernel language in a very flexible way (and at the source level), and this has been used to develop and test numerous extensions including functions, objects, constraints, records, persistence, distributed execution, and others.

The resulting system (Ciao) has been made available freely to the community and currently has a sizable number of users.

---

---

Net Talk

edited by Roberto Bagnara

---

Foreword:
This time, your "Net Talk" editor has found nothing in comp.lang.prolog that seemed to deserve publication here.  It may well be the case that I overlooked some interesting discussion, in which case I will be very grateful if you could draw my attention over it. On the other hand, I will take this accident as a good excuse to introduce the reader to other logic programming resources available on the net.

We start with one of my favorites: the mailing list of SWI-Prolog (http://www.swi-prolog.org/).  Despite the disclaimer you can find on the mailing list home page ("Users may use this forum to discuss porting problems and SWI-Prolog specific questions. Please use other media, such as the newsgroup comp.lang.prolog. for general Prolog questions.")  I consider this list as one of the best available sources of information on the Prolog language and on Prolog programming.  Even if you use a different Prolog system, you definitely want to subscribe that list.

    Roberto Bagnara

---

A Little Problem From: Flavia Cristina Bernardini I'm having trouble with this procedure: a(E1(_,_),E2(_,_)):-E1@<E2. Anybody could tell me what to do in this case?

I'm having trouble with it too, trying to imagine what kind of context could make this seem a sensible thing to do.  It is very far from idiomatic Prolog.

Possibly the first thing to do is to get the space bar on your terminal fixed so that you can put spaces around major operators and after commas.

The cleanest way to solve your problem would be either to restructure your code so that you don't want to do whatever it is you are doing here.  Second cleanest would be to redesign your data structure so that you write f(X,E,Y) rather than E(X,Y).  (There is sure to be some helpful word you can use instead of 'f'.)  Then you would just write

    a(f(_,E1,_), f(_,E2,_)) :- E1 @< E2.

If you really REALLY ****REALLY**** have to stick with the data structure you have (and the chances of that are very low indeed), you could write

    a(T1, T2) :-
        functor(T1, E1, 2),
        functor(T2, E2, 2),
        E1 @< E2.

The question is, what is the context?  What do terms of the form E(X,Y) mean, and why are you comparing them this way?

---

Flavia Cristina Bernardini wrote:
> I'm having trouble with this procedure:
>
> a(E1(_,_),E2(_,_)):-E1@<E2.
>
> Anybody could tell me what to do in this case?

My understanding is that SWI-Prolog does not have variable functors; that is, you cannot write X(Y,Z) as something to match to a(b,c).
The built-in predicates functor, arg, and =.. enable you to take structures apart.  In this case it looks like functor is the one you want.

Perhaps someone can comment on the implementation reasons for not having variable functors.

---

Michael A. Covington wrote:
> My understanding is that SWI-Prolog does not have variable functors
> [meaning "function symbols", it's a very important distinction];
> that is, you cannot write X(Y,Z) as something to match to a(b,c).
   
Some versions of the public-domain READ.PL that I released years ago *do* support X(Y,Z) syntax, mapping it to call(X, Y, Z), so that you can write

    map(P, [],     []).
   map(P, [X|Xs], [Y|Ys]) :-
        P(X, Y),
        map(P, Xs, Ys).

This was put into an internal release of Quintus Prolog once, and *very* quickly afterwards ripped out again.

> ...
>
> Perhaps someone can comment on the implementation reasons for
> not having variable functors.
   
It's the reverse, actually.  There are no implementation problems whatsoever, and several Prologs provide this nasty misfeature.

The problem is coherence.  What the heck does it MEAN? For example, if I can write T = F(X,Y), F = a, then why *precisely* can I not write T = F(X,Y), F = 1? If I can do that, why can't I write 1(X,Y) directly? Even worse, if I can write T = F(X,Y), F = g(27), then why *precisely* can I not write g(27)(X,Y), and if I do, is it the same as g(27, X, Y) and if not, why not?

Recall the map/3 example above.  In the vast majority of cases, the "poor man's closure" that you want to pass as the P argument of map/3 is *not* a simple atom; it is an atom plus one or more arguments.  For example, map(plus(2), Xs, Ys).  So we have to wonder what
      P = plus(2),
    T = P(X, Y)
means, given that you are _not_ allowed to write plus(2)(X, Y) directly, and that you _do_ want it to mean the same as plus(2, X, Y).  To make map/3 work, you don't really have any alternative but to make P(X, Y) mean the same as call(P, X, Y), but if you do _that_, then T = P(X,Y), P = f does *not* mean the same as T = f(X,Y).

Prolog terms are very simple:

    1.    A term is variable (var/1)
    2.    or it is not (nonvar/1). If it is not variable, then it is
            2a.  a number (number/1)
                    2a1.  which might be an integer (integer/1)
                    2a2.  or a floating-point number (float/1).

            2b.  or something you could call (callable/1)
                     2b1.  which might be an atom (atom/1) having 0 arguments
                     2b2.  or a compound term (compound/1) having 1 or more arguments.
            A nonvariable term has a functor, which comprises a function symbol
            and an arity.  The function symbol must be atomic (atomic/1), and
            if it is a number, the arity must be 0.

There is no fundamental implementation reason why numbers could not be allowed arguments.  In fact some Prologs have to work a bit harder NOT to let this happen, because they COULD very easily support it. There are two reasons that I'm aware of that this is not done:

• (f) Floating-point numbers are strange enough (there are floating point numbers X Y for which X =:= Y but not X = Y [take X = +0.0, Y = -0.0] and conversely for which X = Y but not X =:= Y [take X = Y = some NaN]) that using them as function symbols is rather risky.
• (m) We don't want to fool people into writing 2(X+Y) when they mean 2*(X+Y).
  

Ensuring that functors are always (number,0) or (atom,arity) pairs permits implementations in which compound terms require only arity+1 cells. Allowing a term to have a variable for its function symbol doesn't actually *buy* you anything, and the cost (increased space and enormously increased opportunity for error) is high.

Suppose you have a pseudo-Prolog program where variables are allowed as function symbols.  Now, rewrite it.  Everywhere that
    <F>(<A1>,...,<An>)
appears, write instead
    {}(<F>,<A1>,...,<An>).
You will also need to replace
    functor(T, F, N)
with   
    F = {}(F1), N = {}(N1), functor(T, {}, N2), plus(1, N1, N2)
and make other similar changes to a number of built-in predicates. In particular,
    *call(P) :-
        P =.. [{},Q|Xs],
        Q =.. [{},R|Ys],    /* this should probably be recursive */
        append(Ys, Xs, Zs),
        G =.. [R|Zs],
        call(G).
The details are tricky, but the result is that you don't get any added power.

It's also a bit of a nightmare for debugging.  You can't hang a portray/1 mapping off a functor that isn't fully specified...

---

Flavia Cristina Bernardini wrote:
> I'm having trouble with this procedure:
>
> a(E1(_,_),E2(_,_)):-E1@<E2.
>
> Anybody could tell me what to do in this case?

You are not allowed to use variables as functors. Take a look at =../2. Maybe this is what you look for:

---

Emerson Lums dos Santos <emerson@ppgia.pucpr.br> wrote:
> You are not allowed to use variables as functors.

A functor is a *PAIR* (Symbol,Arity) commonly notated as Symbol/Arity. When one writes E(X,Y), one is not using a variable as a *FUNCTOR* but as a *FUNCTION SYMBOL*.  Functor and function symbol are completely separate types; there is no overlap between them at all.

Some Prologs (Sigma Prolog and PopLog amongst others, if I recall correctly) *do* let you use variables as function symbols.  It's an incredibly bad idea, which pops up whenever people have a particular implementation of compound terms and decide to let that implementation show through.

>    Take a look at =../2.
>    Maybe this is what you look for:
>  
>    a(E1, E2) :-
>        E1 =.. [_, _, _],
>        E2 =.. [_, _, _],
>        E1 @< E2.
   
This is of course wrong.  The code should be


But in any case it is a bad idea. (=..)/2 is almost _never_ the right tool for the job. Why construct 6 list cells that you have no use for whatsoever, when you can get the bit you want without constructing _any_ terms? If you just want the function symbol of a term, use functor/3. (It's functor/3, not function_symbol/2, because it returns ALL of the functor, the arity as well as the function symbol.)

It's really like trying to work out how to minimise blood loss while sawing your hand off; it's much better to replan your project so that you don't have to do anything like that in the first place.

---

Ah.  Summing it up, if you're going to have variable function symbols, you have to either invent a new kind of variable that can only unify with an atom, or else prepare to handle a large and clumsy new set of error conditions!

---

> Ah.  Summing it up, if you're going to have variable function
> symbols, you have to either invent a new kind of variable that
> can only unify with an atom, or else prepare to handle a large
> and clumsy new set of error conditions!

Or alternatively accept any prolog term as functor symbol, xsb allows to do it:

althought, it's mostly a hack in the prolog compiler and needs functor symbols to be used in this fashion predeclared.

---

>> Or alternatively accept any prolog term as functor symbol, xsb allows
>> to do it:
>> 
>>   http://xsb.sourceforge.net/manual1/node42.html

But what XSB is implementing there is HiLog (http://citeseer.nj.nec.com/chen89hilog.html), not just plain Prolog.

---

Richard A. O'Keefe wrote:
> Prolog terms are very simple:

...but they could be simpler?

Having "integer" and "float" types is arbitrary and inelegant, and is two steps down a slippery slope Prolog need never have gone down. (why not have 'currency' as well, or 'datetime'? or 'color'?)

All Prolog needs are names (function symbols) which are vectors of zero or more byte values (0..255)

We can define (directed) arithmetic relations over atoms whose names are one-, two-, four- and eight-byte vectors etc

Sure, if some atom is "meant" to be an ANSI string rather than a twos-complement integer, the result may be garbage or the goal may fail, but heck, Prolog is untyped, right?

Of course, any such system should not be called Prolog :-)

NB I'd guess that names of up to, say, 4 bytes would be copied around as values, while longer ones would be stashed in a dictionary, i.e. this is nothing to do with semantics but just an implementation efficiency device?

---

Paul Singleton wrote:
> Richard A. O'Keefe wrote:
>> Prolog terms are very simple:
>
> ...but they could be simpler?
>
> Having "integer" and "float" types is arbitrary and inelegant,
> and is two steps down a slippery slope Prolog need never have
> gone down.
 
CPU architecture.
 
> (why not have 'currency' as well, or 'datetime'? or 'color'?)
 
CPU architecture.

> We can define (directed) arithmetic relations over atoms
> whose names are one-, two-, four- and eight-byte vectors etc
 
Notation?

---

Paul Singleton <paul@jbgb.com> wrote:
> ...but [Prolog terms] could be simpler?
>   
> Having "integer" and "float" types is arbitrary and inelegant,
> and is two steps down a slippery slope Prolog need never have
> gone down.
   
If you want to use traditional arithmetic operators, then it is essential to distinguish somehow between integers and floating point numbers, because
    -0    is identical to 0
but
    -0.0 is NOT identical to 0.0

Let's ignore that (strongly motivated and rather important) IEEE detail, and just consider adding.

    plus(Ix, Iy, Iz) <-> Ix, Iy, Iz are all integers and Ix+Iy = Iz.

Since integer arithmetic is exact, plus/3 can solve for any one of its arguments given the other two.  (With fewer than two arguments bound, plus/3 would have to suspend.)

Unfortunately, if Fx (+) Fy yields Fz, it does NOT follow that Fz (-) Fy yields Fx.  In SWI Prolog, try
    ?- X is 1.0e-30, Y is 1.0, Z is X+Y, W is Z-Y.

So we have to have :- mode fadd(+,+,?), fsub(+,+,?), fmul(+,+,?), fdiv(+,+,?) and so on.

Because integer arithmetic and floating-point arithmetic are so different, any Prolog system which tries to blur the difference is going to make people seriously confused and introduce needless bugs.

For example, in SWI Prolog,
    ?- X is 1.0, integer(X).
Yes
    ?- X = 1.0, integer(X).
No
If you're not confused by that, let me tell you that I *am*. Very confused.  And some of my code IS broken by this.

So we have to distinguish integers from floating point numbers SOMEHOW.

> (why not have 'currency' as well, or 'datetime'? or 'color'?)
   
Because if you have good integer arithmetic (meaning: if you either support bignum arithmetic seamlessly or limit fixnums to no fewer than 64 bits)

• number of (some fraction of) smallest currency unit (cents or mills, say, or farthings in the old LSD days) can model currency;
  Note that there are lots of different currencies around, and that conversion between them is not simple because the exchange rates vary a lot.  Even within a single country, there are often "alternative" currencies like "hours".
  This is of particular importance for European countries. (Does the legal obligation to maintain accounts in _both_ the traditional currency _and_ the Euro still apply?)
• number of milliseconds since some epoch (or even microseconds) can model timestamps (especially if you don't worry about UTC leap seconds, because if you do, you can't pretend to represent timestamps a year or more in the future at all)
• colour (note the "u") isn't numeric. There are many different colour models, RGB is one, RGBa is another, CMYK, HSB, you name it.
  

Numbers, however, are ubiquitous.
More precisely, if you are given good enough integers well separated from floats you CAN distinguish

    mills(Number_Of_Mills)
    timestamp(Number_Of_MicroSeconds_Since_Epoch)
    colour(Red, Green, Blue, Alpha)

but without _some_ representation of numbers you can't get off the ground.

> All Prolog needs are names (function symbols) which are vectors
> of zero or more byte values (0..255)
   
We are not concerned with what *Prolog* needs but with what Prolog *programmers* need.
Here is a perfectly good representation for integers:

    :- type sint
       ---> n(pint)  % if T represents n, n(T) represents -1-n.
          ; p(pint). % if T represents n, so does p(T).
    :- type pint
       ---> z        % represents 0
          ; o(pint)  % if T represents n, o(T) represents 2n+1
          ; e(pint). % if T represents n, e(T) represents 2n+2.

It is straightforward to define integer addition, subtraction, comparison, multiplication, and quotient-and-remainder using these terms. Each integer has a unique representation as a 'sint'.

    :- pred
    plus(?sint, ?sint, ?sint),
    sint_compare(?order, +sint, +sint),
    times(?sint, ?sint, ?sint),
    divide(?sint, ?sint, ?sint, ?sint).

We could even have the Prolog reader accept decimal integers as a shorthand notation for such terms, so that 3 -> o(o(z)).  Heck, we could even use a portray_term/1-like hack to make the Prolog writer do the corresponding transformation on output.  And we'd get accurate answers for calculations that SWI quietly turns into floating-point; there wouldn't be any bound on the size of integers we could represent except available memory.

Of course, it would be slower. Just for interest, I wrote two loops, counting down about a million times.  One used the standard representation, the other the tree representation above.
I have real trouble believing the SWI figures.  Built-in binary arithmetic is SLOWER at subtracting one than "tree" arithmetic?  The time reported was the time for

     bin_down(0) :- !.
    bin_down(N) :- M is N - 1, bin_down(M).

to count down from 2097150.  As a cross-check, I tried counting _up_ 1.000000001 at a time from 0.0 to >2097150.0.  That took 59.55 seconds, so the rather high figure is plausible.  What's going on?

> We can define (directed) arithmetic relations over atoms
> whose names are one-, two-, four- and eight-byte vectors etc
   
We could, but if you want to write plus('\144', X, Y) to add 100 to X, I'd rather not, thanks.

The original motivation for making integer a separate data type was this: for *pure* Horn clause programming, every term is either a variable or a function symbol applied to 0 or more arguments.  To fit within this framework, an integer should be represented by *some* term, but as long as the built-in predicates know what to do with such terms, it shouldn't matter *which* term.  On the other hand, you don't programmers to have to avoid certain functors, when they don't know _which_ functors to avoid. Considering that computer algebra was an early application of Prolog, you really don't want to have to wrap every number in some functor that is different from (+)/2, (-)/1, (-)/2, (*)/2, ... just to be on the safe side. So integers were made an abstract data type.

> Sure, if some atom is "meant" to be an ANSI string rather than
> a twos-complement integer, the result may be garbage or the
> goal may fail, but heck, Prolog is untyped, right?
   
The Prolog _language_ is, but it does not by any means follow that Prolog program _designs_ are.  There's a reason for the existence of the DEC-10 Prolog type checker...

---

Richard A. O'Keefe wrote:
> For example, in SWI Prolog,
>     ?- X is 1.0, integer(X).
> Yes
>     ?- X = 1.0, integer(X).
> No
> If you're not confused by that, let me tell you that I *am*.
> Very confused.  And some of my code IS broken by this.

Still on the issue list, but you can use the iso flag.  See below.

1 ?- set_prolog_flag(iso, true).

Yes
2 ?- X is 1.0, integer(X).

No
3 ?-

>     Binary        Tree        Ratio
> SWI    35.99 sec    28.41 sec    0.79
> QP     3.34 sec    13.25 sec    3.97
>
> I have real trouble believing the SWI figures.  Built-in binary
> arithmetic is SLOWER at subtracting one than "tree" arithmetic?  The
> time reported was the time for
>     bin_down(0) :- !.
>     bin_down(N) :- M is N - 1, bin_down(M).
> to count down from 2097150.  As a cross-check, I tried counting _up_
> 1.000000001 at a time from 0.0 to >2097150.0.  That took 59.55
> seconds, so the rather high figure is plausible.  What's going on?

Without any precautions arithmetic is fully interpreted: first build the term N-1 then call the foreign is/2 implementation.  Using -O (or the optimise prolog flag) it compiles it to a stack machine.  Without optimisation it creates garbage and will do GC.  On my machine:



% pl -s test.pl
?- time(test).
% 4,194,302 inferences in 1.66 seconds (2526688 Lips)

% pl -O -s test.pl
?- time(test).
% 2,097,152 inferences in 0.88 seconds (2383127 Lips)

(SWI-Prolog 5.1.7 multi-threaded on Dual AMD-1600+).  At least your comparison goes the right way like that.  B.t.w. the difference in `inferences' is because the compiled arithmetic instructions aren't counted.

---

Richard A. O'Keefe wrote:
> The original motivation for making integer a separate data type was this:
> for *pure* Horn clause programming, every term is either a variable
> or a function symbol applied to 0 or more arguments.  To fit within this
> framework, an integer should be represented by *some* term, but as long
> as the built-in predicates know what to do with such terms, it shouldn't
> matter *which* term.  On the other hand, you don't [want] programmers to have
> to avoid certain functors, when they don't know _which_ functors to avoid.
> Considering that computer algebra was an early application of Prolog,
> you really don't want to have to wrap every number in some functor that
> is different from (+)/2, (-)/1, (-)/2, (*)/2, ... just to be on the safe side.
> So integers were made an abstract data type.

So the special-cased implementation of 'integer' as a subtype of 'atomic' implies an admission by Prolog's originators that its support for user-defined abstract data types is inadequate?

Your functor-avoidance scenario is just one instance of a dilemma faced by Prolog programmers when introducing an enumerated type: do we wrap values in a distinguishing functor, or hope that their type is always inferrable within context?

Either Prolog programmers need atomic subtypes or they don't: you say they do, but it's just tough if they weren't in at the start so they could build their pet types in as special cases :-)

---

Jan Wielemaker wrote:
> Still on the issue list, but you can use the iso flag.  See below.
>
> 1 ?- set_prolog_flag(iso, true).

I spent _ages_ searching through the PDF of the manual looking for a list of prolog_flag options.  It's a little unfortunate that "fix arithmetic bugs" and "other ISO differences" are coupled in a single flag; the non-ISO arithmetic behaviour is so supremely weird that iso arithmetic should be the default.

>>     Binary        Tree        Ratio
>> SWI    35.99 sec    28.41 sec    0.79
>> QP     3.34 sec    13.25 sec    3.97
>
> Without any precautions arithmetic is fully interpreted: first build the
> term N-1 then call the foreign is/2 implementation.

This is _still_ odd because all the binary version has to do is "M is N - 1", while the 'tree' version often builds more than one compound term.

By the way, it is _extremely_ unfortunate that the succ/2 predicate I invented years ago has been provided with incompatible semantics. plus/3 was invented for *signed integer* arithmetic, succ/2 was invented for *natural number* arithmetic, so that

    succ(M, N) is true when M and N are (eventually) bound to NATURAL
    NUMBERS and N = M+1.

In particular, the whole point of having succ/2 was that succ(X, 0) should *fail*.  It is extremely common in Prolog to write loops that count down to 0 and must on no account be allowed to count down to negative infinity.  It's just like n+k patterns in Haskell:

    f (n+1) = (f n) + 1
    f 0 = 1

does not go into an infinite loop in Haskell when f's argument is initially negative; it fails at once.  In the same way,

    f(N, Y) :- succ(M, N), f(M, X), plus(1, X, Y).
    f(0, 1)

was never intended to go into an infinite loop if called as f(-1, X), but to fail at once.  That is the point of succ/2.  If SWI's succ/2 is not to do this, it would be better if it had a different name, so that people who want the behaviour defined back in '83 or '84 can plug in a definition that works.

> Using -O (or the
> optimise prolog flag) it compiles it to a stack machine.  Without
> optimisation it creates garbage and will do GC.

On my machine,
    optimise        bin_down(2097150)
    false        35.99
    true        17.52

SWI Prolog is not the first Prolog system to be adversely affected by the desire to make compiled and debuggable code identical.  In one Prolog system I know of, the designer finally solved the problem to his satisfaction by compiling *two* copies of every clause, one to be used by call/1 and the other to be used by clause/2 (and the debugger).

Speaking for myself, I regard calls to user-defined "functions" in arithmetic expressions as an abomination; they should not exist, so there should be nothing for the debugger to see in them.

There are a number of intermediate designs.

One, for example, notes that the majority of calls to is/2 in the
SWI library have the form
    Var1 is Var2 + Const
or   
    Var1 is Var2 - Const   
and so creates a pair of special WAM instructions:
    is_plus <var> <var> <const>
    is_minus <var> <var> <const>
For normal execution, these instructions are executed directly. When a clause is to be interpreted by the debugger, or picked up by clause/2, the instructions have the  effect of building is(_,+(_,_)) or is(_,-(_,_)) goals.

(For what it's worth, Quintus Prolog did _not_ have such instructions.)

Another basically does
    ( '%debugging' ->                % 1 jump
      <slow space-hungry debuggable version>    % another jump
    ; <faster space-saving stack version>
    )

---

Paul Singleton wrote:
> So the special-cased implementation of 'integer' as a subtype of
> 'atomic' implies an admission by Prolog's originators that its
> support for user-defined abstract data types is inadequate?
   
Not really.  Edinburgh Prolog was influenced by Pop-2 (hence the use of square brackets for lists) and Lisp (though mostly through Pop-2). Oddly enough, if you look at the original Lisp papers, you will see that one of the uses of Lisp was to represent numbers as data structures, yet Lisp very early departed from theoretical purity and adopted native numbers. This suggests that size and speed might well have outweighed conceptual purity.  (Let's face it, conceptual purity is not where Prolog's at.)

In the original applications of Prolog at Edinburgh, integer arithmetic was important.  I suspect that it simply never occurred to Edinburgh Prolog's designers that non-binary representations for integers might be a serious possibility.  In particular, it is hard to imagine anyone writing a native- code Prolog compiler in Prolog taking seriously any suggestion that Prolog numbers might have a representation utterly unlike native numbers.

It is fair to say that Prolog's support for user-defined abstract data types was at all times nonexistent.

While at Edinburgh I did propose an extension to Prolog for 'sealing' data.  I suspect that the fire at Edinburgh has destroyed all remaining copies of that proposal.  I must admit that I was *not* inspired by thinking about numbers, but by thinking about data-base references.

> Your functor-avoidance scenario is just one instance of a dilemma
> faced by Prolog programmers when introducing an enumerated type:
> do we wrap values in a distinguishing functor, or hope that their
> type is always inferrable within context?
   
There are reasons why the Mycroft/O'Keefe type checker was written... "Wrappers" are a performance disaster. Push that idea far enough, and you arrive at Mercury.  If you want a logic programming language that combines extremely good performance with logical purity and good support for abstract data types, Mercury is worth looking at.

> Either Prolog programmers need atomic subtypes or they don't: you
> say they do, but it's just tough if they weren't in at the start
> so they could build their pet types in as special cases :-)
   
AtomIC, but not quite like atoms.  We're talking about things that _could_ be atoms (if you want to represent numbers as atoms, what's wrong with '0', '1', '2', ... '1048576' ...) or _could_ be compound terms and you not only don't want to know, you want NOT to know. "Sealed" instances of abstract data types should never be allowed as     function symbols of compound terms.

When you have a Prolog that is co-hosted with some other language, like Xerox Quintus Prolog (Lisp) or Poplog (Lisp, Pop-11, ML), it's very useful to have atomic/1 splitting into atom/1 (things that _can_ be used as function symbols of compound temrms) and others (things that cannot).  For example, in XQP, Lisp pairs, symbols, and numbers were mapped to Prolog pairs, symbols, and numbers, while everything else (streams, windows, arrays, records, processes) was carried over directly as an atomic value.

I still think that sealed terms are a good idea, but when I worked at Quintus, no customers wanted them badly enough to justify spending the time finishing the design, implementing it, and documenting it.

Two big issues with sealed terms are

1. Whether they may contain variables; it's seriously weird if something which acts atomic isn't ground. [But Mercury does mode analysis, so not a problem.]
2. Unification of representations is not the same as equality.  [But Mercury doesn't yet support partly instantiated compounds, so unification is either binding or identity testing, and with mode analysis, you know which is which, so you _could_ safely call user-defined equality predicates.  Such predicates should either succeed once or fail, and Mercury does determinism  analysis, so it knows something about which predicates might make sensible equality tests.]
   

---

---

Papers to appear in TPLP and TOCL

---

Contents

• TPLP regular papers
• Transactions On Computational Logic (TOCL) regular papers

---

http://www.cs.kuleuven.ac.be/~dtai/projects/ALP/TPLP/index.html

---

TECHNICAL NOTES

• cTI: A constraint-based termination inference tool for ISO-Prolog,
  Fred Mesnard and Roberto Bagnara.

PROGRAMMING PEARL

• Computing convex hulls with a linear solver,
  Florence Benoy and Andy King and Fred Mesnard.

BOOK REVIEWS

• Bart Demoen: Programming in Prolog. Using the ISO Standard by William F. Clocksin , Christopher S. Mellish, Springer-Verlag, 2003, ISBN 3-540-00678-8, xiii + 299 pages [html] [pdf]

REGULAR PAPERS

• On termination of meta-programs,
  Alexander Serebrenik and Danny De Schreye.
• A uniform approach to logic programming semantics,
  Pascal Hitzler and Matthias Wendt.
• Abductive Logic Programs with Penalization: Semantics, Complexity and Implementation,
  Simona Perri, Francesco Scarcello, Nicola Leone.
• Inferring Termination Conditions for Logic Programs using Backwards Analysis,
  Samir Genaim, Michael Codish.
• A Parameterised Hierarchy of Argumentation Semantics for Extended Logic Programming and its Application to the Well-founded Semantics,
  Ralf Schweimeier and Michael Schroeder.
• On Applying Or-Parallelism and Tabling to Logic Programs,
  Ricardo Rocha, Fernando Silva, Vitor Santos Costa.
• Enhanced sharing analysis techniques: a comprehensive evaluation,
  Roberto Bagnara, Enea Zaffanella, Patricia M. Hill.
• Weight constraints as nested expressions,
  Paolo Ferraris and Vladimir Lifschitz.
  
• Integrating design synthesis and assembly of structured objects in a visual design language,
  Omid Banyasad, Philip T. Cox.
  
• A treatment of higher-order features in logic programming ,
  Gopalan Nadathur.
  
• Specialization of functional logic programs based on needed narrowing ,
  Maria Alpuente, Salvador Lucas, Michael Hanus and German Vidal.
  
• Optimization of bound disjunctive queries with constraints ,
  Gianluigi Greco, Sergio Greco, Irina Trubitsyna, Ester Zumpano.
  
• Preferred answer sets for ordered logic programs ,
  Davy Van Nieuwenborgh, Dirk Vermeir.

---

---

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 4 (October 2004) (tentative)

• A theory of normed simulations, W.O.D. Griffioen and F.W. Vaandrager
• Abstract versus Concrete Computation on Metric Partial Algebras, J.V. Tucker and J.I. Zucker
• NExpTime-complete Description Logics with Concrete Domain, Carsten Lutz
• Proving correctness of Timed Concurrent Constraint Programs, Frank de Boer, Maurizio Gabbrielli and Maria Chiara Meo
• Interval Constraint Solving for Camera Control and Motion Planning, Frederic Benhamou, Frederic Goualard, Eric Languenou and Marc Christie

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

• A Classification of Symbolic Transition Systems, T.A. Henzinger, R. Majumdar and J.-F. Raskin
• Making Abstract Domains Condensing, R. Giacobazzi, F. Ranzato and F. Scozzari
• On Equivalence and Canonical Forms in the LF Type Theory, Robert Harper and Frank Pfenning
• A New Decidability Technique for Ground Term Rewriting Systems with Applications, Rakesh Verman and Ara Hayrapetyan
• A Modal Logic Framework for Multi-agent Belief Fusion, Churn-Jung Liau
• Eternity variables to prove simulation of specifications, Wim H. Hesselink
• Induction from answer sets in nonmonotonic logic programs, Chiaki Sakama
• Complexity of Nested Circumscription and Nested Abnormality Theories, Marco Cadoli, Thomas Eiter and Georg Gottlob
• From Linear Time to Branching Time, Orna Kupferman and Moshe Vardi
• Comparisons and Computation of Well-founded Semantics for Disjunctive Logic Programs, Kewen Wang and Lizhi Zhou
• Equivalences Among Aggregate Queries with Negation, Sara Cohen, Werner Nutt and Yehoshua Sagiv
• Knuth-Bendix constraint solving is NP-complete, Konstantin Korovin and Andrei Voronkov
• Reasoning about Evolving Nonmonotonic Knowledge Bases, Thomas Eiter, Michael Fink, Giuliana Sabbatini and Hans Tompits
• Minimum Model Semantics for Logic Programs with Negation-as-Failure, Panos Rondogiannis and William W. Wadge
• Datalog programs and their persistency numbers Foto Afrati, Stavros Cosmadakis and Eugenie Foustoucos
• On the Complexity of the Disjunction Property in Intuitionistic and Modal Logics Mauro Ferrari, Camillo Fiorentini and Guido Fiorino
• Disjunction and Modular Goal-directed Proof Search Matthew Stone
• Sequent and Hypersequent Calculi for Lukasiewicz and Abelian Logics George Metcalfe, Nicola Olivetti, and Dov Gabbay
• An Effective Decision Procedure for Linear Arithmetic with Integer and Real Variables Bernard Boigelot, Sebastien Jodogne and Pierre Wolper
• Arithmetic, First-Order Logic, and Counting Quantifiers Nicole Schweikardt
• Unfolding Partiality and Disjunctions in Stable Model Semantics T. Janhunen, I. Niemela, D. Seipel, P. Simons and J. You
• Predicate-calculus based logics for modeling and solving search problems Deborah East and Mirek Truszczynski
• Complexity Results on DPLL and Resolution Paolo Liberatore
• Monodic temporal resolution Anatoly Degtyarev, Michael Fisher and Boris Konev
• An Elementary Fragment of Second-Order Lambda Calculus K. Aehlig and J. Johannsen
• Heterogeneous Temporal Probabilistic Agents Juergen Dix, Sarit Kraus and VS Subrahmanian
• Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations Russell Impagliazzo and Nathan Segerlind
• Optimizing Optimal Reduction: A Type Inference Algorithm for Elementary Affine Logic Paolo Coppola and Simone Martini
• Why Are There So Many Loop Formulas? Vladimir Lifschitz and Alexander Razborov
• Decidability Results for Sets with Atoms Agostino Dovier, Andrea Formisano and Eugenio Omodeo
• Propositional computability logic I Giorgi Japaridze
• Ordinary Interactive Small-Step Algorithms, I Andreas Blass and Yuri Gurevich
• Logic Program Based Updates Yan Zhang
• Fast Verification of MLL Proof Nets via IMLL A.S. Murawski and C.-H. L. Ong
• The DLV System for Knowledge Representation and Reasoning Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, and Francesco Scarcello
• Soft Concurrent Constraint Programming S. Bistarelli, U. Montanari, and F. Rossi
• Comprehending Software Correctness Implies Comprehending an Intelligence-Related Limitation Arthur Charlesworth
• A System of Interaction and Structure Alessio Guglielmi
• Domain-Dependent Knowledge in Answer Set Planning Tran Cao Son, Chitta Baral, Nam Tran, and Sheila McIlraith
• Defining Functions on Equivalence Classes Larry Paulson
• Propositional computability logic II Giorgi Japaridze
• On Automatic Partial Orders B. Khussainov, S. Rubin and F. Stephan
• On Program Equivalence in Languages with Ground-Type References A. Murawski
• Convergence Law for Random Graphs with Specified Degree Sequence J. Lynch

---

---

The Next Logic Programming Language

Editor: Enrico Pontelli

---

Unfortunately I did not receive any submissions regarding proposals and/or discussions for the next logic programming language. I would like to use this column to reiterate my invitation to submit material for this column of the newsletter. During the last ICLP 2004 conference, I noticed a significant interest in this area, and quite a number of different opinions. Please, share them with the rest of the community! Your submissions can be as short as a couple of paragraphs (or as long as a complete paper).

---

---

Accepted Conference Papers

---

---

PADL 2005
International Symposium on Practical Aspects of Declarative Languages
Long Beach, California, January 11-12, 2005

http://www.unm.edu/~herme/padl05/

---

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.

Accepted Papers

• Role-based Declarative Synchronization for Reconfigurable Systems
• Vlad Tanasescu, EPFL
• Pawel Wojciechowski, EPFL
• Functional Framework for Sound Synthesis
• Jerzy Karczmarczuk, University of Caen
• Improved Fusion for Optimizing Generics
• Sjaak Smetsers, University of Nijmegen
• Artem Alimarine, University of Nijmegen
• Solving Constraints on Sets of Spatial Objects
• Jesus M. Almendros-Jimenez, Universidad de Almeria
• Antonio Corral, Universidad de Almeria
• A Full Pattern-based Paradigm for XML Query Processing
• Benzaken Veronique, Universite Paris XI, LRI - CNRS
• Castagna Giuseppe, CNRS - LIENS
• Miachon Cedric, LIENS - CNRS
• A Program Inverter LRinv and its Structure
• Masahiko Kawabe, Waseda University, Tokyo, Japan
• Robert Glueck, University of Copenhagen, Denmark
• Discovery of Minimal Unsatisfiable Subsets of Constraints Using Hitting Set Dualization
• James Bailey, University of Melbourne
• Peter Stuckey, University of Melbourne
• A Provably Correct Compiler for Efficient Model Checking of Mobile Processes
• Ping Yang, Computer Science Dept., Stony Brook University
• Yifei Dong, School of Computer Science, University of Oklahoma
• C.R. Ramakrishnan, Computer Science Dept., Stony Brook University
• Scott. A. Smolka, Computer Science Dept., Stony Brook University
• An Ordered Logic Program Solver
• Davy Van Nieuwenborgh, Free University Brussels
• Stijn Heymans, Free University Brussels
• Dirk Vermeir, Free University Brussels
• Type Class Directives
• Bastiaan Heeren, Universiteit Utrecht
• Jurriaan Hage, Universiteit Utrecht
• Specializing Narrowing for Timetable Generation: A Case Study
• Nadia Brauner, Laboratoire LEIBNIZ
• Rachid Echahed, Laboratoire LEIBNIZ
• Gerd Finke, Laboratoire LEIBNIZ
• Hanns GREGOR, Laboratoire LEIBNIZ
• Frederic Prost, Laboratoire LEIBNIZ
• Solving Collaborative Fuzzy Agents Problems with CLP(FD)
• Susana Munoz-Hernandez, Technical University of Madrid
• Jose Manuel Gomez-Perez, Technical University of Madrid
• Character-Based Cladistics and Answer Set Programming
• Daniel Brooks, University of Toronto
• Esra Erdem, Vienna University of Technology
• James Minett, Chinese University of Hong Kong
• Donald Ringe, University of Pennsylvania
• Towards a More Practical Hybrid Probabilistic Logic Programming Framework
• Emad Saad, New Mexico State University
• Enrico Pontelli, New Mexico State University
• Safe Programming with Pointers in ATS
• Dengping Zhu, Boston University
• Hongwei Xi, Boston University
• Improving Memory usage in the BEAM
• Ricardo Lopes, DCC-FCUP & LIACC, University of Porto - Portugal
• Vitor Costa, COPPE/Sistemas, Universidade Federal do Rio de Janeiro - Brasil
• Towards Provably Correct Code Generation via Horn Logical Continuation Semantics
• Qian Wang, UT Dallas
• Gopal Gupta, UT Dallas
• Michael Leuschel, Southampton

---

MOZ 2004
Second International Mozart/Oz Conference
Charleroi, Belgium, October 7-8, 2005

http://www.cetic.be/moz2004

---

---

---

---

COMMONSENSE 2005
7th International Symposium on Logical Formalization of Commonsense Reasoning
Corfu, Greece, May 22-24, 2005

http://www.iccl.tu-dresden.de/commonsense05/

---

One of the major long-term goals of artificial intelligence is to endow computers with commonsense reasoning capabilities. Although we know how to design and build systems that excel at certain bounded or mechanical tasks which humans find difficult, such as playing chess, we have little idea how to construct computer systems that do well at commonsense tasks which are easy for humans. Formalizing commonsense reasoning using logic-based approaches will be the focus of the symposium. Topics of interest include, but are not limited to:

• change, action, and causality
• self-aware systems
• axiomatizations of benchmark commonsense problems
• ontologies, including space, time, shape, and matter, and ontologies of networks and structures
• levels of granularity of ontology and reasoning
• large commonsense knowledge bases
• exploration of new commonsense domains in a preformal way (e.g. new microworlds or benchmark problems)
• nonmonotonic reasoning
• formal models of probabilistic reasoning
• formal theories of context
• mental attitudes including knowledge, belief, intention, and planning
• belief revision, update, and merging
• cognitive robotics
• reasoning about multi-agent systems and social interactions among agents
• applications of formal representations to applications, such as natural language processing
• other mathematical tools for capturing common-sense reasoning
  

The symposium aims to bring together researchers who have studied the formalization of commonsense reasoning. The focus of the symposium is on representation rather than on algorithms, and on formal rather than informal methods. Papers should be rigorous and concrete. Technical papers offering new results in the area are especially welcome; object level theories are preferred. We especially encourage papers on either of the two themes of this symposium, Self-awareness and the Surprise Birthday Present Problem (see below). Survey papers, papers studying the relationship between different approaches, and papers on methodological issues such as theory evaluation, are also encouraged.

Symposium Themes
There will be two themes at this year's Common Sense Symposium. We encourage papers on these two themes, and plan to organize one or more panels on these topics.

The first theme is Self-awareness: the notion of the computer having a sense of self, being conscious of its own reasoning power, and being able to explore itself in relation to other agents. We are especially interested in formal theories that represent self- awareness, and/or allow a system to reason about its own awareness.

The second theme is the Surprise Birthday Present Problem, one of the challenge problems on the Common Sense Problem Page. We encourage submission of papers that present solutions to this problem and to its listed variants. Sample solutions to other challenge problems can be found on the Common Sense Problem Page.

Submission Information
Persons wishing to make presentations at the workshop should submit papers of up to 6000 words, excluding the bibliography. Electronic submissions in pdf, are preferred; otherwise 6 hard copies of the paper are acceptable. All submissions should be sent to one of the Symposium Chairs.

Publication
The proceedings of the symposium will be published as a Dresden University Technical Report (ISSN 1430-211X). Moreover, the program chairs will invite selected authors to submit extended versions of their papers for a special issue of the Journal of Logic
and Computation.

Multiple Submissions Allowed
Papers may be submitted to Commonsense-2005 even if they have been submitted to other conferences or symposia (such as IJCAI-2005). If a paper is accepted at an archival conference such as IJCAI and is also selected by Commonsense-2005 for publication at the special journal issue, then this paper must be substantially revised and/or extended. Previously published papers are not acceptable for Commonsense-2005.

Participation
Persons wishing to attend the symposium should submit a 1-2 page research summary including a list of relevant publications. This is not required for the authors of submitted papers. Moreover PhD students need only to send the tentative title and abstract of their dissertation. All requests for attendance should be sent to one of the Symposium Chairs.

Important Dates

Paper Submission Deadline:	February 8, 2005
Paper Notification:	March 14,2005
Camera Ready Papers Due:	March 28, 2005
Symposium	May 22-24, 2005

Invited Speakers

• Peter Gardenfors, University of Lund
• Pat Hayes, University of West Florida
• John McCarthy, Stanford University
• Leora Morgenstern, IBM Watson Research

Symposium Committee

Co-Chairs
Sheila McIlraith
Dept of Computer Science
University of Toronto
6 King's College Road
Toronto, ON, Canada M4K 2W1
sheila@cs.toronto.edu

Pavlos Peppas
Dept of Business Administration
University of Patras
Patras 256 00, Greece
ppeppas@otenet.gr

Michael Thielscher
Dept of Computer Science
Dresden University of Technology
01062 Dresden, Germany
mit@inf.tu-dresden.de

---

ICALP'05
International Colloquium on Automata, Languages, and Programming
July 11-15, 2005, Lisboa, Portugal

http://icalp05.di.fct.unl.pt/

---

The 32nd International Colloquium on Automata, Languages and Programming, the main conference and annual meeting of the European Association for Theoretical Computer Science EATCS will take place from the 11th to the 15th of July 2005 in Lisboa, Portugal.
 
As a complement to the established Tracks on Algorithms, Automata, Complexity and Games (A), and on Logic, Semantics, and Theory of Programming (B), corresponding to the two main streams of the journal Theoretical Computer Science, ICALP'05 innovates on the structure of its traditional scientific program with the inauguration of a new special Track (C). The aim of Track C is to allow a deeper coverage of a particular topic, to be specifically selected for each year's edition of ICALP on the basis of its timeliness and relevance for the theoretical computer science community.
 
Papers presenting original research on all aspects of theoretical computer science are sought. Typical but not exclusive topics of interest are:
 
Track A (Algorithms, Automata, Complexity and Games):
 Giuseppe F. Italiano
 Universita di Roma "Tor Vergata", Italy (PC Chair)

• Algorithmic Aspects of Networks
• Algorithms and Data Structures
• Automata Theory and Formal Languages
• Combinatorics in Computer Science
• Computational Biology
• Computational Complexity
• Computational Geometry
• Internet Algorithmics
• Machine Learning
• Parallel and Distributed Computing
• Quantum Computing

 
Track B (Logic, Semantics, and Theory of Programming):
 Catuscia Palamidessi
 INRIA Futurs and LIX, France (PC Chair)

• Algebraic and Categorical Models
• Databases, Semi-Structured Data and Finite Model Theory
• Principles of Programming Languages
• Logics, Formal Methods and Model Checking
• Models of Concurrent, Distributed, and Mobile Systems
• Models of Reactive, Hybrid and Stochastic Systems
• Program Analysis and Transformation
• Specification, Refinement and Verification
• Type Systems and Typed Calculi

 
Track C (Security and Cryptography Foundations):
 Moti Yung
 Columbia University, USA (PC Chair)

• Cryptographic Notions, Mechanisms, Systems and Protocols
• Cryptographic Proof Techniques, Lower bounds, Impossibilities
• Foundations of Secure Systems and Architectures
• Logic and Semantics of Security Protocols
• Number Theory and Algebraic Algorithms in Cryptography
• Pseudorandomness, Randomness, and Complexity Issues
• Secure Data Structures, Storage, Databases and Content
• Security Modeling: Combinatorics, Graphs, Games, Economics
• Specifications, Verifications and Secure Programming
• Theory of Privacy and Anonymity
• Theory of Security in Networks and Distributed Computing
• Quantum Cryptography and Information Theory

 
SUBMISSIONS 
Authors are invited to submit an extended abstract of no more than 12 pages in LNCS style presenting original research on the theory of Computer Science. Submissions should indicate to which track (A, B, or C) the paper is submitted. No simultaneous submission to other publication outlets (either a conference or a journal) is allowed. The proceedings will be published in the Lecture Notes in Computer Science Series by Springer-Verlag.
 
IMPORTANT DATES

Workshop Proposals Due	November 28, 2004
Submissions	February 13, 2005
Notification	April 8, 2005
Final Version Due	April 30, 2005

---

IEA/AIE-2005
International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems
Bari, Italy, June 22-25, 2005

http://www.di.uniba.it/iea-aie/

---

IEA/AIE 2005 continues the tradition of emphasizing applications of artificial intelligence and knowledge-based systems to solve real-life problems in all areas including, engineering, science, industry, automation & robotics, business and finance, medicine & biomedicine, bioinformatics, cyberspace, and man-machine interactions.
Topics of interest include, but are not limited to:

• Adaptive Control
• Intelligent Interfaces
• Applications to Design
• Intelligent Systems In Education
• Applications to Manufacturing
• Internet Applications
• Autonomous Agents
• KBS Methodology
• BioInformatics
• Knowledge Management
• Case-based Reasoning
• Knowledge Processing
• Computer Vision
• Machine Learning
• Constraint Satisfaction
• Model-based Reasoning
• Data Mining & Knowledge Discovery
• Natural Language Processing
• Decision Support
• Neural Networks
• Distributed Problem Solving
• Planning and Scheduling
• Expert Systems
• Reasoning Under Uncertainty
• Fuzzy Logic
• Spatial Reasoning
• Genetic Algorithms
• Speech Recognition
• Genetic Programming
• System Integration
• Heuristic Search
• Systems for Real Life Applications
• Human-Robot Interaction
• Temporal Reasoning

Submission Process and Schedule
Authors are invited to submit their paper, written in English, of up to 10 pages, presenting the results of original research or innovative practical applications relevant to the conference. Practical  experiences with state-of-the-art AI methodologies are also acceptable when they reflect lessons of unique value to the conference attendees.
Shorter works, up to 6 pages, to be presented in 10 minutes, may be submitted as SHORT PAPERS representing work in progress or suggesting possible research directions. (Please, indicate "short paper" exclusively in the comments text-area of the submission form).
All papers will have to be submitted electronically through the web-based system,
following the instructions therein. Paper submission is required by November 8, 2004. All papers will be formally peer reviewed.
Notification of the results of the review process will be made by January 17, 2005; final copies of papers for inclusion in the
conference proceedings will be due by February 25, 2005.
All submitted papers must be (strictly) in PDF format. The papers must be prepared in MS Word or LaTeX, complying to Springer's LNCS style (see the typesetting guidelines mentioned below). All papers must provide a key word list including one or more of the topics listed above.
The bundle of the final version of the accepted papers will require the sources used during the preparation as well as the files of
the figures, etc...
The conference proceedings, published in a bound volume by Springer-Verlag in their 'Lecture Notes in Artificial Intelligence'
series will be available at the conference (see the typesetting guidelines at the publisher's site
Referees will be asked to nominate papers for a Best Paper award to be announced at the conference. All papers, but particularly those nominated for the Best Paper competition, will be automatically considered for publication in an expanded form in the International Journal of Applied Intelligence.

IMPORTANT DATES

Paper Submission Deadline	November 8, 2004
Notification of Review Results	January 17, 2005
Final Paper Submission Deadline	February 25, 2004

---

International Conference on Computing Frontiers
Ischia, Italy, May 4-6, 2005

http://www.computingfrontiers.org/

---

The increasing needs of present and future computation-intensive applications have stimulated research in new and innovative approaches to the design and implementation of high-performance computing systems. This challenging boundary between state of the art and innovation constitutes the computing frontiers, which needs to push forward and provide the computational support required for the advancement of all science domains and applications. This conference will focus on a wide spectrum of advanced technologies and radically new solutions and is designed to foster communication between the various scientific areas and disciplines involved.

Authors are invited to submit papers on all areas of innovative computing systems which extend the current frontiers of computer science and engineering and that will provide advanced systems for current and future applications.

Papers are sought on theory, methodologies, technologies, and implementations concerned with innovations in computing paradigms, computational models, architectural paradigms, computer architectures, development environments, compilers, operating environments, etc. Papers should be submitted to one of the following tracks:

1. Non-conventional computing
2. Grid computing
3. High performance embedded architectures
4. Reconfigurable computing
5. Supercomputing
6. Autonomic and Organic computing
7. Compilers and Operating Systems
8. Pervasive computing
9. Architectures and devices for emerging nanotechnologies
10. Workload characterization of emerging applications
11. SOC architectures
12. Temperature, energy, and complexity-aware designs
13. Special purpose architectures
14. Quantum computing
15. Open topics
    

Papers with new ideas and perspectives on computing are more than welcome.
Full papers should be submitted through the Conference Submission Page. Papers should be no longer than 6000 words, single-column and double-spaced, and in PDF format (printable with Acrobat Reader).

PAPER SUBMISSION DEADLINE IS DECEMBER 6, 2004. Acceptance/rejection will be emailed by January 17, 2005. The final manuscript will due February 21, 2005. Submission implies that at least one author will register at the conference and present the paper.

---

RULE'05
6th International Workshop on Rule-Based Programming
Nara, Japan, April 23, 2005

http://rule2005.loria.fr/

---

Scope:
Rule-based programming is currently experiencing a renewed period of growth with the emergence of new concepts and systems that allow a better understanding and better usability. On the theoretical side, after the in-depth study of rewriting concepts during the eighties, the nineties saw the emergence of the general concepts of rewriting logic and of the rewriting calculus. On the practical side, new languages and systems such as ASF+SDF, BURG, CHRS, Claire, ELAN, Maude, and Stratego have shown that rules are a useful programming tool.
The practical application of rule-based programming prompts research into the algorithmic complexity and optimization of rule-based programs as well as into the expressivity, semantics and implementation of rule-based languages.

The purpose of this workshop is to bring together researchers from the various communities working on rule-based programming to foster fertilisation between theory and practice, as well as to favour the growth of this programming paradigm.
The previous editions of the RULE workshop were held in Aachen (2004) and Valencia (2003) during the RDP conference  "Rewriting, Deduction and Programming", and Pittsburg (2002), Firenze (2001), and Montreal (2000) during the PLI conference "Principles, Logics, and Implementations of high-level programming languages".

See http://rewriting.loria.fr (Item "Venues") for more details about these workshops.

We solicit original papers on all topics of rule-based programming, including but not restricted to

• Languages for rule-based programming
• Expressivity
• Semantics
• Implementation techniques
• Applications of rule-based programming
• Analysis of rule-based programs
• Programming methods
• Environments for rule-based programming
• (Partial) Evaluation 
• Abstract machines for rewriting
• Combination of rule-based programming with other paradigms
• System descriptions

Submission procedure and publication:  
Papers (of at most 15 pages) should be submitted electronically as PostScript or PDF files to one of the program committee chairs: Horatiu Cirstea (Horatiu.Cirstea@loria.fr) or Narciso Marti-Oliet (narciso@sip.ucm.es). The message should also contain a text-only abstract and author information.
Papers should be received by January 31, 2005.
 Accepted papers will be published in the preliminary proceedings volume, which will be available during the workshop. Publication of the final proceedings in Electronic Notes in Theoretical Computer Science (ENTCS) is anticipated.

Workshop organizers:
Horatiu Cirstea, LORIA & Universite Nancy II, France
Narciso Marti-Oliet, Universidad Complutense de Madrid, Spain

Program Committee:

Important dates:

Deadline for Submissions	January 31, 2005
Notification of Acceptance	March 8, 2005
Camera-ready Papers	March 21, 2005
Workshop	April 23, 2005

---

QAPL 2005
Workshop on Quantitative Aspects of Programming Languages
Edinburgh, Scotland, April 2-3, 2005
http://www.doc.ic.ac.uk/~qapl05

---

Overview:
Quantitative aspects of computation are important and sometimes essential in characterising the behaviour and determining the properties of systems. They are related to the use of physical quantities (time, bandwidth, etc.) as well as mathematical quantities (probabilities, rates, etc.). Such quantities play a central role in defining both the model of systems (architecture, language design, semantics) and the methodologies and tools for the analysis and verification of system properties.

The aim of this workshop is to discuss the explicit use of quantitative information such as time and probabilities either directly in the model or as a tool for the analysis of systems. In particular, the workshop focuses on

• the design of probabilistic and real-time languages and the definition of semantical models for such languages;
• the discussion of methodologies for the analysis of probabilistic and timing properties (e.g. security, safety, schedulability);
• the probabilistic analysis of systems which do not explicitly incorporate quantitative aspects (e.g. performance and reliability
• analysis);
• applications to safety-critical systems, communication protocols, asynchronous hardware, etc.
  

Topics include (but are not limited to) probabilistic and timing aspects in:

Language design	Performance analysis
Language extension	Program analysis
Language expressiveness	Testing
Semantics	Model-checking
Coordination models	Refinement
Distributed systems	Verification
Time-critical systems	Security
Asynchronous Hardware	Safety
Multi-tasking systems	Scheduling theory

Invited Speakers:

Submission:
There will be two types of submissions:

1. Full papers of at most 15 pages in A4 format. The use of the ENTCS style files is strongly recommended. Submissions should arrive by Sunday 14 December 2004. Authors will be notified of the acceptance or rejection of their papers by Tuesday 22 January 2005. Final versions of accepted papers must be received in camera-ready and electronic form by Monday 14 February 2005.
2. Extended abstracts of ongoing work of at most 5 pages in length. The deadline for submission is Tuesday 1 February 2005. On the basis of available time a selection of these abstracts will be invited for presentation at the workshop. The authors will be informed about a decision by Tuesday 15 February 2005.
   

Publication Policy:
All accepted (full) papers will be published as an ENTCS volume. As for QAPL 2004 we will pursue the publication of the best papers and abstracts presented at the workshop in a special issue of TCS.

Important Dates:

Sunday 14 December 2004	Submission deadline (full papers)
Friday 22 January 2005	Acceptance/Rejection notification
Tuesday 1 February 2005	Submission deadline (abstracts)
Monday 14 February 2005	Camera-ready version due
Tuesday 15 February 2005	Selection of abstracts

---

ICCS 2005
International Conference on Computational Science
Atlanta, May 22-25, 2005

http://www.iccs-meeting.org/

---

You are invited to submit a paper and/or a proposal to organize a workshop at ICCS 2005, Altanta, USA, May 22-25, 2005. Please see http://www.iccs-meeting.org/ for more information.

The theme for ICCS 2005 in Atlanta, USA, is "Advancing Science through Computation", to mark several decades of progress in
computational science theory and practice, leading to greatly improved applications science.

Original contributions not exceeding 8 pages are invited for publication and oral presentation. All accepted papers will be printed in the conference proceedings published by Springer-Verlag in the Lecture Notes in Computer Science series. Selected papers will also be published as special issues of appropriate journals.

Topics of Interest
ICCS 2005 invites original contributions on all topics related to computational science, including, but not limited to:

• Scientific Computing
• Problem Solving Environments
• Advanced Numerical Algorithms
• Complex Systems: Modeling and Simulation
• Hybrid Computational Methods
• Computational Science in Data Mining/Information Retrieval
• Web- and Grid-based Simulation and Computing
• Parallel and Distributed Computing
• Visualization in Computational Science
• Applications of Computation as a Scientific Paradigm
• New Algorithms for Computational Kernels and Applications
• Education in Computational Science
  

Important deadlines:

Proposals for Workshops:	November 8, 2004
Full papers submission:	December 1, 2004
Notification of acceptance of papers:	January 31, 2005
Camera ready papers:	February 14, 2005
Early registration:	March 30, 2005

Contact and Organization:

Scientific Chair	Vaidy Sunderam
Workshops Chair	Dick van Albada
Overall Co-chair	Jack Dongarra
Overall Chair	Peter M.A. Sloot

---

CADE 2005
International Conference on Automated Deducation
Tallinn, Estonia, July 22-27, 2005
http://sise.ttu.ee/it/cade

---

CADE is the major forum for the presentation of research in all aspects of automated deduction.

• Logics of interest include propositional, first-order, equational, higher-order, classical, intuitionistic, constructive, modal, temporal, many-valued, substructural, description, and meta-logics, logical frameworks, type theory and set theory.
• Methods of interest include saturation, resolution, tableaux, sequent calculi, term rewriting, induction, unification, constraint solving, decision procedures, model generation, model checking, natural deduction, proof planning, proof presentation, proof checking, and explanation.
• Applications of interest include hardware and software development, systems analysis and verification, deductive databases, functional and logic programming, computer mathematics, natural language processing, computational linguistics, robotics, planning, knowledge representation, and other areas of AI.

Paper submission: 
Submission is electronic in postscript or PDF format. Submitted papers must conform to the Springer LNCS style, preferrably using LaTeX2e and the Springer llncs class files.  Submissions can be full papers , for work on foundations, applications or implementation techniques (15 pages), as well as system descriptions (5 pages), for describing publicly available systems.  For further information and submission instructions, see the CADE-20 web page: http://sise.ttu.ee/it/cade.
 
Important dates: 
 

E-submission of title and abstract:	February 25, 2005
E-submission papers:	March 4, 2005
Notification of acceptance:	April 22, 2005
Final version due:	May 20, 2005
Workshops and tutorials:	July 22-23, 2005
Conference:	July 24-27, 2005

      
Invited talks:
Invited talks will be given at CADE-20 by Randal Bryant (CMU), Gilles Dowek (Ecole Polytechnique) and by Frank Wolter (U. Liverpool).
 
Organizing Chair: Tanel Tammet (Tallinn TU)  
Workshop and Tutorial Chair: Frank Pfenning (CMU)  
Program Chair: Robert Nieuwenhuis (UPC Barcelona)  
Publicity Chair: Brigitte Pientka (McGill) 
 

---

LICS 2005
20th IEEE Symposium on Logic in Computer Science
Chicago, Illinois, June 26-29, 2005

http://www.lfcs.informatics.ed.ac.uk/lics/

---

The LICS Symposium is an annual international forum on theoretical and practical topics in computer science that relate to logic broadly construed.  We invite submissions on topics that fit under that rubric.
Suggested, but not exclusive, topics of interest for submissions include: automata theory, automated deduction, categorical models and logics, concurrency and distributed computation, constraint programming, constructive mathematics, database theory, domain theory, finite model theory, formal aspects of program analysis, formal methods, hybrid systems, lambda and combinatory calculi, linear logic, logical aspects of computational complexity, logics in artificial intelligence, logics of programs, logic programming, modal and temporal logics, model checking, probabilistic systems, process calculi, programming language semantics, reasoning about security, rewriting, specifications, type systems and type theory, and verification.  We welcome submissions in emergent areas, such as bioinformatics and quantum computation, if they have a substantial connection with logic.

Important Dates: 
Authors are required to submit a paper title and a short abstract of about 100 words  before submitting the extended abstract of the
paper. All submissions will be electronic.

Titles & Short Abstracts Due	January 5, 2005
Extended Abstracts Due	January 10, 2005
Author Notification	March 18, 2005
Camera-ready Papers Due	April 8, 2005

All deadlines are firm; late submissions will not be considered. Detailed information about electronic paper submission will
be posted at the LICS website.

Submission Instructions: 
Every extended abstract  must be submitted in the IEEE Proceedings two-column camera-ready format.  It must be in English and provide sufficient detail to allow the program committee to assess the merits of the paper.  It should begin with a succinct statement of the issues, a summary of the main results, and a brief explanation of their significance and relevance to the conference and to computer science, all phrased for the non-specialist. 
Technical development directed to the specialist should follow. References and comparisons with related work should be
included.  

Extended abstracts may be no longer than 10 pages including references, and must be formatted in the IEEE Proceedings two-column camera-ready style (IEEE style files will be accessible from the LICS website).  If necessary, detailed proofs of technical results can be included in a clearly-labelled appendix in the same two-column format following the 10-page extended
abstract or there can be a pointer to a manuscript on a web site.  This material may be read at the discretion of the program committee. Extended abstracts not conforming to the above requirements concerning format and length may be rejected without further consideration.

The results must be unpublished and not submitted for publication elsewhere, including the proceedings of other symposia or workshops. The PC chair should be informed of closely related work submitted to a conference or journal between 10th January  2005 and 18th March 2005. All authors of accepted papers will be expected to sign copyright release forms.  One author of each accepted paper will be expected to present it at the conference.

Short Presentations: 
LICS 2005 will have a session of short (5--10 minutes) presentations.  This session is intended for descriptions of work in progress, student projects, and relevant research being published elsewhere; other brief communications may be acceptable.  Submissions for these presentations, in the form of short abstracts (1 or 2 pages long), should be entered at the LICS 2005 submission site between 19th March and 25th March 2005.  Authors will be notified of acceptance or rejection by
1st April 2005.

Kleene Award for Best Student Paper: 
An award in honour of the late S.C. Kleene will be given for the best student paper, as judged by the program committee.  Details concerning eligibility criteria and procedure for consideration for this award will be posted at the LICS website.  The program committee may decline to make the award or may split it among several papers.

Affiliated Workshops: 
As in previous years, there will be a number of workshops affiliated with LICS 2005; information will be posted at the LICS website.

Sponsorship: 
The symposium is sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing in cooperation with the Association for Symbolic Logic, and the European Association for Theoretical Computer Science.

---

CAV 2005
International Conference on Computer-Aided Verification
Edinburgh, Scotland, July 6-10, 2005

http://www.cav2005.inf.ed.ac.uk/

---

Aims and Scope:
CAV'05 conference is the 17th in a series dedicated to the advancement of the theory and practice of computer-assisted formal analysis methods for software and hardware systems.  The conference covers the spectrum from theoretical results to concrete applications, with an emphasis on practical verification tools and the algorithms and techniques that are needed for their implementation.  The proceedings of the conference will be published in the Springer-Verlag Lecture Notes in Computer Science
series. Sample topics of interest include:

• Algorithms and tools for verifying models and implementations
• Deductive, compositional, and abstraction techniques for verification
• Modeling and specification formalisms
• Program analysis and software verification
• Testing and runtime analysis based on verification technology
• Applications and case studies
• Verification in industrial practice

Special Events:
Invited speakers for CAV'05 are:

• Bob Bentley (Intel Corp.), "Validating a modern microprocessor".
• Bud Mishra (N. Y. U.), "What's Next? Challenges from Systems Biology."
• George Necula (U.C. Berkeley), "Randomized algorithms for program analysis and verification".

CAV will be preceded by invited tutorials on:

• "Automated Abstraction Refinement" by Thomas Ball (Microsoft Research) and Ken McMillan (Cadence);
• "Theory and practice of decision procedures for combinations of theories", by Clark Barrett (N.Y.U.) and Cesare Tinelli (U. Iowa);

The conference will be followed by a number of special workshops and events including:

• BMC'2005: 3rd Int. Workshop on Bounded Model Checking;
• PDPAR'2005:3rd Workshop on Pragmatics of Decision Procdures in Automated Reasoning;
• SoftMC'2005: 3rd Workshop on Software Model Checking;
• "Satifiability Modulo Theories Competition", a special tools competition.
• (plus other possible workshops and events)

Paper submission:
There are two categories of submissions:
Regular papers. 
Submissions, not exceeding thirteen (13) pages using Springer's LNCS format, should contain original research, and sufficient detail to assess the merits and relevance of the contribution.
For papers reporting experimental results, authors are strongly encouraged to make their data available with their submission.
Simultaneous submission to other conferences with proceedings or submission of material that has already been published elsewhere is not allowed.
Tool presentations. 
Submissions, not exceeding four (4) pages using Springer's LNCS format, should describe the implemented tool and its novel features. A demonstration is expected to accompany a tool presentation. Papers describing tools that have already been presented in this conference before will be accepted only if significant and clear enhancements to the tool are reported and implemented.

Information concerning the procedure for submissions will be available on the conference home page 

Important dates:

Paper submission (strict):	January 21, 2005
Notification of acceptance/rejection:	March 25, 2005
Final version due:	April 29, 2005

Program Chairs:
Kousha Etessami, University of Edinburgh  kousha@inf.ed.ac.uk  
Sriram Rajamani, Microsoft Research  sriram@microsoft.com

---

Coordination 2005
International Conference on Coordination Languages and Models
Namur, Belgium, April 20-23, 2005

http://www.coordination2005.org/

---

IMPORTANT DATES

Submission of abstract:	December 15, 2004
Submission of papers:	December 21, 2004
Notification of acceptance:	February 1, 2005
Final version:	February 15, 2005
Conference:	April 20-23, 2005

CONFERENCE GOALS
Modern information systems rely increasingly on combining concurrent, distributed, mobile, reconfigurable and heterogenous components. New models, architectures, languages, verification techniques are necessary to cope with the complexity induced by the demands of today's software development. Coordination languages have emerged as a successful approach, in that they provide abstractions that cleanly separate behavior from communication, therefore increasing modularity, simplifying reasoning, and ultimately enhancing software development.

Building on the success of the previous editions, this conference provides a well-established forum for the growing community of
researchers interested in models, languages, architectures, and implementation techniques for coordination.

PREVIOUS EDITIONS
The previous editions of COORDINATION took place in Cesena (Italy), Berlin (Germany), Amsterdam (Netherlands), Limassol (Cyprus), York (UK), and Pisa (Italy). More details are available at http://music.dsi.unifi.it/coordination.

TOPICS OF INTEREST
They include but are not limited to:

• Theoretical models and foundations for coordination: component composition, concurrency, mobility, dynamic aspects of coordination, emergent behavior.
• Specification, refinement, and analysis of software architectures: patterns and styles, verification of functional and non-functional properties
• Coordination, architectural, and interface definition languages: implementation, interoperability, heterogeneity.
• Multiagent systems and coordination: models, languages, infrastructures.
• Dynamic software architectures: mobile code and agents, configuration, reconfiguration, self-organization.
• Coordination and modern distributed computing: Web services, peer-to-peer networks, grid computing, context-awareness, ubiquitous computing.
• Programming languages, middleware, tools, and environments for the development of coordinated applications
• Industrial relevance of coordination and software architectures: programming in the large, domain-specific software architectures and coordination models, case studies.
• Interdisciplinary aspects of coordination

<>PROCEEDINGS
The conference proceedings are expected to be published by Springer, in the Lecture Notes in Computer Science (LNCS) series. Proceedings of the previous editions of this conference are also available in the LNCS series: volumes 1061, 1282, 1594, 1906, 2315, and 2949.
A selection of the best papers will also be considered for publication in a special issue of a major journal.

SUBMISSION INSTRUCTIONS
Authors are invited to submit full papers electronically in PostScript or PDF using a two-phase online submission process. Registration of the paper information and abstract (max. 250 words) must be completed before December 15, 2004. Submission of the full paper is due no later than December 21, 2004. Submission will be handled through a conference management system: instructions will be published at http://www.coordination2005.org.

Submissions must be formatted according to the LNCS guidelines (see http://www.springer.de/comp/lncs/authors.html) and must not exceed 15 pages in length. Papers that are not in the requested format or significantly exceed the mandated length may be rejected without going through the review phase.

Submissions should explicitly state their contribution and their relevance to the theme of the conference. Other criteria for selection
will be originality, significance, correctness, and clarity.
Simultaneous or similar submissions to other conferences or journals are not allowed.

CONFERENCE LOCATION
The conference will be hosted by the Institute of Informatics at the University of Namur, Belgium.
Capital of the Walloon Region, Namur is a beautiful city of 80.000 inhabitants. Its position at the confluent of two rivers gave it
military and economic appeal, exploited by the Roman Empire and by many others since then. Much evidence of Namur's past can be visited nowadays, including the citadel, one of the greatest in Europe.
Close to Brussels (60 km) and at the intersection of European railways and highways, Namur can be easily reached by road, train, and plane.

CO-CHAIRS
Jean-Marie Jacquet University of Namur, Belgium
<>Gian Pietro Picco Politecnico di Milano, Italy

---

RTA'05
International Conference on Rewriting Techniques and Applications
Nara, Japan, April 19-21, 2005

http://www-i2.informatik.rwth-aachen.de/RTA05/

---

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).

IMPORTANT DATES:

• Nov 12, 2004: Deadline for electronic submission of title and abstract
• Nov 19, 2004: Deadline for electronic submission of papers
• Jan 14, 2005: Notification of acceptance of papers
• Feb 4, 2005: Deadline for final versions of accepted papers
• Apr 19-21, 2005: Conference

The deadlines are strict.

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):

• APPLICATIONS:
• case studies; rule-based (functional and logic) programming;
• symbolic and algebraic computation; theorem proving;
• system synthesis and verification; proof checking.
• FOUNDATIONS:
• matching and unification; narrowing; completion techniques;
• strategies; constraint solving; explicit substitutions; tree automata.
• FRAMEWORKS:
• string, term, and graph rewriting; lambda-calculus and
• higher-order rewriting; proof nets; constrained
• rewriting/deduction; categorical and infinitary rewriting.
• IMPLEMENTATION:
• compilation techniques; parallel execution; rewriting tools.
• SEMANTICS:
• equational logic; rewriting logic.

INVITED TALKS 
Invited talks will be given at RTA'05 by:

• Amy Felty (Ottawa)
• Yoshihito Toyama (Sendai)
• Philip Wadler (Edinburgh)

BEST PAPER AWARDS AND TRAVEL GRANTS:
An award of 100,000 Yen will be given to the best paper or papers as decided by the PC. 

A limited number of student travel grants is available. Preference will be given to students whose papers are accepted at RTA and who do not have alternative funding. Students applying for travel support should indicate this by sending an e-mail to the PC chair (giesl@informatik.rwth-aachen.de) together with their submission.


RTA'04 PROGRAM COMMITTEE:

RTA'05 SUBMISSIONS:
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.

LOCATION, TRAVEL, ACCOMMODATION, AND REGISTRATION
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.

RTA'05 PROGRAM CHAIR:
Juergen Giesl
LuFG Informatik II 
RWTH Aachen
giesl@informatik.rwth-aachen.de

RTA'05 CONFERENCE CHAIR:
Hitoshi Ohsaki
AIST, Japan
ohsaki@ni.aist.go.jp

---

SAT 2005
8th International Conference on Theory and Applications of Satisfiability Testing
St. Andrews, Scotland, June 19-23, 2005

http://www.satisfiability.org/SAT05/

---

The International Conference on Theory and Applications of Satisfiability Testing is the primary annual meeting for researchers studying the propositional satisfiability problem (SAT).  Located in the historic town of St Andrews, SAT 2005 will feature technical paper and poster sessions, invited talks, and the annual SAT Solver Competition and QBF Solver Evaluation.   We welcome submissions on SAT from any discipline with an interest in the problem, including theoretical, experimental and applied work. Topics of interest include, but are not limited to:

• Proof Systems and Proof Complexity
• Search Algorithms and Heuristics
• Analysis of Algorithms  
• Theories beyond the propositional
• Hard Instances ; Random Formulas
• Problem Encodings
• Industrial Applications
• Solvers and other tools
• Case Studies and Empirical results

ARTICLE SUBMISSION
Accepted papers will be collected together and distribued at the conference in a LNCS volume. All submissions must be 15 pages or less in the Springer-Verlag LNCS style (http://www.springer.de/comp/lncs/authors.html)
All appendices, tables, figures and the bibliography must fit into the 15 page limit.  Submissions deviating from this requirement may be rejected without review.  Submission will be in electronic form as PDF files, and authors should refer to the conference web site (http://www.satisfiability.org/SAT05) for details.  Authors are asked to register their papers on the web site one week before the submission deadline. All submissions will be reviewed by three members of the program committee, and may be accepted for either a paper or poster presentation.

ASSOCIATED SOLVER COMPETITIONS
Associated with the conference are the 2005 SAT Solver Competition and the 2005 QBF Solver Evaluation.  The SAT competition and QBF evaluation organizers welcome submissions of for both SAT and QBF, benchmark instances, as well as SAT and QBF solvers.  For details see the 2005 SAT Solver Competition web page, http://satlive.org/SATCompetition/2005, and the 2005 QBF Solver Evaluation web page http://satlive.org/QBFEvaluation/2005.

IMPORTANT DATES

Electronic Registration	February 13
Paper Submission:	February 20
SAT and QBF Solver/Benchmark Submission:	February 23
Notification of Acceptance:	April 8
Camera Ready Deadline:	April 22
Conference:	June 19-23

CONFERENCE ORGANIZERS

---

AAAI 2005
20th National Conference on Artificial Intelligence
Pittsburgh, Pennsylvania, July 9-13, 2005

http://www.aaai.org/Conferences/National/2005/aaai05.html

---

AAAI-05 is the Twentieth National Conference on Artificial Intelligence (AI). The purpose of this conference is to promote research in AI and scientific interchange among AI researchers, practitioners, and scientists and engineers in related disciplines. AAAI-05 will have multiple technical tracks, poster sessions, invited speakers, and exhibit programs, all selected according to the highest reviewing standards.

The conference provides a forum for a broad range of topics, including (but not limited to) knowledge representation, machine learning, autonomous agents, planning, machine perception, robotics, expert systems, theorem proving, common- sense reasoning, probabilistic inference, constraint satisfaction, game playing, automated diagnosis, data mining, natural language processing, neural networks, reinforcement learning, semantic web, information integration and cognitive modeling.

As the national conference for all of AI, AAAI encourages the presentation of results both from core AI technical areas and from efforts to synthesize and unify approaches to the problems faced by intelligent systems. Contributions involving the role of AI techniques and systems in other emerging areas of computer science, science, and society (such as the Web, grid computing, biotechnology, health care, and sensory networks in physical environments, to name just a few) are particularly encouraged.

In addition to normal technical papers, this year, we also specifically encourage vision/challenge papers that lay out near-term directions for particular subfields of AI.

TIMETABLE FOR AUTHORS

• January 14, 2005 to March 18, 2005: Authors register on the AAAI web site
• March 18, 2005: Electronic submission of abstract.
• March 22, 2005: Electronic submission of paper.
• March 29, 2005: Submitters fax/mail one formatted title page, including tracking number, title, authors, and contact information
• April 29, 2005: Notification of acceptance or rejection
• May 10, 2005: Final, corrected PDF camera-ready copy due at AAAI office

Author Registration
Authors must register at the AAAI-05 web-based technical paper submission site. The software will assign a password, which will enable the author to log on to submit an abstract and paper. In order to avoid a rush at the last minute, authors are encouraged to register as soon as the software is available, scheduled for January 14, 2005.

Paper Submission
Electronic paper submission is required. Instructions about how to submit papers electronically are available at the AAAI web site (www.aaai.org/Conferences/National/ 2005/). Papers may be no longer than 6 pages including references, and formatted in AAAI two-column, camera-ready style. We cannot accept submissions by e-mail or fax. Reviewing for AAAI-05 will be blind to the identities of the authors. Details on formatting and preparing the paper for blind review can be found at the AAAI-05 web site.

Authors should submit abstracts by March 18, 2005 and papers by March 22, 2005. The software will assign paper ID number at the time of the submission. Vision/challenge papers should be clearly marked as such by selecting the keyword "vision/challenge" in addition to any applicable technical keywords.

Authors will receive confirmation of receipt of their papers shortly after submission. AAAI will contact authors again only if problems are encountered with papers. Inquiries regarding lost papers must be made no later than March 29, 2005.

Title Page Submission
Authors are also requested to submit one copy of the formatted version of their title page, including authors and affiliations, no later than March 29, 2005. This title page should also include the paper ID number assigned by the submission software. This page will be retained by the AAAI office for author identification and author order. Please note that author information should not be included on the PDF of the full paper submitted electronically for review because AAAI-05 papers will have a blind review. Please send title pages to:

AAAI-05
445 Burgess Drive, Suite 100
Menlo Park, CA 94025-3442
Telephone: 650-328-3123
Fax: 650-321-4457

Submissions to Other Conferences or Journals

Papers submitted to this conference must not have been accepted for publication elsewhere or be under review for another AI conference. However, to encourage interdisciplinary contributions, we may consider work that has been submitted or presented in part to a forum outside of AI. The guidelines of the AAAI policy on multiple submissions are fully detailed at the AAAI-05 web site and must be carefully followed.

Review Process

Program committee members will identify papers they are qualified to review based on the information submitted electronically (the paper's title, keywords, and abstract). Their reviewing will be done blind to the identities of the authors and their institutions. The program committee's reviews will make recommendations to the senior program committee, which in turn will make recommendations to the program cochairs. Although the program cochairs will formally make all final decisions, in practice almost all will be made earlier in the process.

This year, as an experiment, the cochairs are planning to allow authors of papers that may have conflicting reviews, a limited opportunity to respond to the reviews. This author's feedback may then be taken into account in making the final decisions. Further details on this specific "if controversial, hear the authors" idea will be made available on the AAAI-05 website.

Copyright

Authors will be required to transfer copyright of their paper to AAAI.
Authors of all accepted papers will have a chance to present their work both orally and again in a pan-conference poster session.

---

PPDP 2005
International Symposium on Principles and Practice of Declarative Programming
Lisbon, Portugal, July 11-13, 2005

http://www.site.uottawa.ca/~afelty/ppdp05/

---

Scope of the Conference

PPDP 2005 aims to provide a forum that brings together those in the declarative programming communities, including those working in the logic, constraint and functional programming paradigms. The goal is to stimulate research in the use of logical formalisms and methods for specifying, performing, and analyzing computations, and to stimulate cross-fertilization by including work from one community that could be of particular interest and relevance to the others.

Topics of more specific interest are enhancements to such formalisms with mechanisms for mobility, modularity, concurrency, object-orientation, and static analysis, as well as the fuller exploitation of the programming-as-proof-search framework through new designs and improved implementation methods. At the level of methodology, the use of logic-based principles in the design of tools for program development, analysis, and verification relative to all declarative paradigms is of interest. Papers related to the use of declarative paradigms and tools in industry and education are especially solicited. This list is not exhaustive: submissions related to new and interesting ideas relating broadly to declarative programming are encouraged. Prospective authors are encouraged to communicate with the Program Chair about the suitability of a specific topic.

Submission Guidelines

Papers should be submitted electronically by 13 February 2005 via the symposium's web page (to be available soon). Acceptable formats are PostScript or PDF, viewable by gv. Submissions should not exceed 12 pages (including bibliography and appendices) in standard ACM conference format. They must be written in English, must have a cover page with an abstract of up to 200 words, keywords, postal and electronic mailing addresses, and phone and fax numbers of the corresponding author.

Evaluation of Submissions

Submitted papers will be judged on the basis of significance, relevance, correctness, originality, and clarity. They should include a clear identification of what has been accomplished and why it is significant. They must describe original, previously unpublished work that has not been simultaneously submitted for publication elsewhere. Authors who wish to provide additional material to the reviewers beyond the 12-page limit can do so in clearly marked appendices: reviewers are not required to read such appendices. Submissions that do not meet these guidelines may not be considered.

Proceedings

Proceedings will be published by ACM Press. ACM formatting guidelines are available at http://www.acm.org/sigs/pubs/proceed/template.html, along with formatting templates or style files for LaTeX, Word Perfect, and Word. Authors of accepted papers will be required to sign the ACM copyright form. Information on SIGPLAN's Republication Policy is available on the web.

Related Events

PPDP 2005 will be co-located with the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), which will take place 11-15 July 2005.

---

---