A complete calculus for the multialgebraic and functional semantics of nondeterminism.
The current algebraic models for nondeterminism focus on the notion of possibility rather than necessity and consequently equate (nondeterministic) terms that one would intuitively not consider equal. Furthermore, existing models for nondeterminism depart radically from the standard models for (equational) specifications of deterministic operators. One would prefer that a specification language for nondeterministic operators be based on an extension of the standard model concepts, preferably in such a way that the reasoning system for (possibly nondeterministic) operators becomes the standard equational one whenever restricted to the deterministic operatorsthe objective should be to minimize the departure from the standard frameworks. In this article we define a specification language for nondeterministic operators and multialgebraic semantics. The first complete reasoning system for such specifications is introduced. We also define a transformation of specifications of nondeterministic operators into derived specifications of deterministic ones, obtaining a computational semantics of nondeterministic specification by adopting the standard semantics of the derived specification as the semantics of the original one. This semantics turns out to be a refinement of multialgebra semantics. The calculus is shown to be sound and complete also with respect to the new semantics.
Introduction
The notion of nondeterminism arises naturally in describing concurrent systems. Various approaches
to the theory and specification of such systems, for instance, CCS [Milner 1980], CSP [Hoare
1985], process algebras [Bergstra 1986], event structures [Winskel 1988], include the
phenomenon of nondeterminism. But nondeterminism is also a natural concept in describing
sequential programs, either as a means of indicating a "don't care'' attitude as to which among a
number of computational paths will actually be uti lized in a particular computation (e.g., [Dijkstra
1976]) or as a means of increasing the level of abstraction [Meldal 1989, Walicki 1994a]. The
present work proceeds from the theory of algebraic specifications [Ehrig 1985, Wirsing 1990] and
generalizes it so that it can be applied to describing nondeterministic operations. Our main concern
is to make such an extension non-intrusive, i.e., such that it does not change the existing
framework, and in particular, reduces to the standard deterministic theory when only deterministic
operations are present in the specification.
In terms of satisfiability, allowing nondeterminism is quite distinct from underspecification.
The latter, though admitting distinct models, still insists on a function always returning a specific
value, given a particular list of arguments. In the case of nondeterministic operators this is no
longer true. 1 Also, nondeterminism turns out to be a useful abstraction tool whenever there is a
* We gratefully acknowledge the financial support received from the Norwegian Research Council.
1 In the interest of clarity we shall let the term function denote deterministic operator, and the term operation denote
nondeterministic as well as deterministic operators.
hidden state or other components of a system description which are, methodologically or
technically, inaccessible at a particular level of abstraction. As we illustrate in section 6 [also
Walicki 1994a], underspecification does not provide an equally powerful abstraction mechanism.
The basic concept of classical algebraic specifications is the notion of function. Classical
specifications describe programs which, when viewed abstractly, are input-output functions - a
particular input uniquely determines the output value resulting from evaluating the program. 2 This
does not hold for nondeterministic programs. The input to such a program does not uniquely
determine the resultant output. Since a nondeterministic program cannot be modeled as an input-output
function, the set approach [Hesselink 1988, Kaplan 1988, Kapur 1980, Maibaum 1977,
Subrahmanyam 1981] generalizes the standard algebraic notion of programs as functions, and
regards nondeterministic programs as functions in a multialgebra. A program then denotes a function
which instead of returning single values returns sets of values. For a particular nondeterministic
operator f and argument a, the term f(a) denotes the set of all values possibly returned by f . Thus, in
the set approach, a nondeterministic specification of programs is modeled by structures describing
its possible behaviors.
For a sort T, let " #._: Set(T)#T" denote an operator which makes a nondeterministic choice
among the elements of some set of T-elements. For instance, # .{0, 1} may return either of the
values 0 and 1, and need not return the same value at every application.
In the set approach, the semantics of the term #.{0, 1} is a constant - the term #.{0, 1} denotes
the set {0, 1} of possible results. Consequently, the equality #.{0, 1}=#.{0, 1} will hold, since both
sides are interpreted as the same set-valued constant. Consider now the evaluation of a program
making use of such an equality, for instance in the expression "if #.{0, 1}=#.{0, 1} then 5 else 6 fi".
According to our intuition the result of evaluating the expression could be either 5 or 6, depending
on whether the two applications of #.{0, 1} returned the same value or not. But according to the set
semantics of equality the result will always be 5, because the term #.{0, 1} denotes one and the
same set-valued constant - the equality " #.{0, 1}=#.{0, 1}" is interpreted as a test of whether the set
{0, 1} equals the set {0, 1}, which is always true [Hesselink 1988, Kaplan 1988, Kapur 1980,
Maibaum 1977, Subrahmanyam 1981]. Thus the set semantic interpretation of equality implies the
possibility of two terms returning the same result, but it does not guarantee that the same results
actually will be produced. This leads to particular difficulties in treating properly such notions as,
for example, observability [Hennessy 1980, Nipkow 1987] and implementation [Qian 1993].
Equality in our view should be a necessary equality which must hold in every evaluation of a
program (specification). It does not correspond to set equality, but to identity of 1-element sets. Thus the
simple formula t=s will be considered true (in a multistructure M) iff both t and s are interpreted as
one and the same set which, in addition, has only one element. (To indicate this modified
interpretation we will use the symbol "# " instead of the usual identity "=".)
Besides problems with construct ing an adequate algebraic model the set approach originally
forced one to consider even simple equa tional specifications as full first order theories
[Subrahmanyam 1981, Kapur 1980]. This, of course, led to reasoning systems whose efficiency and
This observation extends to reactive systems as well, see [Kahn 1974].
simplicity could not match that of the existing systems for equational reasoning (see, e.g., [O'Donell
1977, Dershowitz 1990] for references).
The difficulty with the set approach as sketched above is its inability to distinguish between the
equivalence of terms and the equivalence of application of terms. This distinction is of no
consequence in the deterministic case, because there every term necessarily identifies a single value;
evaluating a term more than once will always yield the same result. On the other hand, distinct
applications of a nondeterministic operator will typically yield different results.
The distinction between terms (operations) and their applications is merely a technical
reflection of the distinction between programs and computations, a distinction whose relevance
became obvious with the advent of parallel and nondeterministic computing. When writing
specifications, we are primarily interested in these as constraints on computations . Their importance
as constraints on the acceptable programs is only a secondary concern, arising from the fact that a
program identifies a set of possible computations.
We are not interested in programs (they are just pieces of text), but rather in what happens
when they are evaluated. A specification serves the purpose of abstractly describing legal
computations. In contrast to the algebras of possibilities represented by the set approach we offer
algebras of actual computations . Any particular computation is an abstract computation in the sense
of algebra - input-output functions. In this way we preserve the basics of classical algebraic theory,
and we believe that this view is the more relevant in actual use.
This paper presents a function oriented view which refines the notion of equality in the
multialgebraic semantics. The result of a (non-)deterministic operator is considered a single (rather
than set) value, namely the result of a particular application . Distinct occurrences of a particular
term will each denote a single value, but not necessarily the same one for each. The equality #.{0,
1}=#.{0, 1} no longer holds. Instead, we will restore the meaning of equality as a necessary relation
which must hold in any particular evaluation of a program.
In this new semantics, nondeterminism is reflected in the existence of distinct computations -
each realizing distinct possibilities of nondeterministic operators. Simple facts such as "if x is a
result of applying # .{0, 1} then x=0 or x=1" are not only expressible and provable in this sys tem
they have a natural interpretation in the computational model. 3 The semantics also satisfies a
secondary concern of ours: that the specification formalism not only deals with nondeterminism in
a sensible and intuitive way, but that it also preserves the notions and results of the standard
algebraic approaches to deterministic constructs. This is important for two reasons: (1) The
formalism behaves in the expected ways within the usual domains of formal specifications. Thus the
specifier need not be exposed to new (and possibly exotic) semantic concepts as long as he stays
within the deterministic domain of discourse. (2) The existing tool base, created to cater for
standard (equationally defined) algebras [Dershowitz 1990, O'Donell 1977] can be retained. In
3 This may seem trivial, but was in fact hard enough to require the introduction of full first order logic in the early
deduction systems [Kapur 1980, Subrahmanyam 1981]. All classes of structures proposed as semantics of
nondeterminism allow models in which such disjunctive equations are not valid, and can be satisfied only by making
additional semantic restrictions [Hu-mann 1990,Hu-mann 1993,Maibaum 1977,Mosses 1989a].
extending the tool base to cover nondeterminism as well, one can hope for reusing much of the
existing software.
At the same time we show that replacing the notion of set equality by the element equality, the
two semantics are compatible - the multialgebraic semantics can be seen as a convenient
abstraction of the function oriented one. The calculus introduced in the paper is sound and
complete with respect to both semantics and thus allows one to reason at the more abstract level
where terms are thought of as sets of possible results.
As the main results we present:
modified view of equality in the multialgebraic semantics of nondeterminism.
calculus, NEQ, which is sound and complete with respect to the multialgebraic
semantics, and which behaves identically with the standard equational calculus
[Birkhoff 1935] in the deterministic case.
new - functional - semantics for nondeterministic specifications which refines the
multialgebraic one.
Soundness and completeness of NEQ with respect to this new semantics.
transformation procedure allowing one to interpret specifications of
nondeterministic operators as underspecified deterministic functions.
The structure of the paper is: in section 2 we introduce a specification language L neq which
provides for nondeterministic operators. In section 3 the class of multimodels of a specification in
L neq is defined. In section 4 we show how specifications of nondeterministic operators in L neq can
be transformed into specifications of deterministic ones by translating them into the language L deq
which is the usual language of deterministic conditional equations extended with disjunction. We
then define the (loose) functional semantics of the original specification as the class of standard
models of the derived L deq specification. Subsection 4.3 compares the two semantics. Section 5 introduces
a calculus NEQ, discusses some of its features and states soundness and completeness of
NEQ with respect to both multialgebraic and functional semantics. Section 6 contains an example
specification of access types. Section 7 summarizes our results and comments briefly on some re -
lated work.
The proofs have been omitted from the paper - they are given in full in [Walicki 1993a],
except for the soundness and completeness theorems which are proved in the appendix.
2. Writing specifications of nondeterministic operators
In this section we present the specification language L neq , in which the user is expected to write the
specifications. We also explain informally the intended semantics of L neq and discuss the relation
between the interpretation of terms as applications of (possibly nondeterministic) operations and as
sets of possible results.
2.1. Syntactic preliminaries
A specification in L neq is a pair ((, )), where the signature ( is a pair of sets (S, F ) of sorts S and
operation symbols F (with arguments and result sorts in S). There exists a denumerable set V of
variables for every sort. For any syntactic entity (term, formula, set of formulae) x, V[x] will denote
the set of variables in x. Letters from the end of the Latin alphabet, x, y, z are used for variables.
The set of terms over the signature ( and a variable set X is denoted W (, X
. We always assume
that, for every sort S, the set of ground terms of sort S, (W (
, is not empty. 4
P is a set of clauses. Each clause C is a set of literals (i.e., the ordering and multiplicity of the
literals do not matter), written as a 1 , . , a n (possibly within "{ }"). A clause will be interpreted as
disjunction of its literals and, sometimes, we will write it explicitly as a 1 #a n
. Usually, we use
uppercase Latin letters for single clauses, uppercase Greek letters for sets of clauses, and lowercase
Latin letters a , e for literals. Comma indicates concatenation (set union) of clauses, and semicolon a
collection. E.g., if C is {c 1 , ., c n }, D is {d 1 , ., d m }, and a is a literal (identified with an atomic clause
for brevity), then "C ; D" denotes the conjunction of the two clauses, while " C, D" denotes the
clause {c 1
is the clause {c 1
, a} and " C ; a" is the conjunction
of C and {a}. "P ; C" denotes the set (of clauses) P extended with the clause C.
A literal (atomic clause) is either an equation, t#s, an inclusion, t#s, or an inequality , t-s, of terms
t, s#W (, X . Equations and inclusions are called the positive literals (or atoms), and inequalities the
negative literals. 5 We do not use a negaton of inclusion - as will be explained below, inequalities
play the role of the complement of both equalities and inclusions. A clause { t- s, p#r } is thought
of as the conditional formula -( t-s) # p #r, stating that p is included in r whenever t is not
(necessarily) distinct from s . A clause with exactly one positive literal is called a Horn formula, and a
Horn formula with no negative literals a simple formula.
All variables occurring in a clause are implicitly universally quantified over the whole clause. A
clause is satisfied if, for every assignment to the variables, at least one of the literals is true.
For a specification SP=((, )), L neq
(SP) is the restriction of L neq
to W ( , V .
2.2. L neq
specifications and informal semantics
Multialgebraic semantics [Hu-mann 1993, Kapur 1980] interprets specifications in some form of
power structures where the (nondeterministic) operations correspond to set-valued functions . This
means that a (ground) term is interpreted as a set of possibilities - it denotes the set of possible results
of the corresponding operation. We, on the other hand, want our formulae to express necessary
i.e., facts which have to hold in every evaluation of a program (specification). We think of each
occurrence of a term of L neq as referring to a particular (arbitrary) application of the operation which
returns one of the possible results of the operation. Thus two occurrences of syntactically identical
terms refer to two potentially dis tinct applications of the operation, and syntactic identity of terms
4 We do not address the problem of empty sorts here and will present calculus which works under the assumption that
sorts are not empty. We will usually give signatures with at least one constant for every sort but other ways of
restricting the signatures [Goguen 1981, Huet 1980] or ensuring nonemptiness [Goguen 1981, Goguen 1987] can be
used instead. It seems also that the most flexible approach which generalizes calculus by introducing explicit variables
[Goguen 1981, Goguen 1982, Ehrig 1985] can be adapted to our framework.
5 An equivalent (and the original) formulation of the syntax and the following results could use sequents A , B, where
all atoms in A are equalities (corresponding to - ) and all atoms in B equalities or inclusions. Because such a
formulation complicates the calculus and proofs, we choose the present syntax of clauses.
does not , in general, imply semantic iden tity . Every two syntactic occurrences of a term t are thought
of as possibly distinct applications of t . For nondeterministic terms this means that they may denote
two distinct values.
This distinction between deterministic and nondeterministic terms is captured in the
multialgebraic semantics by the modified notion of equality which we interpret (according to the
discussion in section 1) as necessary equality. Although multialgebras interpret terms as sets of
possible results, and hence two terms denoting the same set are equal as sets , we will make a clause
t#t hold only if any two applications of t return the same result, i.e. if t is deterministic. # is then a
equivalence relation and terms t for which t#t is valid are exactly the deterministic terms, denoted
by D SP, X . Variables will always be interpreted deterministically - all occurrences of a
particular variable in a clause denote the same value (see definition 3.3). (For a discussion of the
consequences of allowing variables to be interpreted nondeterministically, see [Walicki
1994a,Walicki 1994b].) We consider the loss of referential transparency implied by such a
reinterpretation of equality to be an intrinsic feature of nondeterminism [e.g. Qian 1993]. And as a
consequence our proof system only allows a restricted form of substitutivity.
Observe that operators with no arguments (which in theories of deterministic operations always
denote constants) need not be constant at all in L neq
. An operator such as c: #S will have distinct
meanings depending on whether the determinacy axiom " c#c" is valid or not. If it follows from the
specification then c denotes a usual deterministic constant. If not, then c corresponds to (possibly
unbounded) nondeterministic choice from the set of elements of the sort S. This, together with
inclusion and (limited) negation expressed by - allows us to utilize nondeterminism for defining
and reasoning about subsort hierarchies at the term level (in a way reminiscent of unified algebras
1989a]).
Interpreted in the multialgebras, " s#t " means that the possible results of s are contained in the
set of possible results of t . This intuition is preserved when s and t are interpreted as particular
applications - and not the whole sets of possible results - by the requirement that any result
returned by (an arbitrary application of) s is also returned by some application of t.
There is a subtle difference between this and the set interpretation. Consider a user defined
choice operation #, and the two terms " #.{0, 1}" and " #.{0, 1, 2}". One would expect the set of
possible results of the former to be included in the set of possible results of the latter. But the
validity of the clause " #.{0, 1}# .{0, 1, 2}" will depend on the specification of # . Unless this
inclusion is an axiom (or a consequence of the axioms) it is not (and should not be) valid, since the
evaluation of #.{0, 1} does not require an evaluation of # .{0, 1, 2} - an acceptable implementation
would have the former always returning the value 0, while the latter could always return 2. Thus it
is not necessarily so that for every evaluation of the term #.{0, 1} there exists an evaluation of #.{0,
returning the same value. If we insisted on a fairness requirement - that for any computation,
if a particular term is evaluated sufficiently often, all its possible results would be realized - then
s#t would coincide with the subset relation between the result sets of s and t in the set approach.
We do not explore the issue of fair nondeterminism further in this paper.
The above interpretation does not contradict facts like "# .{0, 1} # .{0, 1}". This inclusion
will always be valid - for any application of #.{0, 1} (on the left) there is an application of #.{0, 1}
(on the right, namely the same one) such that the two return the same result.
Besides necessity, the aspect of possibility is present in L neq
in that we use clauses (disjunctive
lae) in specifications.
In the following section we introduce the multialgebraic semantics. In section 4 it is refined to
the function oriented semantics which expresses directly the notion of particular applications of
operations by means of oracle arguments.
3. The multialgebraic semantics
We define the semantics of L neq specifications using multistructures. Our definitions are very
similar to those used by other authors [Pickett 1967, Hesselink 1988, Hu-mann 1990, Hu-mann
1993, Kapur 1980, Nipkow 1986, Bauer 1985] except for the notion of equality.
Definition 3.1 (Multistructures). Let SP be an L neq specification. M is an SP-
multistructure if
1. its carrier _ M_ is an S-sorted set and
2. for every f: S 1 -S n #S in F there is a corresponding function
Operations applied to sets refer to their unique pointwise extensions. We let MStr(SP) denote the
class of SP-multistructures. It has the distinguished term structure:
Definition 3.2 (Term structure). The term multistructure W (
for a specification
SP=((, )) is defined as:
1. for each S#S, (W (
is the set of ground terms of sort S,
2. for each f: S 1 -S n #S in F, t i #(W (
Definition 3.3 . Let M be an SP-multistructure, b: X# _M_ an assignment to a set of
variables X. M P-satisfies a literal a under b iff
. a is s#t and b[s] # b[t]
. a is s-t and b[s] #
. a is s#t and b[s] # b[t], where A#B iff A and B are the same 1-element set.
M P-satisfies a clause C, M- P C, iff for each b, M P-satisfies at least one literal of C.
An SP-multimodel is an SP-multistructure which satisfies all the axioms of SP.
MMod(SP) denotes the class of multimodels of SP.
We let - denote the standard satisfiability relation and annotate it, as in - P , to indicate that a
particular definition of satisfiability is being used. Notice that although different occurrences of a
given (nondeterministic) term t will denote one and the same set, the interpretation of # will make
t#t false, if this set contains more than one element. The reason for using empty intersection (and
not set inequality) as the interpretation of the negative literals s -t is the same as using
"elementwise" equality as the interpretation of # . Since we avoid set equality in the positive sense,
the most natural negative form seems to be the one we have chosen. Under this interpretation #
denotes necessary equality and - denotes necessary inequality, i.e. t- s is valid only if t and s never
return the same value. For deterministic terms t and s , s-t is the same as s-t, i.e., deterministic
negative literals correspond exactly to equational (deterministic) conditions.
Initiality of the term multistructure in MStr(SP) depends on the definition of multi-
homomorphism. It is a known fact [Hu-mann 1993, Mosses 1989a] that, in the general case, one
should not expect the exis tence of initial multimodels . In [Hu-mann 1993] Hu-mann has shown
that such multimodels may not exist even if the specification language is restricted to simple
formulae. Therefore we allow general clauses in the specifications and will concentrate on the whole
class of multimodels of a specification. For the discussion of the structure of the class of
multistructures and (the lack of) initiality results, the reader is referred to [Hu-mann 1993, Walicki
1993a]. In the present context, the significance of the term structure is expressed in
Lemma 3.4 . If M is an SP-multistructure then, for every set of variables X and
assignment b: X#|M|, there exists a unique function b[]: W (,
Observe that, as a consequence of the definition of multistructures, operations in M are #-mono-
tonic, i.e., b[s]#b[t] # b[f(s)]#b[f(t)]. 6
According to definition 3.3 variables are assigned only single elements from the carrier _M_ and
so always denote individual values. This means that, for instance, the clause s-t is equivalent to
{ x-s, x-t }. Considering x to be an individual and t a set, x -t may be understood as the more
familiar x-t. Thus we may treat our notation as an abbreviation for more elaborate formulae with
two negated membership relations and one new variable (not occurring in the rest of the clause).
Because of the special role the literals of the form x-t with x#V play we will call them bindings.
As a simple example of the formalism and the important role of bindings, consider the
following specification:
Example 3.5
S: Nat
F: 0: # Nat (zero)
s: Nat # Nat (successor)
_#_: Nat-Nat # Nat (binary nondeterministic choice)
1. 0#0
2. s(x)#s(x)
3. 1-0 (As usual, we abbreviate s n (0) as n.)
4. 0#1#0 # 0#1#1
6 This is the reason for calling them "multistructures," and distinguishing them from power structures (where
operations go from power sets to power sets rather than from sets to power sets, and where operations need not be #-
monotonic).
The first two axioms make zero and successor deterministic, and the third makes 0 distinct from 1.
(Thus - serves as a limited form of negation.) In writing clause 4 one could have intended to
require that any application of 0#1 returns either 0 or 1. But according to the interpretation of
terms as arbitrary applications of the operation, it actually states for arbitrary two applications of the
term 0#1 returning the values n 1 and n 2 respectively, n 1 will be 0 or n 2 will be 1. Since these were
arbitrary pairs of applications, the ef fect would be that either every application of 0#1 returns 0 or
every such application returns 1, i.e., that choice is not really nondeterministic but merely
underspecified.
To get the desired meaning we need to state that axiom 4 holds when both occurrences of 0#1
refer to the same application . The means of binding a particular application of an operation could be
obtained by introducing additional constructs such as " let c=0#1 in ." but we prefer to keep the
language as compact as possible. The desired effect is obtained by (1) observing that the semantics
of L neq requires to assign only single values to variables, i.e., within a particular clause, a variable
will denote one specific value. And (2) by making the identification of a particular term application
with a variable in a negative literal. The variable may be then used more than once in the clause
referring to the same value returned by this particular application.
Example 3.5b
Replace axiom 4 of example 3.5 with
Axiom 4- states that for a given value x, x is either impossible as a result of 0#1, or x is 0 or 1.
Viewing 0#1 as a set (of possible results), this represents the conditional
x#1. In terms of application of operations, the axiom indicates that whenever x is the result
returned by some application of 0#1 then it equals 0 or 1.
General choice is a very natural nondeterministic operator. Unless indicated otherwise, we will
assume that it takes a non-empty, finite set as argument and satisfies the following axioms (where
"{_}" returns a 1-element set, and "add(S , y)" adds an element y to the set
Choice:
Notice the " # " in the last formula. The operational interpretation of this clause is that the
evaluation of a choice from the set add(S, y) amounts to either taking y or evaluating a choice from
the set S.
7 In order not to elaborate unnecessary details we assume here, and in the following examples, that some specifications
of the needed sorts (such as finite sets: Set, finite sequences: Seq) and operations are given.
4. Deriving deterministic specifications
In this section we define an alternative semantics of our specifications. A model M of a specification
will now be a "particular computation" or, more precisely, a standard deterministic algebra where a
nondeterministic operation is interpreted as a set of deterministic functions.
We describe a transformation of a nondeterministic L neq specification into an underspecified
determin istic specification over the equational language L deq
. The transformation preserves validity
of L neq
clauses in the sense that the model class of the derived specification satisfies a clause C iff the
class of multimodels satisfies C . The transformation goes via an intermediary language L # . L # is
L neq without inclusion, but with existentially quantified equations, and L deq is simply L neq with
equality and inequality as the only primitives.
The semantics of an L neq
specification SP can then be defined alternatively in terms of the
semantics of its L deq
transform SP- . The advantage of that is that the semantics of nondeterministic
specifications can be given in terms of standard algebraic constructions. We also consider the
validity-preserving refinement of the specification language in the transition from L neq to L deq
(together with the semantics of the latter) a plausible model for observable nondeterminism which
results from the presence of invisible parameters.
4.1. Transforming L neq
specifications into deterministic specifications.
In the following, for an L neq syntactic entity x (be it a signature, term, equation, inclusion or
clause), we let x # denote the L # transform and x- the L deq transform of x.
The main step in transforming L neq specifications is the trans formation of the nondeterministic
operators into underspecified, but deterministic, functions. This is done by equipping every
operator symbol with an additional argument called an index. 8 The index argument(s) of an L # or
L deq term identifies which application of the L neq operators the term refers to. Thus the first step is to
extend the L neq signature ( with a new index sort I and to modify the profiles of the operations:
Definition 4.1 (Index sort) . Given an L neq signature (=(S, F), the derived L #
signature ( # is the pair (S # , F # ) where:
where I is a new sort, and where every f: S 1 -S i #S i+1
in F is converted into the
corresponding f: I-S 1 -S i #S i+1 in Fi. 9
Note that we index all operations, also the ones which are supposed to be deterministic. What
8 In terms of the intended interpretation indices correspond to oracles . At the level of the derived deterministic
specification, however, they are merely additional arguments to the operations. We therefore prefer the semantically
more neutral word "index".
9 In [Walicki 1993a], where the above construction was introduced, one also added a new constant l of sort I to
ensure that the sort is not empty. This extension has also important consequences for the existence of initial/quasi-
initial semantics which was studied there. Here we merely assume that all sorts are not empty. The if_then_else_
function on index sorts is necessary only in one special case in the proof of soundness.
distinguishes deterministic operations from the nondeterministic ones in an L neq
specification is the
validity of simple equations of the form f( x)#f(x), saying that every application of the term f(x)
evaluates to the same value as every (other) application of the term f (x). In L # terms this translates
into the assertion that the index argument of f does not affect the result of its application. Thus the
corresponding are distinct variables. That is, since the
index value represents a particular application of the operation, arbitrary application is represented
by an arbitrary index value - different occurrences of terms are indexed by distinct index variables.
(As a notational convenience we shall often omit the indices of deterministic terms.) Transformation
of equalities and inequalities, in general, will conform to this schema.
Inclusion l#r is to mean that for every evaluation of l there exists an evaluation of r returning
the same result. In terms of indices this amounts to the existence, for every index i at l, of an index j
at r such that l(i) and r(j) evaluate to the same result. We transform L neq
axioms according to:
Definition 4.2. The L # transform C #
of a given L neq
, ., a m
} is obtained
as follows:
1. introduce distinct index variables for all non-variable subterms in C obtaining {a 1 #
., a m# },
2. for every inclusion l #r in C and every index variable i introduced in r #
, we add an
existential quantifier #i in front of the clause obtained in 1.
3. Finally, all symbols "# " and "# " are replaced with "=", and all " -" with "-".
For instance, let j be the axiom (from the Choice example): x- #.add(S, y) # x#y # x# .S. The L #
transform of j will be:
Note that, as a consequence of the second point of this definition, all existential quantifiers (if any)
will refer only to index variables in the positive literals of C # .
Definition 4.3 (SP #
is obtained from
SP=((, extending ( as in definition 4.1 and taking ) # ={C # | C#)}.
SP # is a deterministic specification, but clauses in ) # may contain existential quantifiers. To obtain
an equational specification in L deq
we Skolemize all L # clauses in which existential quantifiers occur
- we introduce a new indexing (Skolem) function for every existential quantifier. The L deq clause
corresponding to the clause j # is then:
y,
where s is a new Skolem function. (The Skolem functions can be simplified by removing redundant
arguments, e.g., s will not depend on i 2
(if add is deterministic) nor on x (which is determined by
Similarly, variables occurring in unique bindings can be eliminated by substitution when
constructing C
. Such simplifications have only bearing on possible implementations and we are
not concerned with them here.)
Definition 4.4 (Derived specification). Given an L neq
specification SP=((S, F), )), the
derived L deq
specification SP- is ((S-, F-) where:
is the Skolemized version of C # .
s an indexing function from ) -}.
4.2. Computations
Both SP # and SP - are ordinary first order theories, and so their classes of structures,
Str(SP -), are defined in the usual way [e.g. Chang 1977]. Models are structures that satisfy the
axioms and so the definition of the model classes, Mod(SP # ) resp. Mod(SP -), is the usual one too. By
the standard argument concerning the preservation of satisfiability by the process of Skolemization
[Chang 1977], the two model classes are equal in the sense that every M #Mod(SP # ) can be turned
into an M -#Mod(SP-) by supplying an interpretation for the indexing functions, and every
M-#Mod(SP-) can be turned into an M #Mod(SP # ) by forgetting such an interpretation.
Of course, our main concern will be with the class Mod(SP -), since SP- is as close to an
equational specification as we can get.
Definition 4.5. For an L neq
specification SP the class of SP (computational) structures,
CStr(SP), is defined to be the class Str(SP -). The (loose) semantics of SP, Comp(SP), is
defined to be the class Mod(SP -). 10
Since M#Mod(SP-) corresponds to a particular choice of functions satisfying SP, we will call the
members of Comp(SP) computations of SP.
Just like MMod(SP) did not, in general, possess an initial object, so at the level of L deq
specifications one cannot hope to find an initial algebra appropriate for the interpretation of general
clauses. The reason is well illustrated by Meseguer [Meseguer 1990, Meseguer 1992] and Wirsing
[Wirsing 1989], and is a consequence of the fact that disjunctive equations where none of the
alternatives are maximal (valid in all models) do not admit initial models. One can, however, obtain
initial algebras by banning disjunctions - i.e., by allowing only Horn formulae (as it is done in
[Hu-mann 1993] and [Mosses 1989a]).
Instead of looking for initial algebras exclusively, we therefore consider the class of all
structures sat isfying the axioms of the specification. The proponents of initial semantics may find
partial satisfaction in the proposals of generalizing this notion to quasi-initiality [Goguen 1988,
Kaplan 1987, Volger 1989a, Volger 1989b, Wolter 1992]. Quasi-initiality yields multiple non-
10 The term "computational structure" is not to be confused with the "computation structure" as used, for instance, in
[Wirsing 1989]. The latter is a synonym for "reachable structure" while computational structures as defined here are
new kinds of models of nondeterminism.
isomorphic structures, but nevertheless conforms to the dictum of "no junk - no confusion" cited as
the main justification for the initial seman tics. The results from [Wolter 1992] are directly
applicable at the level of computations - any equa tional specification with Gentzen formulae (such
as SP -) admits quasi-initial semantics. A mild restriction on the specifications allows us to lift quasi-
initial semantics to the multialgebra level [Walicki 1993a].
In order to relate the classes Comp(SP) and MMod(SP) we define what it means for a
computational structure to satisfy an L neq
(SP) formula. There are at least two alternatives here and
we record both of them:
Definition 4.6 . Let C be an L neq (SP) clause. M#CStr(SP) #-satisfies C,
The other possibility is to tighten the requirements for satisfiability of inclusions. (Recall that
existential quantifiers in C # bound, at most, index variables introduced into inclusions.) Instead of
considering an inclusion s#t satisfied if for any index value at s there exists an index value at t
making the two equal, we may require that the index at t must be a function of the index at s
denotable by the indexing functions from the translated specification.
Definition 4.7. Let C be an L neq (SP) clause, and i 1 , ., i z be all the existentially
quantified variables in C # . M#CStr(SP) C -satisfies C, M- C C, iff there exist L deq index
terms d 1
, ., d z
such that M-(C $
- is C # with all existential quantifiers
removed.
denotes the standard satisfaction for all assignments of elements from M to the
variables in the clause. Notice that d 1 , ., d z can be arbitrary terms - also single variables possibly
occurring in C
- .
To illustrate the difference between the two definitions, let s , t be two constants of sort S, and
let s be the only indexing function introduced in the translated specification SP 9. Let M#CStr(SP)
be as follows: S (b)=1, and consider the
inclusion s# t. Obviously, M - # j . s(i)=t(j) but M 2 s(i)= t(s n (i)) for any n.
The requirement of the existence of indexing terms d 1
, ., d z
rather than just existence of
elements in the carrier, will make a clause C -valid only if there exists a corresponding L deq
clause
(with the index terms d 1 , ., d z ) which is valid. This explains the relevance of C -satisfiability
- validity of an L deq clause C - will imply validity of the corresponding L neq clause C, and the former
can be examined using standard techniques. (Of course, one is still left with the problem of finding
appropriate index terms.) Obviously, for a given M, the two definitions are not equivalent. M- C C
implies M- # C , but not vice versa. However, it is an interesting consequence of the completeness
theorem that both notions of validity coincide on the class of all computations (corollary 5.3).
4.3. Comp(SP) and MMod(SP)
We have introduced computational models because, in our opinion, they offer a more operationally
intuitive interpretation of L neq
specifications than multialgebras do. The latter can be seen as a
convenient abstraction of computations and an intermediate level between the external specification
and its internal semantics.
Lemma 4.8 . Define the operator P: CStr(SP)#MStr(SP):
1.
2. f PM I }, for every f#F.
If M#Comp(SP) then PM#MMod(SP).
The P operator 11 abstracts away the information about indices and maps operations to their
respective result sets. By the lemma, every computation determines a multimodel. There will be
many computations with the same multimodel
Definition 4.9. A relation # is defined on Comp(SP) by A#B iff PA=PB.
# is an equivalence relation, and the # -equivalence class [A] corresponds to the classification of its
elements as possible computations of the program (specification) which is modeled by the
multialgebra PA. It is easy to see that, in general, an # -equivalence class does not possess initial or
terminal elements. Nonexistence of such computations is hardly surprising. We may even say that
the opposite would not be desirable. One should not expect to find "the best" (generic, initial) computation
of a nondeterministic program since such computations realize incommensurable possibilities
of the program.
Thus the opposite transition - from MMod(SP) to Comp(SP) - cannot be defined uniquely
unless we choose some arbitrary member from each equivalence class. What can be shown is that
MMod(SP) contains no "redundant" models, i.e., there are no models which do not have a
computational interpretation - every multimodel can be obtained by applying P to some
computation.
Lemma 4.10. #M#MMod(SP) #A#Comp(SP) . PA=M.
The following lemma is an easy consequence of definition 4.8 of the P-operator:
Lemma 4.11. For any A#CStr(SP) and clause C . A- # C iff PA- P C.
This, together with the previous lemmas, leads to
Lemma 4.12. For any clause C . Comp(SP)- # C iff MMod(SP)- P C.
As a consequence of the completeness theorems reported in the next section we will be able to
further strengthen the equivalence of Comp and MMod (corollary 5.3).
11 It is easily extended to a functor if we look at Comp(SP) and MMod(SP) as categories.
5. The L neq calculus NEQ for specifications of nondeterministic operators
The rules of NEQ are:
R1: a) # x-y, x#y b) # x-t, x#t x, y#V
x
s
x
x
s
x
x not in a right-hand side of # in C
(CUT) (# being either # or #)
R5:

x
at most one x in C
x denotes C with t substituted for x. A few comments regarding the rules may be in order.
the relation between - and equality and inclusion. Since variables x and y are
individuals, the two rules correspond to, respectively, x-y # x=y , and x -t # x#t. They also
capture the fact that '# ' is a partial equivalence relation and is reflexive only for variables (see
PER below).
is a paramodulation rule allowing replacement of deterministic terms (in the case when s #t
holds in the second assumption). In particular, it allows derivation of the standard substitution
rule when the substituted terms are deterministic, and prevents substitution of nondeterministic
terms for variables.
R3 allows "specialization" of a clause by substituting for a term t another term s which is included in
t. The restriction that the occurrences of t which are substituted for don't occur in the right-hand
side of # in C is needed to prevent, for instance, the unsound conclusion # p# s from the
premises # p#t and # s#t.
implies both negation of s#t and of s#t. R4 allows us to resolve these complementary literals.
R5 allows one to weaken the premise clause by extending it with additional disjuncts.
R6 eliminates redundant bindings, namely those that bind an application of a term occurring at
most once in the rest of the clause.
We will write P #C to indicate that C is provable from P with the calculus NEQ.
The following derived rules allow us to rename variables in a clause, substitute deterministic
terms for variables and introduce bindings, i.e., exchange several occurrences (applications) of a
term with one unique application of it. (x, y, z #V, t #W (,X
PER: a) # x#x b) # t#t proof: R1a, resp. R1b, and R6
x
proof: #
x
y
x
y
x

x
proof:
z t C D
z
z
x
z
x
z
x
y
x
y not in a right-hand side of # proof:

y
x
y
The INTR rule allows binding of several applications (occurrences) of a term and, for instance, to
conclude that if # h (g, g )#f(g) then # h(x , x)#f(g), x -g. Bindings reflect the computational
interpretation of operations as returning unique results and are crucial for completeness of NEQ as
the following example illustrates [Hu-mann 1993, Walicki 1993a].
Example 5.1
Let SP be (S, F,
F: a, b, g: #S f: S #S
1. a#a 2. b#b 3. a#g 4. x#h(x, x) 5. h(x, x)#f(x)
We have that MMod(SP)-
P g#f(g) and the semantic reasoning to this effect goes as
follows: for any M#MMod(SP), m#M S
4. 5. m#g ; f # -monoton.
If we did not have bindings and the ELIM rule, this inclusion would not be derivable.
With R3 we can only obtain x#f(x), from which R5 gives {x-g, x#f(x)}. But since g#g
is not derivable we cannot substitute g for x.
The reasoning can proceed only if it can consider "elementwise" transitions. The
derivation in NEQ proceeds as follows:
INTR
The example illustrates the significance of making explicit the distinction between operations and
their applications, since this distinction plays a crucial role at the semantic level.
The main new result concerning the two semantics and the calculus is:
Theorem 5.2. For every L neq
specification SP=((, )) and clause C#L neq
(SP),
Soundness is proven by induction on the length of the proof ) #C. Completeness in 1) is not
proven directly but via the derived deterministic semantics and completeness in 2).
Corollary 5.3. For every L neq
specification SP=((, )) and clause C#L neq
Comp(SP)- C C iff Comp(SP)- #
The implications from left to right are easy consequences of the definitions of satisfiability, and the
completeness theorems yield the equivalence MMod(SP)- P C iff Comp(SP)- C C.
That - # implies - C is, perhaps, not surprising in view of the fact that Comp(SP) is closed under
subalgebras. Thus if all computations #-satisfy a clause C (i.e., its existentially quantified version
reachable computations will # -satisfy C. In particular, the initial covering of the class
Comp(SP), i.e., all computations initial in their respective component of the class, will satisfy C.
This means that the index terms whose interpretation in a quasi initial object I 0 gives I 0 - C C can be
used to validate C in other computations to which there exists a unique homomorphism from I 0
Corollary 5.3 significantly strengthens such an argument. There is an obvious difficulty with
applying the above argument to negative formulae as they are not necessarily preserved under ho -
momorphisms [Lyndon 1959]. More importantly, the above reasoning does not guarantee that for
an existential quantifier in C # there will exist one index term - the terms may be different in
different components of Comp(SP). But the corollary implies that if in all computations
(multimodels) the result set of an operation s is included in the result set of an operation t then
computing s really depends on computing t - there exists an index term d(i) such that s(i)=t(d(i)).
The corollary shows also that Comp(SP) and MMod(SP) satisfy the same L neq (SP) formulae.
Hence the former constitutes a refinement of MMod(SP) only in so far as the language is concerned.
contains more detailed description of the operations using new indexing functions which are
not present in L neq
6. An Example
As an example of our formalism we give a specification of an access data type. Nondeterminism
provides here an invaluable abstraction mechanism which releases the specifier from the burden of
describing exactly the mechanism of allocating new pointers. This leads not only to a more abstract
specification but also avoids the problems of distinguishing the structures which are supposed to
have the same observational behavior. Motivation for this example comes from [Meldal 1987,
Meldal 1989]. First, we illustrate the problems arising in the case of the usual deterministic
underspecification and then show how they can be avoided by introducing nondeterministic
operations.
We have the following sorts and operations: sort A of the accessed values, sort P A of access
values (pointers), and sort C A
which is a collection of access values P A
. Collections were introduced
by Hoare and Wirth in [Hoare 1973]. An access value serves here as an index to a set of the
referenced type. Changes to a referenced object as well as allocation of new objects are considered
changes to the collection in a way quite similar to the treatment of arrays.
The operation Init produces a new, empty collection, St(ore) takes a collection, an access value
and an object and allocates the object with the given access value returning a new collection, Next
gives an access value of the next object to be allocated in the current collection, and Acc(ess)
accesses the value through a given access value. Finally, the operation New allocates a new object
with the given access value in a collection and returns the extended collection.
To simplify the example we will ignore things like NIL pointers with no accessed value,
deallocation and the problems of limited storage space. First we give a deterministic underspecified
version to illustrate the need for a more sophisticated abstraction mechanism. To mimic as far as
possible the expressiveness of L neq we allow here use of equalities, inequalities and disjunctions.
D-POINTER is
S: { A, P A , C A }
{ # A (an error value)
Next_: C A # P A
New_: C A - A #C A
. x, y: P A
, a, b: A # V
P: { 1. St(St(C, x, a), y, b) # St(St(C, y, b), x, a), x#y
2. St(St(C, x, a),
Acc: 3. Acc(St(C, y, a), x) # Acc(C, x), x#y
4. Acc(St(C, x, a), x) # a
5. Acc(Init, x) #
Next: 6. Acc(C, Next(C)) #
New: 7. New(C, a) # St(C, Next(C), a) }
The first axiom tells that the order in which objects are allocated is inessential as long as they have
different access values. 2. makes the last St operation at access value x override all previous ones.
(These two ax ioms are equivalent to the conditional St(St(C, x, a), y, b) # if x=y then St(C, y, b) else
St(St(C, y, b), x, a).) Accessing a value x goes along the nesting of St until the access value equal to x
is found or until the Init collection is reached. In the latter case # is returned indicating that x has
not been allocated. Axiom 6. ensures that Next does not return an allocated value.
Axiom 7. defines the New operation in the expected way. Since this operation is fully defined in
terms of St and Next , it might be considered merely a convenient abbreviation. However, it is
natural to assume that this is the operation we are actually interested in - the operation Next is
needed to define it. Observe that New does not return a pointer but merely modifies the collection.
It is the general assumption of algebraic specifications that all operations return result of one sort.
Hence, if one wanted to define one operation which does both - modifies the collection and returns
a new pointer - one would define an additional sort corresponding to the cartesian product
[C A -P A ] with appropriate projection functions _ 1 and _ 2 . Although this might be closer to a
programmer's intuition, it would unnecessarily complicate the example. Introducing an operation
Alloc: C A -A # [C A -P A
would require, for instance, reformulation of the axiom 6. as Acc (C,
cluttering the example with projection functions. We refrain from
making this complication because the operations New and Next play the role of such projections,
and one may easily introduce the sort [C A - P A ] and an operation Alloc at a later stage of
development of an implementation from the specification D-POINTER.
It seems that the underspecification D-POINTER puts reasonable restrictions on the possible
implementations. In particular, axiom 1. makes the collections abstract - the sequence in which
new objects are allocated is not essential. However, consider the following two expressions, where
a-b are constant accessed values:
1. New(New(C, a), b) # St(St(C, Next(C), a), Next(St(C, Next(C), a)), b)
2. New(New(C, b), a) # St(St(C, Next(C), b), Next(St(C, Next(C), b)), a)
The former stores first an a (at the Next access value) and then a b (again at Next), while the latter
stores first b and then a. Simple equational reasoning yields
1a. Acc( New(New(C, a), b), Next(C) ) # a
2a. Acc( New(New(C, b), a), Next(C)
and then, a-b implies the antecedent of the following implication (which follows from
Next(C)#Next(C) by the congruence axiom for
# New(New(C, a), b)-New(New(C, b), a)
To illustrate the problem, we may rephrase this in terms of an imperative program. Assume some
Pascal-like language with a command allocate(var coll: C A ; v: return P A . A call to allocate(C, v)
does three things: (1) returns an access value to a new object in the col lection C, (2) stores the value
v in that object, and (3) changes C appropriately. (It may be thought of as an operation which in
virtue of (2) and (3) implements New.)
1. Z := C; 2. Z := C;
(The program variable Z is used to capture the state of the collection before the allocations occur.)
In terms of the operations from the specification, we might formulate these as:
1. Z := C; 2. Z := C;
y, b);
y := Next(C); C := St(C, y, b); x := Next(C); C := St(C, x, a);
These two sequences of commands should be equivalent for all purposes. Yet, after executing
sequence 1. we have that x=Next(Z), but this is not the case after execution of 2. which yields
x=Next(St(Z, Next(Z), b)). The problem is that the function Next essentially counts the number of
objects that have been stored, identifying uniquely an access value by its place in the sequence of
allocations. The language of deterministic operations is too expressive, forcing us to consider details
beyond what is necessary for our purposes. The problem might be avoided by designing more
specific "storage structures" but this would be more suitable for a definition of programming
language semantics rather than specification. Alternatively, one might introduce a more abstract
notion of "observational equivalence" [Hupbach 1983, Sannella 1985] (e.g., with respect to the
operation Acc) in order to consider the two programs equivalent.
The example illustrates the general problem of abstraction from some low-level details which
are irrelevant at the actual level of description. Underspecification does not allow, in general, for
abstraction from conceptually invisible entities (such as hidden state, timing or interaction with a
human being). In this case it forces one to distinguish two expressions because of the internal
structure of their arguments (the order of allocating pointers) which may correspond to a hidden
state. (We discuss this problem in more detail in [Walicki 1994a].)
A simple way out is to avoid identifying different occurrences of Next(Z) as referring always to
the same unique value, i.e., to consider it as a nondeterministic operation. The only change to the
specification D-POINTER would then be in the last axiom:
POINTER is
as in D-POINTER
St(C, x, a)#St(C, x, a)
New: 7. New(C, a) # St(C, Next(C), a) }
Only Acc , St and # are deterministic. Since Next has become nondeterministic, the New operation
becomes nondeterministic, too. Also, we no longer have the identity Next(C)#Next(C), but only
equivalence (by PER): Next(C)#Next(C). 12
Now, if a is a defined accessed value, it is reasonable to admit the axiom a-#. Using that and
axioms 4. and 6. we obtain:
INTR
Acc St C x a Next St C x a
x Next St C x a Acc St C x a x a
x Next St C x a Acc St C x a x a Acc St C x a x a
x Next St
Using this fact we get the two clauses:
1b.
2b.
which lead to the following conclusion (assuming a-b):
12 s#t is an abbreviation for two inclusions: s#t and t#s.
a b
x Next C Acc St St C x a Next St C x a b x b
x Next C Acc St St C x a Next St C x a b x Acc St St C x b Next St C x b a x
x Next C Acc New St
where the last line is obtained by two applications of R3 from axiom 7. However, this does not
imply New(New(C, a), b) - New(New(C, b), a). Observe also, that the conclusion follows only
because we have identified the bindings x-Next(C) from 1b and 2b - x in the conclusion is
supposed to be the same when returned by the Next(C) called from St(C, Next(C), a) and from St(C,
Next(C), b).
Thus we cannot establish that the two collections are disjoint (distinct), but we cannot prove
that they are identical either, i.e., POINTER 0 New(New(C, a), b) # New(New(C, b), a). Even the
simpler equality St(C, Next(C), a) # St(C, Next(C), a) would be too strong (and does not follow
from the POINTER axioms) since the two applications of Next(C) may allocate a at different access
values.
Adding the axiom New(New(C, a), b) # New(New(C, b), a) would make the two collections
equivalent, in the sense that whatever is the collection resulting from New(New(C, a), b) could be
also obtained from New(New(C, b), a) and vice versa. We would then have New(New(C, a), b) #
New(New(C, b), a) but still could not prove this formula with # instead of #.
One might wish to specify an "ideal" access type which, in analogy with the typical specifications of
natural numbers, has an unlimited resource of access values.
U-POINTER is
as in POINTER
Next:
8. Next(St(C, x, a)) # Next(C)
9. x-Next(C), x # Next(St(C, y, b)), x#y
According to axiom 8. any access value which is not allocated in St(C, x, a), i.e., which can be
returned by Next(St(C, x, a)), is not allocated in C either (and so can be returned by Next(C) as
well). 9 is the reverse of that saying that any access value x which is available as a possible result of
Next(C) is also available from the extended collection St(C, y, b) provided that x is different from y.
Interestingly, with these axioms we can establish, for instance, the equivalence Next(St(C, x, a))
# Next(St(C, x, b)) which says that the choice of the Next access value to be allocated does not
depend on the accessed values stored in the collection:
I
z Next St C x a z Next St C x b z x
x Next St C x a
x z z Next St C x a
z Next St C x a z Next St C x b
Next St C x a Next St C x b
NTR
The other direction can be now proved by REN.
7. Conclusions and related work
We have defined a formalism suitable for specifying nondeterministic operators. In distinguishing
between terms and their applications, we have focused on the observational aspect of programs, on
their computations (which is what one observes when evaluating a program). We have introduced
the calculus NEQ and given the first proof of completeness for multialgebraic semantics.
We have given a procedure for interpreting a specification of a nondeterministic system in
terms of an underspecified equational system within a classical conditional equational logic
extended with dis junction. The translation yields a specification over a refined language and enables
us to define a function oriented, computational semantics. We feel that the latter has a more
plausible computational interpretation and reflects our intuition about evaluations of
nondeterministic programs. The computational semantics is non-intrusive with respect to the
algebraic semantics of deterministic constructs, in the sense that it does not require a change of
existing models. This is in contrast to a move to a relation- or set valued model which does have an
impact on the model of deterministic functions, whereas our understand ing of nondeterminism
retains a standard function oriented model.
A deterministic interpretation of nondeterministic specifications can be found in some earlier
works [Kapur 1980, Subrahmanyam 1981]. They used only simple equations (interpreted as set
equalities) and specified a nondeterministic operation f by means of the associated characteristic
predicate expressing that x is a possible result of f. Translation of an equation s =t was
semantically equivalent to our intermediary translation step (def 4.3) for two inclusions, and the
characteristic predicates were used for binding results of applications of nondeterministic terms:
Our derived specifications are based on further Skolemization of such formulae and yield a new
semantics where nondeterminism is made explicit in form of the index arguments. Furthermore,
[Kapur 1980, Subrahmanyam 1981] did not address the problem of referential opacity of
nondeterministic terms at the level of the specification language. Reasoning had to be carried out at
the level of the derived deterministic formulae in full first-order logic.
We have also shown that the refinement of the specification language to the level of indexed
functions is compatible with the multialgebra semantics. On the one hand, any multimodel has a
computational interpretation and, on the other, multisemantics can be used as a correct abstraction
tool in cases when such an abstraction from the computational semantics is needed. Both
multimodels and functional models of a specification SP satisfy the same formula of L neq
(SP).
Some of the more recent work on algebraic specifications of nondeterminism bears some
similarities to the approach presented in this paper.
An elegant construction - unified algebras - has been proposed by Mosses in [Mosses 1989a,
Mosses 1989b]. The unified algebras provide quite general and flexible semantic tools.
Nondeterministic choice is modeled as a separate sort comprising exactly the possible results. (This
is very similar to our nondeterministic constants.) The language allows variables to refer to arbitrary
applications of the operations (as in our bindings) in which case they must be interpreted as
individuals (unique results) in the semantic domain. In addition, unified algebras represent one of a
few algebraic approaches supporting both singular and plural ("call-time-choice" and "run-time -
choice") semantics of parameter passing. (We have given an account of this distinction in a multi-
and poweralgebraic framework in [Walicki 1994a,Walicki 1994b].) In spite of the similarities at the
language level, the semantics leading to such flexibility is very different from ours. In particular, it
completely changes the traditional notion of a model - also in the cases when specifications involve
only deterministic functions.
In [Hu-mann 1988, Hu-mann 1993] Hu-mann uses the standard generalization of algebras to
multialgebras as the semantics of nondeterminism. The primitives of his specification language are
analogous to the primitives of the language L neq . They comprise inclusions and a determinacy
predicate (where the assertion DET(t) corresponds to our t# t). The rewriting systems designed for
such specifications provide an excellent example of a very constructive approach to reasoning about
nondeterminism. Unfortunately, several restrictions must be put on the specifications in order to
prove even a limited form of completeness, and the full completeness result is still lacking. (NEQ
can be used to show which extensions are needed to Hu-mann's calculus and theorem 5.2 yields
then the desired completeness theorem [Walicki 1992].) The language and the calculus given by
Hu-mann can be constructed as special cases of ours. In fact, general clauses in our language and
calculus can be restricted, for instance to those having only a single positive formula, without
impairing the results obtained for the general case. It is an open problem whether the system
implemented by Hu-mann [Hu-mann 1985] can be accommodated to this more general context.
In the recent work [Kriauciukas 1994], an alternative and extended version of NEQ is given which
also includes rewriting.
Unlike our approach, both Mosses and Hu-mann succeed in construction of initial models.
However, it turns out that initial semantics for nondeterministic specifications tend to introduce
redundant elements, thus violating the "no junk" dictum of the original initial approach [Walicki
1993b]. In our formalism, disjunction provides sufficient means for eliminating "junk" and leads to
more intuitive semantics.

Acknowledgment

The paper was significantly improved thanks to the suggestions of the anonymous referees. We are
particularly grateful to one referee whose proposal to recast the original sequent based presentation
in terms of clauses made both the logic and proofs simpler and more elegant.
The first author thanks Norwegian Research Council for the financial support during the work
on this paper.



--R

"Testing Equivalencies for Event Structures"
The Munich Project CIP: The Wide Spectrum Language CIP
"Algebra of communicating processes"
"On the Structure of Abstract Algebras."
Model Theory
"Rewriting Systems"
A Discipline of Programming
Fundamentals of
"Completeness of Many-Sorted Equational Logic"
"Universal realization, persistent interconnection and implementation of abstract modules"
"Remarks on Remarks on Many-Sorted Equational Logic"
What is unification?
"On Observing Nondeterminism and Concurrency"
"Observing Processes"
"A Mathematical Approach to Nondeterminism in Data Types"
"An axiomatic definition of the programming language PASCAL"

Rapid prototyping for algebraic specifications - RAP system user's manual
"Nondeterministic algebraic specifications and nonconfluent term rewriting"

Nondeterminism in Algebraic Specifications and Algebraic Programs
"Equations and Rewrite Rules: A Survey"
"On Behavioural Equivalence of Data Types"
"The semantics of a simple language for parallel programming"
"Conditional Rewriting"
"Rewriting with a Nondeterministic Choice Operator"
Towards a theory of abstract data types
Reasoning and Rewriting with Set-Relations I: Ground Case
"Properties Preserved under Homomorphism"
The Semantics of Nondeterminism
Allocations of Objects Considered as Nondeterministic Expressions
"An Abstract Axiomatization of Pointer Types"
"Conditional Rewriting Logic: Deduction, Models and Concurrency"
"Conditional rewriting logic as a unified model of concurrency"
Calculi for Communicating Systems
"Unified Algebras and Institutions"
"Unified Algebras and Action Semantics"
"Non-deterministic Data Types: Models and Implementations"
"Observing nondeterministic data types"
"Computing in Systems Described by Equations"
"Homomorphisms and subalgebras of multialgebras"
"Referential Opacity In Nondeterministic Data Refinement"
"On Observational Equivalence and
"Nondeterminism in Abstract Data Types"
"The semantics of disjunctive deductive databases"
The Semantics of Disjunctive Deductive Databases
Calculii for nondeterministic specifications: three completeness results
Algebraic Specifications of Nondeterminism
"Initiality+Nondeterminism => Junk"
"Multialgebras, Power Algebras and Complete Calculi of Identities and Inclusions"
Singular and Plural Nondeterministic Parameters: Multialgebras
"An introduction to event structures"


"Beyond Conditional Equations"
--TR
Communicating sequential processes
Non-deterministic data types: models and implementations
The Munich Project CIP: Volume I: the wide spectrum language CIP-L
On observational equivalence and algebraic specification
Remarks on remarks on many-sorted equational logic
Testing equivalences for event structures
A mathematical approach to nondeterminism in data types
Rewriting with a nondeterministic choice operator
Observing nondeterministic data types
Unified algebras and action semantics
Fundamentals of algebraic specification 2: module specifications and constraints
Unified algebras and institutions
The semantics of disjunctive deductive databases
Algebraic specification
Conditional rewriting logic as a unified model of concurrency
Nondeterminism in algebraic specifications and algebraic programs
Referential opacity in nondeterministic data refinement
A Calculus of Communicating Systems
Computing in Systems Described by Equations
A Discipline of Programming
Multialgebras, Power Algebras and Complete Calculi of Identities and Inclusions
Nondeterminism in Abstract Data Types
Universal Realization, Persistent Interconnection and Implementation of Abstract Modules
Nondeterministic Algebraic Specifications and Nonconfluent Term Rewriting
Reasoning and Rewriting with Set-Relations I
Process theory based on bisimulation semantics
An introduction to event structures
Conditional Rewriting Logic
On Observing Nondeterminism and Concurrency
Observing processes
Allocations of Objects Considered as Nondeterministic Expressions - Towards a More Abstract Axiomatics of Access Types
Completeness of many-sorted equational logic

--CTR
Yngve Lamo , Micha Walicki, Quantifier-free logic for nondeterministic theories, Theoretical Computer Science, v.355 n.2, p.215-227, 11 April 2006
Michal Walicki , Manfred Broy, Structured specifications and implementation of nondeterministic data types, Nordic Journal of Computing, v.2 n.3, p.358-395, Fall 1995
Beata Konikowska, Rasiowa-Sikorski deduction systems in computer science applications, Theoretical Computer Science, v.286 n.2, p.323-366, 17 September 2002
Stefan Ratschan, Convergent approximate solving of first-order constraints by approximate quantifiers, ACM Transactions on Computational Logic (TOCL), v.5 n.2, p.264-281, April 2004
Andrea Corradini , Fabio Gadducci, A functorial semantics for multi-algebras and partial algebras, with applications to syntax, Theoretical Computer Science, v.286 n.2, p.293-322, 17 September 2002
Micha Walicki , Sigurd Meldal, Algebraic approaches to nondeterminisman overview, ACM Computing Surveys (CSUR), v.29 n.1, p.30-81, March 1997
algebraic specifications;reasoning with nondeterminism