1 (h.fg) Algorithms

Define some variant of ND-language – give it “operational” interpretation – describe algorithms.

Nonmonotonic logic for states? (without defaults, just with assignments)

2 (h.fg) CSP

Given a multialgebra M determine/describe/characterize the class of its complete determinizations. Perhaps, give a construction of a complete determinization of M.

See how to use it for defining/modelling constraint-satisfaction-problem – a determinization of M should be a solution to the problem modelled by M.

Given a set B of primitive (basic) relations – is there a complete set of relational operators allowing to define all possible relations “extractable” from B (what does it mean? cf. Jeavons invited paper in CP’98, LNCS 1520).

3 (h.fg) Distributed Algebras

cf. Communication algebras. Essentially: define a homomorphism A → B where several values in A jointly represent a value in B and where several functions in A jointly represent (are mapped to) one function from B. This is more than traditional data-refinement. Use it for parallellisation – in context of CAs?

3.1 – cf. 6 Possibly, define implementation along a homomorphism induced by ι : Σ_{SP} → T_{Σ_{IM}}.

4 (PhD) Action refinement via nondeterminism

Events are actual events; their descriptions use only abstract labels. Idea: A1(a) ≺ b is A1(a) ⊆ b and reads as “after a (i.e., A1(a)) a b must follow”.

sorts: E(vents)
opers: a, b, c, … → E (event labels)
A1: E → E  (after)
A2: E × E → E (after 2 events)
…

and axioms using ND-logic

x ≺ a ⊢ A1(x) ≺ b, A1(x) ≺ c
⊢ A1(a) ≺ ⊔.{b, c}
⊢ A1(a) ≺ b, A1(a) ≺ c

A1(a) ≺ c ⊢ i.e.,

after any a, there follows either b or c (or both) after any a, there follows either b or c (but not both ?) either after all a follws b or after all a follows c c never follows after a

4.1 (h.fg.) Algebraic Basics

1. define language,

2. define dual semantics: multialgebra & process (is “after” ‘immediate’ after or ‘eventually’ after? – multialgebraically, it is rather ‘eventually’ – hence 1. below might work.)

3. add parallell composition –

4. see how it relates to ACP, PA, ...

4.2 ...and then

1. Will the refinement for multialgebras give a decent action refinement notion?

2. Is “after” ‘immediate’ after or ‘eventually’ after? (multialgebraically, it is rather ‘eventually’ – hence 1. can work.)

3. Can we make it sufficiently expressive/relevant ?

Can try Russell’s theory of moments-as-events, or its refinements...

5 (???) Algebras for Multialgebras

Two ways of obtaining “nondeterministic” power-set algebras from algebras. Given an A ∈ Alg(Σ) :

1. extend it to an algebra P A over ℘(A) by:

(a) c^{P A} =^{def} {c^{A}}

(b) f^{P A}(X_{1}, …, X_{n}) =^{def} ⋃{f^{A}(x_{1}, …, x_{n}) : x_{i} ∈ X_{i}}.

Here, we get that for all ground terms t ∈ GT_{Σ} : |t| = 1.

2. make a multialgebra by taking a quotient by an equivalence instead of a congruence. Here, constants remain deterministic, but this may be perhaps treated somehow by introducing new elements into the carrier, possibly, modelling constants in the multialgebra by operations taking “hidden” arguments.

Try to, for one or both of these possibilities,

• determine one/class of algebras for a given multialgebra in 2., is any multialgebra M ⇀ ↽ A/_{∼} for some algebra A and equivalence ∼?

• see under what conditions this makes sense: is it always possible? does it always follow a natural (not too arbitrary) construction? if not, then when?

• see what implications this may have if we then transfer other notions (homomorphisms…) and results (initiality…) from algebras to multialgebras in 1., this is the question (Brink, etc.) of preservation of properties under transition to power structures – can it be expressed in terms of 1-element identity?

• say if it is reasonable to consider a category of (multi)algebras with quotients by equivalences instead of congruences: the notion of homomorphism, …?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Used . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 (h.fg) Implementation via morphism SPEC → IMPL

(Bjørn Tore) Instead of abstraction function, try to define implementation I of a specification SP by a signature morphism ι : Σ_{SP} → T_{Σ_{IM}}.

7 (h.fg) Implement a generic proof-checker (Adugna)

User definable: 1. term and formulae syntax (?),

2. rules over 1. and proof-syntax (?)

8 (h.fg) Cats of multialgs (Adis)

Properties of the categories of mults. with remaining compositional homs (from the theorem).

9 (PhD) PA’s as MA’s (Yngve)

Model a partial algebra A not as a multialgebra Â, where for f : S → T, f Â(x) = Ø ⇔ x ∉ dom(f^{A}) but by one where f Â(x) = TÂ ⇔ x ∉ dom(f^{A}), i.e., partiality means complete unpredictability.

9.1 ND for behavioral abstraction (Yngve ?) See - Jo’s application to NFR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vague or old . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10 (???) ND for implementation

cf. Peter Mosses

11 (???) Hyperidentities to model ND

12 (???) ND for graph part of CA

13 (PhD) General relational algebra (allegories?)

Extend, as far as possible, Jónsson-Tarski’s relational algebra to relations of arbitrary arities – in particular, what is/should be the meaning of relational composition, complement, inverse, etc. in this generalized context (cf. Allegories).

See how much of appliations of relations could be captured in this way?

1. relational structures – Boolean composition of relations

2. relational databases – joins, projections etc.

3. (hyper)graphs as relations [?, ?] – graph operations.