23
Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer, schrittweise Spezifikation von ADT Definition „Kombination“ Es sei SPEC SPEC = (, E) eine Spezifikation mit einer S-sortigen Signatur . Hier ist = ( w,s ) w S*, s S (vgl. Kap. 2) SPEC* SPEC* = (*, E*) heißt eine Kombination aus SPEC SPEC und der Ergänzung (S 0 , 0 , E 0 ), wenn S 0 eine Menge (neuer) Sorten, 0 eine (S S 0 )-sortige Signatur und E 0 eine Menge von ( 0 )-Gleichungen ist, und es gilt

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Embed Size (px)

Citation preview

Page 1: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1

Kapitel 12

Erweiterung von Gleichungsspezifikationen

• Ziel: modularer, schrittweise Spezifikation von ADT Definition „Kombination“

Es sei SPECSPEC = (, E) eine Spezifikation mit einer S-sortigen Signatur . Hier ist = (w,s)w S*, s S (vgl. Kap. 2)

SPEC*SPEC* = (*, E*) heißt eine Kombination aus SPECSPEC und der Ergänzung (S0, 0, E0), wenn S0 eine Menge (neuer) Sorten, 0 eine (S S0)-sortige Signatur und E0 eine Menge von ( 0)-Gleichungen ist, und es gilt *= 0, E*= E E0 . Schreibweise: SPEC* SPEC* = SPECSPEC + (S0, 0, E0)

S0 , 0 , E0 können auch leer sein, bezeichnet die disjunkte Vereinigung. (S0, 0, E0) selbst ist i.a. keine Spezifikation

Page 2: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 2

Beispiel 1:boolbool = sorts bool

oprs true, false : bool not : bool bool and, or, implies : bool, bool bool

var p, q : bool eqns not(true) = false not(false) = true not(not(p)) = p and(true, p) = p and(false, p) = false and(p, q) = and(q, p) or(p, q) = not(and(not(p), not(q))) implies(p, q) = or(not(p), q) end boolbool

Page 3: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 3

Beispiel 1 (Forts.)Bilde Kombination durch Ergänzung von boolbool : ternaryternary = boolbool + oprs maybe : bool

eqns not(maybe) = maybe and(true, maybe) = maybe and(false, maybe) = false or(true, maybe) = true end ternaryternary

• Absicht: 3-wertige Logik Was passiert? Zu ADTADTboolbool gehört Tboolbool mit genau 2 Kongruenzklassen als Elementen: [true], [false].Tternaryternary besitzt die 3 Elemente [true], [false], [maybe].

Page 4: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 4

Beispiel 1 (Forts.) Zu Tternaryternary gehören aber auch noch die Elemente [or(maybe, maybe)], [or(maybe, or(maybe, maybe))], [or(maybe, or(maybe, or(maybe, maybe)))] ... usw. Statt 3 Werten hat man unendlich viele Elemente spezifiziert!Die Gleichung (oder eine geeignete andere) or(maybe, maybe) = maybehätte dies verhindert.• Achtung: Initiale Semantik kann durch ein (kleines) Versehen viel zu viele Elemente erzeugen! In der Regel will man durch Hinzunahme neuer Sorten, Operatoren und Gleichungen die Eigenschaften und Anzahl der ursprünglichen Elemente nicht verändern!

Page 5: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 5

Beispiel 2Betrachte die früheren Spezifikationen natnat und boolbool und bilde: orderorder = natnat + boolbool + oprs : nat, nat bool var m, n : nat

eqns (0 n) = true (suc(n) 0) = false (suc(n) suc(m)) = (n m) end orderorderBei dieser „Erweiterung“ von natnat + boolbool entstehen keine neuen Elemente. Denn die neuen Gleichungen verändern die „Zahlen“ [sucn(0)] nicht. Es entstehen auch keine neuen Elemente der Sorte bool. Denn jeder Term der Sorte bool der Gestalt (t1 t2) läßt sich durch die Gleichun-gen aus natnat in (t1* t2*) umformen mit suc-Termen t1*, t2*, und dann mit den neuen Gleichnugen in true oder false.

Page 6: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 6

Beispiel 3Es ist auch möglich, daß durch eine solche "Kombination" ursprüngliche Elemente weg- bzw. zusammenfallen.Betrachte z.B. die Kombination testbooltestbool = boolbool + eqns implies(true, false) = true end testbooltestboolHier erhält man

[true] = [false],denn es gilt dann true E* implies(true, false) E* or(not(true), false) E* or(false, false) E* not(and(not(false), not(false))) E* not(and(true, true)) E* not(true) E* false .

Damit ist diese Kombination keine „Erweiterung“ von boolbool .

Page 7: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 7

• Ziel: Untersuchung, wann eine Kombination tatsächlich eine echte Erweiterung der ursprünglichen Spezifikation darstellt.

Definition „Redukt“

Es sei SPECSPEC = (, E) eine Spezifikation und SPEC*SPEC* = SPECSPEC + (S0, 0, E0). Das SPECSPEC-Redukt von TSPEC*SPEC* ist die -Algebra

(TSPEC*SPEC*)SPEC SPEC = [(TSPEC*SPEC*)SPECSPEC , (f*) ]

mit (TSPEC*SPEC*)SPECSPEC

= (TSPEC*SPEC*, s)sS

(Nur die Sorten und Operatoren, die auch in SPECSPEC vorkommen!)

Page 8: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 8

Mit diesem Begriff läßt sich nun eine echte Erweiterung vernünftig definieren.

Definition „Erweiterung“

Eine Spezifikation SPEC*SPEC* heißt eine Erweiterung der Spezifikation SPECSPEC genau dann, wenn

(TSPEC*SPEC*)SPECSPEC TSPEC SPEC .

Bei den vorangegangenen Beispielen trifft diese Bedingung

offensichtlich nur auf das Beispiel 2 zu.

Page 9: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 9

Die Bedingung(TSPEC*SPEC*)SPECSPEC

TSPECSPEC

für eine Kombination, eine Erweiterung zu sein, ist eine semantische Bedingung. Denn es ist im wesentlichen Isomorphie für gewisse Faktor-algebren zu überprüfen. Aber sowohl Homomorphismen als auch Kongruenzen entsprechen Semantik!

Deshalb ist folgender Satz nicht verwunderlich:

Die Frage, ob eine Spezifikation SPEC*SPEC* eine Erweiterung einer Spezifikation SPECSPEC ist, ist im allgemeinen unentscheidbar.

Suche nach hinreichenden Kriterien

Page 10: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 10

Definition „vollständig, konsistent“

Es sei SPECSPEC = (, E) eine Spezifikation und SPEC*SPEC* = SPECSPEC + (S0, 0, E0). h sei der eindeutig bestimmte Homomorphismus 1)

h : TSPECSPEC (TSPEC*SPEC*)SPECSPEC .

Dann heißt SPEC*SPEC* vollständig bezüglich SPECSPEC genau dann,

wenn h surjektiv ist, und konsistent bezüglich SPECSPEC genau dann,

wenn h injektiv ist.

1) Beachte, daß beides (, E)-Algebren sind, und T,E in der Klasse Alg,E initial ist.

Page 11: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 11

Beispiel Man überzeugt sich leicht davon, daß bei den vorangegangenen drei Beispielen gilt:• ternaryternary ist bezüglich boolbool konsistent, aber nicht vollständig. • orderorder ist bezüglich natnat + boolbool konsistent und vollständig. • testbooltestbool ist bezüglich boolbool vollständig, aber nicht konsistent.

Trivialerweise gilt der Satz:

Konsistenz und Vollständigkeit:

SPEC*SPEC* ist eine Erweiterung von SPECSPEC genau dann, wenn SPEC*SPEC* bezüglich SPECSPEC konsistent und vollständig ist.

Beweis: Ein Homomorphismus h ist Isomorphismus genau dann, wenn h surjektiv und injektiv ist.

Page 12: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 12

Beispiel Beim Entwurf von Spezifikationen können sehr leicht inkonsistente Kombinationen entstehen:

set(nat)set(nat) = natnat + sorts setoprs : set

insert : set, nat setvar s : set

m, n : nat(1) eqns insert(insert(s, n), n) = insert(s, n)(2) insert(insert(s, n), m) = insert(insert(s, m), n)end set(nat)set(nat)

Nun soll noch eine Lösch-Operation hinzukommen. Wie könnte man da diese Spezifikation noch „erweitern“?

Page 13: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 13

Beispiel (Forts.)Man muß einen zusätzlichen Operator einführen und dessen Eigenschaften durch geeignete Gleichungen beschreiben:

newset(nat)newset(nat) = set(nat)set(nat) +

oprs del : set, nat setvar s : set

n : nat(3) eqns del(, n) = (4) del(insert(s, n), n) = send newset(nat)newset(nat)

Sieht vernünftig aus - oder?

Page 14: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 14

Beispiel (Forts.)Leider funktioniert dies nicht in der offenbar gewünschten Weise.Denn es ergibt sich „dummerweise“:

E* del(insert(, n), n) wegen (4)

E* del(insert(insert(, n), n), n) wegen (1)

E* insert(, n) wegen (4) Die Gleichung (1) läßt sich wie alle anderen ja auch von rechts nach links verwenden.

Damit hat die Operation insert keine Wirkung mehr!

Die Sorte set besteht nur noch aus einem einzigen Element: [] !Die Spezifikation newset(nat)newset(nat) ist bezüglich set(nat)set(nat) inkonsistent!

Page 15: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 15

Lemma:Falls SPEC*SPEC* = SPECSPEC + (S0, , ), so ist SPEC*SPEC* eine Erweiterung von SPECSPEC .

Beweis: trivial

Lemma:Wenn SPEC*SPEC* eine Erweiterung von SPECSPEC ist, und SPEC**SPEC** eine Erweiterung von SPECSPEC*, so ist SPEC**SPEC** auch eine Erweiterung von SPECSPEC .

Beweis: gilt wegen der Eigenschaften bei Nacheinanderausfüh-rung von Homomorphismen

Page 16: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 16

Definition „Anreicherung“

Gilt SPEC*SPEC* = SPECSPEC + (, 0, E0), so heißt SPEC*SPEC* eine Anreicherung von SPECSPEC .

Wegen der obigen Lemmata genügt es, die Suche nach hinreichenden Kriterien

dafür, daß eine Kombination eine Erweiterung ist, auf Anreicherungen zu beschränken. Das heißt, wir suchen nun Kriterien für die Vollständigkeit und Konsistenz von Anreicherungen.

Page 17: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 17

Vollständigkeit und Konsistenz von Anreicherungen:

Es sei SPEC*SPEC* eine Anreicherung einer Spezifikation SPECSPEC, SPEC*SPEC* = SPECSPEC + (, 0, E0), wobei SPEC*SPEC* = (*, E*), SPECSPEC = (, E), *= 0, E*= E E0 (alles S-sortig). Dann ist SPEC*SPEC*1.) vollständig bezüglich SPECSPEC genau dann, wenn

t' (t' T* t (t T t' E* t ), und 2.) konsistent bezüglich SPECSPEC genau dann, wenn

t1 t2 ( t1 ,t2 T t1 E* t2 t1 E t2).

Page 18: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 18

T T*

g

hT ,E T*,E*

nat(

E

) nat(

E*

)

Die Homomorphismen g, h und die Inklusion werden jeweils auf den SPECSPEC-Redukten betrachtet.Wegen Initialität existieren alle diese Homomorphismen und sind eindeutig bestimmt.

Weil speziell auch g eindeutig ist, muß auch gelten:

() h([t]E) = [t]E*

für alle tT

Beweis:

Page 19: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 19

Beweis (Forts.):() h([t]E

) = [t]E* für alle tT

zu 1.) SPEC*SPEC* vollständig gdw. h surjektiv ist. Dies gilt gdw. zu jeder Kongruenzklasse [t']E*

eine Kongruenzklasse [t]E

existiert mit h([t]E) = [t']E*

.

Wegen () haben wir[t']E*

= h([t']E) = h([t]E

) = [t]E* gdw. t' E* t .

Also ist SPEC*SPEC* vollständig gdw. zu jedem t' T* ein t T existiert mit t' E* t .

zu 1.) SPEC*SPEC* vollständig bezüglich SPECSPEC gdw. t' (t' T* t (t T t' E* t )

Page 20: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 20

Beweis (Forts.):() h([t]E

) = [t]E* für alle tT

zu 2.) SPEC*SPEC* konsistent gdw. h injektiv ist. Dies gilt gdw. t1 ,t2 T :

h([t1]E) = h([t2]E

) [t1]E = [t2]E

Wegen () gilt dies gdw.[t1]E*

= [t2]E* [t1]E = [t2]E

also gdw. t1 E* t2 t1 E t2 ,

w.z.b.w.

zu 2.) SPEC*SPEC* konsistent bezüglich SPECSPEC gdw. t1 t2 ( t1 ,t2 T t1 E* t2 t1 E t2)

Page 21: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 21

Das Kriterium für die Vollständigkeit läßt sich noch verschärfen:Man muß nur solche Terme beachten, bei denen die neuen Operatoren nur als Hauptverknüpfungsfunktoren auftreten.

Definition „0-normaler Term“

Sei SPEC*SPEC* = SPECSPEC + (, 0, E0), SPEC*SPEC* = (*,E *),

SPECSPEC = (, E). Ein Term t T* heißt ein 0-Term genau dann, wenn t = t1t2 ... tn für ein 0. Ein 0-Term t1t2 ... tn heißt ein 0-normaler Term genau dann, wenn i (1 i n): ti T ist.

Page 22: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 22

Der Beweis läßt sich leicht induktiv über die Anzahl der Vor-kommen von neuen Operatoren aus 0 in einem Term t' T*

zeigen. Man ersetze im Induktionsschritt den jeweils innersten 0-normalen Term durch den gemäß obigem Kriterium

existierenden äquivalenten Term aus T . Der resultierende

Term ist nach dem Gleichungskalkül zum ursprünglichen t' äquivalent und enthält mindestens einen neuen Operator weniger.

Vollständigkeitskriterium:Mit denselben Bezeichnungen wie eben gilt: SPEC*SPEC* ist vollständig bezüglich SPECSPEC genau dann, wenn für alle 0-normalen Terme t0 T* ein t T existiert mit t0 E* t .

Page 23: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 1 Kapitel 12 Erweiterung von Gleichungsspezifikationen Ziel: modularer,

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 12 / 23

Die vorgestellten Kriterien erfordern die Prüfung der Äquivalenz von Termen:

t1 E t2 ?für verschiedene Gleichungssysteme, d.h. die Lösung des entsprechenden sogenannten Wortproblems.Folglich ist diese Frage i.a. unentscheidbar!Man benötigt i.a. weitere hinreichende Kriterien. Für eine Reihe konkreter Gleichungssysteme ist die Frage auch entscheidbar! Damit beschäftigt sich die Theorie der

Termersetzungssysteme.

• Für die Vollständigkeit gibt es eine Reihe von praktikablen, d.h. relativ einfachen, hinreichenden Kriterien. • Für die Entscheidung der Konsistenz gibt es vergleichbar einfache Kriterien leider bisher nicht.