Manfred Droste, Yuri Gurevich (editors):

Semantics of Programming Languagesand Algebra

Dagstuhl-Seminar-Report; 6507.06.-11.06.93 (9323)

ISSN 0940-1121

Copyright © 1993 by IBF I GmbH, Schloss Dagstuhl, D-66687 Wadern, GermanyTeI.: +49-6871 - 2458Fax: +49-6871 - 5942

Das Internationale Begegnungs- und Forschungszentrum für Informatik (IBFI) ist eine gemein-nützige GmbH. Sie veranstaltet regelmäßig wissenschaftliche Seminare, welche nach Antragder Tagungsleiter und Begutachtung durch das wissenschaftliche Direktorium mit persönlicheingeladenen Gästen durchgeführt werden.

Vera: nwortlich für das Programm ist das Wissenschaftliche Direktorium:Prof. Dr. Thomas Beth.,

Prof. Dr.-Ing. Jose Encamacao,Prof. Dr. Hans Hagen,Dr. Michael Laska,Prof. Dr. Thomas Lengauer,Prof. Dr. Wolfgang Thomas,Prof. Dr. Reinhard Wilhelm (wissenschaftlicher Direktor)

Gesellschafter: Universität des Saarlandes, �

Universität Kaiserslautern,Universität Karlsruhe,Gesellschaft für Informatik e.V., Bonn

Träger: Die Bundesländer Saarland und Rheinland-Pfalz

Bezugsadresse: Geschäftsstelle Schloss DagstuhlUniversität des SaarlandesPostfach 1150

D-66041 Saarbrücken, GermanyTeI.: +49 -681 - 302 - 4396

Fax: +49 -681 - 302 - 4397

e-mail: x)�ice@dag.uni-sb.de

Semantics of Programming Languagesand Algebra

Organized by:

MANFRED DROSTE (Universität Essen)YURI GUREVICH (University of Michigan)

June 6-11, 1993

The theme of the conference was the interplay between various approaches to the semantics of

programming languages and the mathematical areas of logic (especially model theory) and algebra.The topics of the 26 talks included

1. questions of de�nability in �rst-order logic and its various extensions (�xed-point logic, gener-alized quanti�ers, etc.)

2. evolving algebras and various applications of them,

3. denotational semantics and domain theory, and

4. generalizations of automata theory and network theory.

There were many fruitful interactions and collaboration between specialists from different areas aswell as wide�ranging and vigorous discussion sessions. The conference was attended by 33 participantsfrom 11 countries.

On behalf of all participants, the organizers would like to thank the staff of Schlo� Dagstuhl forproviding an excellent environment for the conference.

Abstracts

U.Abraham, M.MagidorBakery Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

F.Afrati, S.CosmadakisEzpressiveness of Datalog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

E.Astesiano

A Unifying View of Imperative and Functional Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . �.2

C.Beierle

Designing an Abstract Machine and ProvingCompiler Correctness for Constraint Logic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ”�

A.Bla.ss

Semantics for Linear Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

E.B6rger, D RosenzweigOccam: Speci�cation and Compiler Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . �4

E.Dah]haus, N �SinclairE�cient Reduction of NP�Problems to Satis�ability by Interpretations . . . . . . . . . . . . . . . . . . . . . . . . . �.4

M.Droste

A Kleene Theorem for Recognizable Languages over Concurrency Monoids . . . . . . . . . . . . . . . . . . . . . . .5

E.Grädel

Inductive Definability with Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

Y.Gurevich

Distributed Evolving Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..6

R.Heckma.nn

Lower Bag Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7

W.HodgesDe�ning the Behaviour of a System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7

D.Kuske

Representation of Domains by Residuum Systems . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . ..8

J .A.MakowskyLogical Reducibility, Lindstrom Quanti�ers and Oracles K@� . �y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..8

G.L.McCo1m

Eventual Periodicity and Monadic Least Fixed Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9

F.Moller

Decidability Results in Automata and Process Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9

P.D.MossesAction Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10

K..}t.Niissler

Universality and Powerdomains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

M.Otto

On Simple Lindstrom Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 11

A.P(°)'tzsch�Heffter

Evovling Algebras as a Foundation forSemantics�Based Programming Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..12

K.Sieber

Call-by� Value and Nondeterminism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

E.W.Stark

Dataflow Algebra: A Tale of Two Monads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

I.Stewart

Extending First-Order Logic Using NP Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

B.Wald

On Types in C'omputer�-Algebra-Systems.Dynamic Recursive Types in Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Bakery Algorithms

URI ABRAHAM MENACHEM MAGIDOR

Lamport�s Bakery Algorithm and some variants are studied (these are all mutual exclusion pro-tocols). The main contribution is a protocol that is similar to the Bakery Algorithm but only usesbounded values. Another variant uses local clocks to coordinate the protocol�s execution, and condi-tions on the clocks are determined that suffice for the protoco1�s correctness.

In what sense is the bounded algorithm similar to the unbounded Bakery Algorithm? Usingthe notion of de�nability in models of system executions, a new property, the �Bakery De�nabilityproperty�, which is a strong form of the First Come First Serve (FCFS) property is de�ned. It isshown that Lamport�s Bakery Algorithm and its variants have this property.

Expressiveness of Datalog

Foro A1-�RATI STAVROS COSMADAKIS

Datalog is the language of negation-free, function-free Horn clauses; it mayviewed as a fragmentof �xpoint logic. The computational and expressive capabilities of Datalog have been the object ofconsiderable research recently, because it provides a simpli�ed model of the data sublanguage of logic

programming.Any query expressible in Datalog can be expressed in polynomial time. If the database includes

a total order of the domain and negation in the input relations is allowed, then Datalog «xpressesall polynomial time queries. However, without this extension, every query expressible in Datalogsatis�es certain well�known monotonicity properties, which exclude even some very simple queries;an example is the query which asks if the domain has even cardinality.

In this work, we give monotonic queries computable in polynomial time, which are not expressiblein Datalog. We show that a query which asks if a given directed graph has a path with length aperfect square, is not expressible in Datalog. We develop new tools to prove the results. The knownproof techniques for proving non-expresibility in Datalog make use of the fact that Datalog queriescan be expressed by in�nitary logic with �nitely many variables. The perfect square query , howeveris expressible in this logic. To prove that perfect square query is not expressible in Datalog, weshow that such queries satisfy a �pumping lemma�;this result exploits the �regular� structure of thein�nitary formulas which express Datalog programs.

We, also, give NC computable Datalog queries that cannot be expressed by any linear Datalogprogram. To prove the latter result, we show that queries expressible in linear Da.talog satisfy a morerestricted pumping lemma.

A Unifying View of Imperative and FunctionalLanguages

EGIDIO ASTESIANO

(joint work with ELENA ZUCCA)

D-oids are a model for systems of dynamic entities, based on the following featuresi

0 States are modelled by structures (algebras, usually) in some category; we assume that everystructure (called instant structure) has an underlying support consisting in an S�sorted familyof sets;

0 Variations of state are modelled by dynamic operations (also called methods) calls, whosesemantics is the most typical features of the approach: the effect of a call is a transformationof the source state into a new state, consisting in a map between the underlying carriers; thismap is called �tracking map�, since intuitively it keeps track of the identities of the evolvingdynamic entities.

An appropriate rather natural notion of morphism is given such that the d-oids over a category ofinstant structures are a category.

The emphasis of this talk is on a recent new result, consisting in the construction of the d-oid of dynamic terms over a dynamic signature and a family of variables. In the case that theinstant structures are provided of a free construction of terms over families of generators, then thed-oid of dynamic terms is a free construction. A most notable feature of the construction is theunique representation ;in other words a canonical representation is provided (no identi�cation) as ithappens in the classical static case. It can be shown that usual imperative method expressions canbe translated into the language of dynamicterms, which then may be seen as the basis of a kernellanguage for de�ning methods with the typical �avour of an applicative language.

Designing an Abstract Machine and ProvingCompiler Correctness for Constraint Logic

Programming

CHRISTOPH BEIERLE

The constraint logic programming scheme CLP(X ) provides a means of extending logic program-ming by constraints over a domain X. Given a constraint solver for X, one obtains a constraintsolver for the freely generated terms over X. By viewing the required term uni�cation part as inter-acting with the actual constraint solver over X, it is argued that a general scheme for an extensionof Warren�s Abstract Machine for executing Prolog can be designed for CLP(X

The thus obtained abstract machine WAM(X) not only uses the WAM�s original AND/OR struc-ture, but also most of the WAM�s term representation ca.n be kept and is extended in an orthogonalway. This permits us to introduce modular extensions of Börger and Rosenzweig�s formal deriva-tion of the WAM and their correctness proof which uses the concept of evolving algebras. As inthe original WAM case, our correctness proof also covers the sophisticated WAM optimizations likeenvironment trimming, last call optimization, switching, etc. which are still present in our WAM( X )extension. Our development is generic in the sense that it allows applications to different constraintformalisms like Prolog III, the type constraints of PROTOS-L (Beierle and Borger 92), or the arith-metic constraints of CLP(R) (Börger and Salamone 93).

Semantics for Linear Logic

ANDREAS BLASS

This survey talk began with an introduction to linear logic, emphasizing its semantical origins incoherence spaces. After a short summary of Lorenzen�s dialog interpretation of intuitionistic logic,I described game semantics for linear logic and stated its soundness and completeness theorems.Finally, I described the modi�cations of game semantics introduced by Abramsky and Jagadeesanto obtain their full completeness theorem for multiplicative linear logic with the mix rule. (Time didnot permit a planned discussion of de Paiva�s �relational� semantics or the observation that thereseem to be two rather different semantical intuitions attached to the �of course� modality.)

Occam: Speci�cation and Compiler Correctness

EGON BÖRGER DEAN ROSENZWEIG

Aiming at a transparent mathematical correctness proof for a general compilation scheme of Oc-cam programs on the Transputer, we develop a simple and natural abstract machine for (formalizationoi�) operational semantics of Occam, at several levels of abstraction. Starting from a truly concurrentmodel of the language, we re�ne communication, parallelism and alternation to an abstract notionof processor, running a queue of processes, still close to the abstraction level of atomic Occam com-mands. The speci�cation is effected within the framework of evolving algebras of Gurevich, relyingon the theory of concurrency developed recently within that framework by Glavan and Rosenzweig.The model lends itself naturally to re�nement down to the abstraction level of Transputer InstructionSet.

Eflicient Reduction of NP�Problems to Satis�abilityby Interpretations

ELIAS DAHLHAUS NATHAN SINCLAIR

We deal with the problem to �nd reductions to satis�ability given a logical description. Our aim is*§:i: solve N P-problems with the help of an efficient satis�ability solver. We assume that N P-problemsare expressed by existential second order formulas (see Fagin). Using the ideas of Lovasz and Gacs,we can �nd reductions to satis�ability efficiently. These reductions are not only polynomial time butl.l?J,�.J(�. nice logic properties. Moreover, we can take care that the size of the corresponding satis�abilityproblem can be minimized.

A Kleene Theorem for Reco nizable Languages overConcurrency onoids

MANFRED DROSTE

We investigate an operational model for concurrent systems, automata with concurrency rela-tions. These are classical �nite automata A, endowed with a system of symmetric binary relationsindicating when two events in a particular state of A can occur independently of each other. Theseconcurrency relations are assumed to depend locally, but not globally of each other. On the set ofall �nite computation sequences of A they induce, similarly as in trace theory, an equivalence, andvia composition of computation sequences we obtain a monoid M

In previous work, we investigated the relationship between these automata and Petri nets resp.Scott-domains. Here, we obtain, under suitable assumptions on A, a Kleene-type characterizationof all recognizable languages over concurrency monoids M (A): These are precisely the languageswhich can be constructed from �nite languages of M (A) by �nitely many applications of the oper-ations union, product, concurrent iteration. This contains Kleene�s theorem as a special case. Theproof uses methods of Ochmanski and Cori & Metivier from trace theory, Kleene�s theorem and thecombinatorics / algebra of concurrent algebra.

Inductive De�nability With Counting

ERICH GRÄDEL

(joint work with MARTIN OTTO)

We study the properties and the expressive power of logical languages that include both a mech-anism for inductive de�nitions and the ability to count. The most important of these languages is�xpoint logic with counting terms, denoted (FP + C).

Although it is known that these languages do not quite capture all polynomial-time core;:p11tab¥,=:queries, they provide a natural and important level of expressiveness. Besides (FP + C) we alsoinvestigate several other logical and algorithmical versions of inductive de�nability with <:o11ze:ti11gand show that they all have the same expressive power. In particular we consider:

D:�1f�."tl();�f 1&#39;/it}: counting. By adding counting terms to Datalog, we obtain l")zitalog + (J) whixtln wc:show to lie equivalent to (FP +C). In particular, (Datalog + C) is closed under xwgat,ionn n- f.|�|l&#39;I�f�*f()Te� in the presence of counting, the usual extensions of Datalog, notably E§t.m�;E�e«.E=. 421.3% 2-1.: are eq..iv:;ient to Ilatalog. This is not at all the case �-.vithout <&#39;ounting.

A functional logic It is known that the usual schemes, that de�ne � over N � the recursive func-tions, characterize, when interpreted over ordered �nite structures, precisely the functions com-putable in polynomial time. We de�ne a class of global functions, de�ned by a similar scheme,which has precisely the power of (FP + C).

A machine theoretic characterization. An algorithmic de�nition of (FP + C) is provided by a �re-lational machine�. The queries computed in polynomial time by these machines are preciselythe queries in (FF + C), those computed in polynomial space characterize partial �xpoint logicwith counting (PFP + C).

We also investigate the relationship of �xpoint logic and in�nitary logic in the presence of counting.In particular, we show that the types can beuniformly ordered by a formula in (FP +C). As aconsequence, there exists for every structure an (ordered) arithmetical invariant, which is uniformly(FP + C)-de�nable and which characterizes the original structure up to equivalence. Furthermore the(FC + C) de�nable properties of the original structures exactly correspond to the PTIME-propertiesof the associated invariants.

Abiteboul and Vianu recently proved that partial �xpoint logic collapses to �xpoint logic if andonly if PTIME= PSPACE. We show that the analogous result in the presence of counting is alsotrue: PTIME = PSPACE iff (FP + C) = (PFP + C). On the other side, Abiteboul and Vianu alsoproved that already a collapse of PFP|p to �xpoint logic is equivalent to PTIME = PSPACE. (Thelogic PFP] p is partial �xpoint logic restricted to PFP operators that close after at most polynomiallymany iterations on every structure.) In the presence of counting we can prove instead that (FP +C) z: (PFP|p + C).

Distributed Evolving Algebras

YURI GUREVICH

This is a joint work with my student Jim Huggins. In order to test the expressive power of DEalgebras, we construct a DE algebra for Kermit, the well known communication protocol.

Lower Bag Domains

REINHOLD HECKMANN

In the classical power domain constructions, multiplicities of results are not taken into account.Together with the order structure, this implies that certain �nite sets are identi�ed. In contrast, wepropose to count results, thus considering bags instead of sets. Since the lowerconstruction is thesimplest of the three classical power constructions, we investigate its non-idempotent analogue, thelower bag domain construction.

According to the general theory of power constructions, it can be introduced in two ways: as�initial� construction £7�, where £&#39;9�X is the free lower monoid over X in DC_PO, or as ��nal� con-�I �l

struction D�, where £}X = [[X �-> N3°] L�d> N3°] is the dcpo of continuous additive functions from[X �-> N3°] to N3°. The latter can be simpli�ed to £;�,,X = [SIX 2g N3°]� the dcpo of continuousmodular functions from the lattice (IX of opens of X to N3°.

We show that for sober dcpo�s X, each element of £;",,X can be represented as a (possibly in�nite)sum of singletons. For algebraic X, £&#39;,"nX is again algebraic; its basis consists of �nite sums ofsingletons from the basis of X. Equivalently, it consists of all �nite bags of �nite elements of Xordered by an analogue of the lower order on sets. In contrast to the set case, all �nite bags can bedistinguished. From this description, one concludes that .C;�,,X and £3� X are isomorphic for algebraicX and hence for continuous X. .

The construction �Cf = Cfn does not preserve the property to be a Scott domain, nor to be bi�nite.This negative result can be� seen at a small �nite example. Moreover, we can show that there is nopower domain construction with characteristic semiring N8° that preserves these domain classes.

De�ning the Behaviour of a System

WILFRID HODGES

We ask how far one can give a mathematical sense to the statement that two speci�cations(possibly in different languages) specify the �same behaviour� of a system. It is possible to give auniform denotational semantics for the standard algebraic and set-theoretic speci�cation languages;this is a theorem, and its proof shows how to give translations between these various languages. Twoproblems are noted.

(a) Speci�cations in set-theoretical languages (notably Z) are incompletely formalised, and to givetheir semantics in the style discussed above, we need to understand the author&#39;s intentions.This gap seems not to be serious.

(b) More seriously, the notion of �behaviour� used above is crude; in particular it does not includethe notion of behaviour being expressed in time as a response to earlier input. Wo can hope toextend the theorem above to more re�ned notions of behaviour (as for example in CCS). butthe result is likely to be less canonical.

Representation of Domains by Residuum Systems

DIETRICH KUSKE

Several models of concurrent systems and the domains generated by them have been investigated.Monoids of computations introduced in this talk can be used to represent all domains in a. uniformway. As a generalization of classical residuum operations (on automata, on term rewriting systems,on concurrent transition systems) we endow the monoids of computations by such an operation whichgives the minimal amount of computation necessary to obtain the result of one computation afterperforming another one. These extended monoids of computations are called residuum systems.By additional axioms, the classes of those residuum systems which generate L�domains and Scott-domains, respectively, are determined. The classes of residuum systems generating coherent Scott-domains, bi�nite domains, dl�domains and several other distributive domains can be described aswell.

Additionally it is possible to de�ne morphisms between residuum systems to get categories whichare equivalent to wellknown categories of domains with continuous or with stable functions as mor-

phisms.

Logical Reducibility, Lindstrom Quanti�ers andOracles

J.A. MAKOWSKY

(joint work with Y.B. PNUELI)

We describe a general way of building logics with Lindstrom quanti�ers which capture complex-ity classes based on oracle Turing machines. We �rst introduce a notion of reducibility based onc:.:tensions of first order logic rather than resource bounded Turing machines or �rst order logic. Itsmain property is that if a logic L captures a complexity class D, then a problem A is D reducibleto a problem B if? A is ß reducible B. This allows us to build logics capturing complexity classesincrementally, rather than by resorting to �rst order reductions. Our approach is sensitive to ther..z&#39;a.A:l«: computation model. Our results hold for the unbounded model introduced by Buss in supportr. 1&#39; his �rrrlativizatirin thesis�. They do not hold for the nondetermiziistic Elllil alterna�iing oracle compu-m: ions stiiclied by Iadner and Lymth. Simon and Fizzzo, Simon and ".§�ort:p:t. (im results _i:;ene&#39;ra?.i:z-�2and exte.1:..rl previous results of Stewart a.nd Makowszky and Fran-ii.

Eventual Periodicity and Monadic Least FixedPoints

GREGORY L. McCoLM

This talk concerned an application of the monotonicity of positive elementary formulas. Theimportant point was that this monotonicity could be used in the studying expressibility of (fragmentsof) Least Fixed Point logic. A system <po(:Eo,.§), . . . ,<,9,,(:E,,,5&#39;) of 5�-positive formulas is operative if,for each i, :2; and S; are of the same arity. Usually, we use such systems to get �least �xed points�as follows: <p?+1(:i:) E (,9.-(§:,g.o,&#39;)�,...,<,of,�) gwhere 90,71 = (b), and then set the least �xed point tobe (pi-�° = U,, 30?. Given some relations R = Ro,...,R,,, we want the unique system of relationsX = X0, . . . �X, such that:

1. For each i, i, X�-(5:) z- cp(i,X&#39;), and,2. for each i, R; _C_ X.-, and,3. for any X� also satisfying (1) and (2), X,- Q X,� for each i.Such a system X can be obtained by induction on the system 95, only starting at R(),..., R,

instead of (b, . . . ,0.We use this method of building �xed points from someplace other than the beginning to impose

restrictions on �xed points, and to prove that least �xed points on some structures look like (are 7&#39;-Fraissé equivalent to) least �xed points on other structures. We apply these techniques to the problemof determining whether given boolean LFP-de�n able queries are 1-dimensional, i.e., whether they canbe de�ned from systems cp,-(as,-, 5&#39;), i = 0, . . . � 1/, where each S; is unary.

Most of the material in this talk appeared in Eventual Periodicity and One-Dimensional Queries,Notre Dame J. of Formal Logic 33:2 (1992), 273-290.

Decidability Results in Automata and ProcessTheory

FARON MOLLER

In this lecture we survey decidability results for various notions of equivalence over three classesof processes: regular (�nite-state) processes, context-free processes, and basic parallel processes. Inparticular, we demonstrate the decidability of bisimulation equivalence over all three classes, us-ing three different techniques: for regular processes the result follows by a brute force search for abisimulation relation over the �nite-state agents; for context-free processes we use a �nite charac-terisation of in�nite bisimulation relations; and for basic parallel processes we use a tableau-baseddecision procedure. We also demonstrate the undecidability of simulation and language equivalences

for basic parallel processes; the proof is a modi�cation by Y.Hirshfeld of a proof by P.Jancar of theundecidability of bisimulation equivalence of labelled Petri nets.

Action Semantics

PETER D. MOSSES

Action Semantics is a framework that combines some of the best features of denotational se-

mantics, operational semantics, and algebraic speci�cations. The combinator-based action notationprovided by the framework appears to solve the modularity problems of previous semantic descriptiontechniques, and experiments have shown that action semantic descriptions scale up smoothly fromsimple pedagogical examples to practical programming languages.

In this talk, action semantics is introduced by showing how it can be used to describe a fragmentof Standard ML. The intended interpretation of the required part of action notation is explained. Thesyntax of the described language is then extended with the main constructs of Concurrent ML, and itis shown how the semantic description can be extended to the new constructs � without changing thervriginal semantic equations at all! The talk concludes by comparing action semantics with evolvingalgebras, and considering the possibility of hybrids involving features of both frameworks.

Universality and Powerdomains

KAY J. NÜSSLER

The class of all L�domains is not closed under the Plotkin�powerdomain�construction. Hencewe are looking for an ordertheoretic property that gives a characterization of all L�domains (D, 3)whose Plotkin�Powerdomain P[D] is again an L�domain. The demand that (D, 3) does not containthree special �nite posets is equivalent to the condition that the powerdomain is an L�domain.

In the theory of denotational semantics of programming languages, various authors establishedthe existance of special kinds of universal objects. It is a question of Plotkin whether there existsa Scott�domain (D, 3) whose P1otkin�powerdoma.in P[D] is universal for the category of bi�nitedomains (SFP�domains), i.e. for every bi�nite domain (E, 3) there exists an embedding projectionpair of (E, 3) into P[D]. We showed that this question can be answered negatively and gave a �nitecounterexample. Moreover we �nd out that even the class of bi�nite domains does not contain anobject whose Plotkin�-powerdomain is universal for the category of all �nite domains with embeddingprojection pairs.

10

On Simple Lindström Extensions

MARTIN OTTO

In abstract model theory Lindström quanti�ers provide a uniform formalism for the treatment ofextensions of logics:A new structural property � as given by an as yet not de�nable class of structures � is made availablein the extension by allowing to assert this property of structures which are de�nably interpretedwithin the domain of discourse. &#39;

9 In �nite model theory one looks for matches between logical expressibility (logical complexity)and computational complexity. While this approach has been very successful within the domainof linearly ordered structures, there are no de�nite results for even the most important complexityclasses below N PTime. Most notably, �xed-point logic (FP) captures PTime on ordered structures,but is far too weak in the general case. No extension which exactly reaches up to PTime has beenfound, and in fact it has even been conjectured that no logic captures PTime in the general case

(Gurevich, 88).Hence the systematic investigation of extensions of FP is of interest. The ad junction of all PTime

Lindström quanti�ers corresponds to a trivial shift of the problem: the resulting �logic� is triviallycomplete for PTime, but syntactically acceptable as a logic only if the class of all PTime structuralproperties is recursively enumerable. This latter condition is equivalent with the existence of a logicfor PTime.

With a view to the idea of a closer or lower-level match between algorithmic analysis and logical,i.e. descriptive modelling, one might therefore focus on the adjunction of simple, low complexityor fundamental extra structural properties to �xed-point logic and try to leave the modelling ofrecursion to �xed-point generation. We here show that � for one conception of �simplicity� expressedin terms of the existence of simple invariants � this attempt must fail. This conception of simplicityencorporates in particular the most liberal formalisation of cardinality properties, which also providethe key example for this analyis: even the adjunction of all cardinality based Lindström quanti�ers to�xed-point logic does not reach up to the expressive power of the natural (and non-Lindstréim type)extension of �xed-point logic, which allows to assess and process cardinalities in a recursive way (seeGrädel/ Otto, CSL 92, for a detailed overview of this logic). These results extend to other propertiesgoverned by simple invariants, like monadic properties, or properties of equivalence relations.

In the present framework we naturally deal with in�nite families of Lindström quanti�ers acrossall arities. Known negative results in this context - based on different techniques and prerequisites� focus on �nite Lindström extensions, cf. Hella, LICS 92, and Kolaitis/Vaananen LICS 92.

11

Evolvin Algebras as a Foundation forSemantics� ased Programming Environments

ARND PÖTZSCH-HEFFTER

Semantics�based programming environments should enable the user to annotate programs, tospecify program analyses, and to prove annotations and other program properties correct. Suchenvironments heavily rely on an appropriate speci�cation of the underlying programming language.

The talk introduced attributed occurrence structured � a formalism to specify the context-dependent syntax and static semantics of programming languages in terms of �rst�order structures�- and proposed to use evolving algebras together with attributed occurrence structures (AOS forshort) as a speci�cation framework for semantics�based programming environments. Even thoughthe use of AOS�s i-s not necessary from a theoretical point of view, they are essential when it comes tothe construction of realistic systems. AOS�s are a generalization of attribute grammars; in particular,they allow to specify classes of graph structures.

We showed how the �rst�order language given by an EA+AOS�speci�cation can be used to de-1* are program annotations and data �ow analyses in terms of temporal logic formulas. The semanticsof these formulas coincide with the runs of the EA semantics. We de�ned the weakest precondi-tion transformer associated with an EA and gave the corresponding basic rule to prove invarianceproperties of programs.

Call�by-Value and Nondeterminism

KURT SIEBER

In order to study nondeterminism in a very �pure� setting, we consider a simply typed purelyfunctional call-by-value language with nondeterministic choice operators at all types. For this lan-guage we de�ne a generic denotational semantics in terms of an arbitrary powerdomain construc-tion. The three �classical� instances of this generic semantics, obtained by the Hoare-, Smyth- andPlotkin-powerdomain, correspond to three different notions of observable behavior of nondetermin-istic programs, which we call partial correctness behavior, total correctness behavior and overallbehavoir.

For all three powerdomain semantics we investigate the question of full abstraction. For theHoare-powerdomain we obtain full abstraction by more or less traditional methods. For the Smyth-powerdomain full abstraction fails irreparably. Full abstraction also fails for the Plotkin-powerdomain,but here we can repair something: By adding an exists-operator, which can test all paths of a (non-deterministic) compuctation in parallel, we obtain full abstraction for the sublanguage, in which all

12

functions have only ground type results. But for the full language, even this highly parallel exists-operator is not sufficient to obtain full abstraction, and there is some evidence that this cannot berepaired by adding further operators to the language.

Data�ow Algebra: A Tale of Two Monads

EUGENE W. STARK

Data�ow networks constitute a paradigm for concurrent computation in which a collection ofconcurrently and asynchronously executing processes communicate by passing messages containingdata values over FIFO communication channels. In previous work (reported in the 1992 LICS con-ference), I introduced a formal calculus, called �data�ow calculus,� for data�ow networks, de�neda bisimulation-based notion of network equivalence, and obtained a sound and complete axiomati-zation of the resulting equational theory. In this lecture, I consider the problem of de�ning a classof �data�ow algebras�, having sufficient structure to provide an interpretation of the syntactic con-structs (network terms and computation terms) of data�ow calculus. I provide motivation for theidea that data�ow algebras have simultaneously the structure of algebra for two related monads: onemonad P that captures the notion of parallel composition of networks, and a second monad F, whichcaptures the notion of forming feedback loops in terms of the �action� on networks of a a certainsimple class of continuous functions. The two structures are related by a distributive law of feedbackover parallel composition.

Extending First�Order Logic Using NP Operators

IAIN STEWART

We investigate why similar extensions of �rst-order logic using operators (that is, generalizedquanti�ers) corresponding to N P-complete decision problems apparently differ in expressibility: thelogics capture either NP or L(N P). It had been conjectured that the complexity class captured is NPiff the operator is monotone. We show that this conjecture is false. However, we provide evidencesupporting a revised conjecture involving finite variations of monotone problems.

13

On Types in Computer�Algebra�SystemsDynamic Recursive Types in Maple

BURKHARD WALD

From our point of view the computer�algebra�system Maple is just a programming language.Maple has an extensive type�system, which we call syntactical type-system, because Maple�datasare mathematical terms and hence syntactical things. The talk introduces a possibility to assign atype to a symbol, which gives the symbol a mathematical meaning. For this semantic propose wede�ne new types.

EXAMPLE. There is a syntactic type integer. For type-assignment we de�ne a type INT byrecursion ( integer are INT, sums of INT are INT and so on). In addition, if we make a type-assignment of INT to a symbol, this symbol gets type INT. Hence the set of terms which are oftype INT changes dynamicly. At last we compare our approach with the new assun e-functionalityuf release 2 of Maple V .

14

Dagstuhl-Seminar 9323: List of Participants 25.06.93

Uri Abraham Egon BörgerBen Gurion University Universita� di PisaDept. of Mathematics and Computer Sci- Dip. di lnformaticaence Corso Italia 40Beer Sheva I-56100 PisaIsrael Italyabraham@indigo.bgu.ac.iI boerger@di.unipi.it

tel.: +39-50-51 02 30Foto AfratiNational Technical University of Athens Elias DahlhausDept. of Elec. Eng. and Comp. Science University of Sydney9 Heroon Politechnion Basser Dept. of Computer Science15773 Zographon New-South -Wales 2006Greece Australia

afrati@theseas.ntua.gr dahIhaus@cs.su.oz.autel.: +30-1 -2232097 / 30-1 -7757401 tel.: +61 �2�692-3756

Egidio Astesiano Hans DobbertinDipartimento di lnformatica e Bundesamt für SicherheitScienze deII&#39;Informazione InformationstechnikDISI Godesberger Allee 183Viale Benedetto XV W-5300 Bonn 1I-16132 Genova GermanyItaly tel.: +49-228-768331 (privat)astes@disi.unige.ittel.: +39-10-353-8O 31 Manfred Droste

FB Mathematik und InformatikAndreas Baudisch Postfach 10 37 64Freie Universität Berlin W-4300 Essen 1Fachbereich Mathematik GermanAmimallee 3 matb3O vm.hrz.uni�essen.deD-14195 Berlin teI.: +49-201-183 2505

Germanybaudisch@math.fu-berIin.de H.-D. Ebbinghaus

Universität FreiburgChristoph BeIerIe Abt. für Mathematische Logik undIBM Deutschland GmbH Grundlagen der MathematikWissenschaftliches Zentrum Heidelberg Albertstr. 23bInstitut für Wissensbasierte Systeme D-79104 FreiburgPostfach 10 30 68 GermanyW�6900 Heidelberg hde@sun1.ruf.uni-�treiburg.deGermany tel.: +49-761-203-23 84beierle@vnet.ibm.comtel.: +49�6221�594393 Jörg Flum

Albert-Ludwig-Uni. FreiburgAndreas Blass Abt. für Mathematische Logik undUniversity of Michigan Grundlagen der MathematikDept. of Mathematics Albertstr. 23bAnn Arbor MI 48109-1003 D-79104 FreiburgUSA Germanyabiass@umich.edu fIum@sun1�rutuni-freibesrcdeteI.: -;-1-313-763-1183 teI.: +49-761-203-23 82

Erich Grädel V�Lehrgebiet Math. Grundlagen Dietrich Kuskeder Informatik Universität GHS EssenMathematisches Institut Fachbereich Mathematik und InformatikAhornstr. 55 Postfach 10 37 64D-52074 Aachen W-4300 Essen 1German Germanygraedelémjoliinformatik.rvvth-aachen.de mem080@de0hrz1 a.bitnettel. : +49-241-802-1 O80 teI.: +49-201 -1833-659

Irene Guessarian Menachem MagidorUniversite de Paris VI Hebrew UniversityLaboratoire Informatique Dept. of MathematicsThéorique et Programmation 91904 Jerusalem4 Place Jussieu IsraelF-75252 Paris Cedex 5 menachem@sunrise.huji.ac.iI_France teI.: +972-2-58-5355/6ig@|itp.ibp.irteI.: 4-33-1-4427-7029 Janos A. Makowsky

Technion � Haifa

Yuri Gurevich Computer Science Dept.Universit of Michi an Haifa 32 O00Dept. of lectrical ngineering and IsraelComputer Science janos@cs.technion.ac.iIArbor Ml 48109-2122 teI.: +972-4-332952gurevich@eecs.umich.edu Greg L. McCoImteI.: +1�313-7 63 45 26 University of South Florida (USF)

Dept. of MathematicsReinhold Heckmann 4202 E. Fowler Ave. PHY 114Universität des Saarlandes Tampa FL 33620-5700FB 14 - Informatik USAPostfach 11 50 mccolm@math.usf.eduD-66041 Saarbrücken teI.: +1 813-974-2643/3498 or 989-2590Germanyheckmann@cs.uni-sb.de Faron MollerteI.: +49-681-302-24 54 Universit of Edinburgh

Dept. of omputer ScienceChristian Herrmann The King&#39;s BuildingsTechnische Hochschule Darmstadt Mayfield RoadFachbereich Mathematik &#39; Edinburgh EH9-3JZSchlossgartenstr. 7 Great BntainW-6100 Darmstadt fm@|fcs.ed.ac.ukGermany teI.: +44-31-650-51 50

herrmann@mathematik.th-darmstadt.de Peter Mosses

Wilfrid Hodges Aarhus UniversityQueen Ma and Westfield College Com uter Science Dept.School of athematical Sciences Ny unkegadeMile End Road D -8000 Aarhus CLondon E1 4NS DenmarkGreat Britain pdmosses@daimi.aau.dkw.hodges@qmw.ac.uk teI.: +45-86-12 71 88

Kay J. NüßlerUniversität GHS EssenFachbereich Mathematik und InformatikPostfach 10 37 64W-4300 Essen 1

GermanyteI.: +49-201-737 569

Martin OttoRWTH AachenLehr- und ForschungsgebietMathematische Grundlagen der InformatikAhornstr. 55W-5100 Aachen

Germanyotto@jo|i.informatik.rvvth�aachen.de

Leszek PacholskiInsitute of MathematicsPolish Academy of ScienceKopernika 18PL-51 617 WroclawPolandteI.: +48-71-25 12 71

Amd Poetzsch-HeffterCornell UniversityDepartment of Computer Science4112 Upson Halllthaca NY 14853-7510USA

poetzsch@cs.cornell.eduteI.: +1 -607-255-9222

Dean RosenzweigUniversity of ZagrebFSB Katedra MatematikuDure Salaja 541000 ZagrebCroatia

dean.rosenzweig@uni�zg.ac.maiI.yu teI.: +38�41 �611944

Kurt SieberUniversität des SaarlandesFachbereich 14 - InformatikPostfach 1150D-66041 Saarbrücken

Germany sieber@cs.uni-sb.deteI.: +49-681-302-32 35

Eugene W. StarkState University of New Yorkat Stony BrookDept. of Computer ScienceStony Brook NY 11794-4400USA

stark@cs.sunysb.eduteI.: +1-516-632-8444

lain A. StewartUniversit College of SwanseaDept. of omputer ScienceSingleton ParkSwansea SA2 8PPGreat Britain

i.a.stewart@swansea.ac.ukteI.: +44-792-20 56 78

Burkhard WaldUniversität GHS Essen

Hochschuirechenzentrum Postfach 10 37 64W-4300 Essen 1

GermanywaId@hrz.uni�essen.deteI.: +49-201-183-2921

Zuletzt erschienene und geplante Tntel:

A. Arnold, L. Priese� R. Vollmar (editors):Automata Theory: Distributed Models, Dagstuhl-Seminar-Report; 54; 11.01 .-15.01 .93 (9302)

W. Cellary, K. Vidyasankar, G. Vossen (editors):Versioning in Database Management Systems, Dagstuhl-Seminar-Report; 55; 01.02.-05.02.93(9305)

B. Becker, Ft. Bryant, Ch. Meinel (editors):Computer Aided Design and Test , Dagstuhl-Seminar-Report; 56; 15.02.-19.02.93 (9307)

M. Pinkal, R. Scha� L. Schubert (editors):Semantic Formalisms in Natural Language Processing, Dagstuhl-Seminar-Report; 57; 23.02.-26.02.93 (9308)

W. Bibel, K. Fumkawa, M. Stickel (editors):Deduction , Dagstuhl-Seminar-Report; 58; 08.03.-12.03.93 (9310)

H. Alt, B. Chazelle, E. Welzl (editors):Computational Geometry, Dagstuhl-Seminar-Report; 59; 22.03.-26.03.93 (9312)

H. Kamp, J. Pustejovsky (editors):Universals in the Lexicon: At the Intersection of Lexical Semantic Theories, Dagstuhl-Seminar-Report; 60; 29.03.-02.04.93 (9313)

W. Strasser, F. Wahl (editors):Graphics & Robotics, Dagstuhl-Seminar-Fleport; 61; 19.04.-22.04.93 (9316)

C. Been�, A. Heuer, G. Saake, S. Urban (editors):Formal Aspects ot Object Base Dynamics , Dagstuhl-Seminar-Report; 62; 26.04.-30.04.93 (9317)

R. V. Book, E. Pednault, D. Wotschke (editors):Descriptional Complexity, Dagstuhl-Seminar-Report; 63; 03.05.-07.05.93 (9318)

H.-D. Ehrig, F. von Henke, J. Meseguer, M. Wirsing (editors):Specification and Semantics, Dagstuhl-Seminar-Report; 64:24.05.-28.05.93 (9321)

M. Droste, Y. Gurevich (editors):Semantics of Programming Languages and Algebra, Dagstuhl-Seminar-Report; 65; 07.06.-11 .06.93 (9323)

Ch. Lengauer, P. Quinton, Y. Robert, L. Thiele (editors):Parallelization Techniques tor Uniform Algorithms, Dagstuhl-Seminar-Report; 66; 21 .06.-25.06.93(9325)

G. Farin, H. Hagen, H. Noltemeier (editors):Geometric Modelling, Dagstuhl-Seminar-Report; 67; 28.06.-02.07.93 (9326)

Ph. Flajolet, R. Kemp, H. Prodinger (editors):"Average-Case"-Analysis of Algorithms, Dagstuhl-Seminar-Report; 68; 12.0�/.-16.07.93 (9328)

JW. Gray, A.M. Pitts, K. Sieber (editors):Interactions between Category Theory and Computer Science, Dagstuhl-Seminar-Report; 69;19.07.-23.07.93 (9329)

D. Gabbay, H.-J. Ohlbach (editors):Automated Practical Reasoning and Argumentation, Dagstuhl-Seminar-Report; 70; 23.08.-27.08.93 (9334)

A. Danthine , W. Eflelsberg, O. Spaniol, (editors):Architecture and Protocols for High-Speed Networks, Dagstuhl-Seminar-Fteport; 71; 30.08.-03.09.93 (9335) �

R. Cole, E. W. Mayr, F. Meyer a.d.Heide (editors):Parallel and Distributed Algorithms, Dagstuhl-Seminar-Report; 72; 13.09.-17.09.93 (9337)