Zusammenfassung Theo Inf PDF

Preview

Summary

DEA NEA REG RA CFL TM Deterministischer endlicher Automat Nichtdeterministischer endlicher Automat Sprache Ausruck Kontextfreie Sprache Turingmaschine LBA Linear Automat DSPACE(n) alle L(LBA) NTM Nichtdeterministische Turingmaschine univ. Turingmaschine (zur Simulation einer anderen) nicht TM hardwa...

Description

DEA NEA REG RA CFL TM

Deterministischer endlicher Automat Nichtdeterministischer endlicher Automat Reguläre Sprache Regulärer Ausruck Kontextfreie Sprache Turingmaschine LBA Linear beschränkter Automat DSPACE(n) = alle L(LBA) NTM Nichtdeterministische Turingmaschine Mu univ. Turingmaschine (zur Simulation einer anderen) nicht aufzählbare TM ATM Word-RAM hardwarenahe Registermaschine Q Quines (Programme, die ihren eigenen Code ausgeben) EQTM Equivalente TM coKomplement P Klasse der polynomiell (nk ) lösbaren Probleme NP Klasse der polynomiell verifizierbaren Probleme E Entscheidbare Sprachen A Aufzählbare Sprachen (=erkennbar) ฀ echte Teilmenge E ⊆ A

∪ ∩ \

Hält immer kann Zykeln bei Nichtakzeptanz

Vereinigung Schnitt Differenz

Nach Bearbeiten des Kurses 01657 können die Studierenden mit den wesentlichen Grundbegriffen Berechenbar Es gibt eine TM für dieses Problem Entscheidbar Es gibt eine TM, die immer hält Aufzählbar Es gibt eine TM, welche zykeln kann umgehen. Sie können mit formalen Sprachen arbeiten und diese wichtigen Klassen zuordnen Regulär an Es gibt einen DEA n n Kontextfrei a b Es gibt eine CF-Grammatik, bzw. einen Kellerautomaten Entscheidbar anbncn Es gibt eineTM, die nicht zykelt Sie kennen zudem Berechnungs- und Beschreibungsmodelle dieser Sprachklassen. Nach erfolgreicher Bearbeitung von Kurs 01658 können die Studierenden mit Komplexitätsmaßen (P, NP) umgehen, Probleme Komplexitätsklassen zuordnen und bei schwierigen Problemen einzuschätzen, ob sie NP-vollständig sind. Sie lernen, wie man zeigen kann, dass Probleme nicht berechenbar sind.

A Einführung und Formale Sprachen Lernziele Nach dem Studium dieser Lerneinheit sollten Sie in der Lage sein: erklären zu können, warum man Eingabeinstanzen von Problemen kodieren muss, und was dabei zu beachten ist, Ein Rechner versteht nur 0 und 1. Alle Angaben müssen in eine Form gebracht werden, die leztlich darauf basiert. Bsp.: Adjazenzlisten/-matrizen bei Graphen erklären zu können, was man unter Entscheidungsproblemen versteht, Problemstellungen, deren Antwort eindeutig “ja” oder “nein” lautet Operationen auf formale Sprachen anzuwenden, ∪ Vereinigung ∘ Alle Wörter einer Tabelle ais L1 und L2 k Wie ∘, jedoch skalierbar als Potenz ∩ Schnitt L n \ Differenz Komplement (E*\L) die wichtigsten mathematischen Grundbegriffe zu den Themen Mengen, Tupel, Relationen, Funktionen und Graphen sicher zu benutzen. Mengen Gruppe von Objekten, Objekte können Mengen sein Partition: Vollständige Teilmengen einer Menge Potenzmenge: Menge aller Symbole von einer Menge \ ∅ Tupel Kartes. Produkt: Tabelle aus zwei Listen (wie ∘) Relationen Komposition: a(b(x)) ≙ a ∘ b & Funktionen Graphen Reguläre Sprachen I: Endliche Automaten und Reguläre Ausdrücke Lernziele Nach dem Studium dieser Lerneinheit sollten Sie in der Lage sein: reguläre Sprachen zu erkennen, Für alle REG gibt es einen DEA die Modelle DEA, NEA und RA erklären zu können, DEA M = (Q, Σ  , δ, q0, F) Q alle Zustände Eingabealphabet Σ δ Übergangsfunktion q0 Startzustand F akzeptierte Zustände NEA: wie DEA, N = … + ε-Übergänge mehrere mögl. Zeichen pro Übergang ein möglicher Lauf muss nur existieren interierte Übergangsfunktion: q*(qi ,w) RA

beschreibt eine Sprache statt durch einen Automaten durch ein Wort einer Sprache: Σ ∪ { (, ), *, +, ·, ∅ , ε }

NEA Potenzautomat ⊆ DEA, DEA ⊆ NEA

für eine reguläre Sprache einen DEA, NEA oder RA zu konstruieren, (Übung) aus einem DEA, NEA, oder RA seine Sprache zu bestimmen, (Übung) die Potenzautomatenkonstruktion auszuführen, (Übung) Abschlusseigenschaften der regulären Sprachen herzuleiten, Vereinigung (Beweise durch Produktautomat (Zustandspaare) oder NEA (trivial)) Konkatenation Kleene-Stern Spiegelung Komplement den Satz von Kleene und die dahinterstehende Beweisideen wiederzugeben. - Alle Sprachen von RAs sind REG (Beweis durch vollst. Induktion der Ableitungsregeln) - Für alle REG existiert ein RA (Beweis durch den rekursiven Algorithmus der DEAs in RAs umwandelt) => {REG} = {L(RA)} Satz von Kleene Reguläre Sprachen II: Minimierung von DEAs und Grenzen der regulären Sprachen Lernziele Nach dem Studium dieser Lerneinheit sollten Sie in der Lage sein: zu einem DEA seinen kollabierten Automaten zu konstruieren, Zusammenfassen äquivalenter Zustände (gleiche Ein- & Ausgänge, so wie deren Ergebnis) (siehe Table-Filling-Algorithmus) die Myhill–Nerode Klassen von einfachen Sprachen bestimmen zu können, a) alle Varianten für ausreichend lange Wörter b) Alle unzureichend langen Wärter (können z.t. zu a) ergänzt werden, nicht trivial) erklären zu können, warum der Myhill–Nerode Automat ein Minimalautomat ist, MN-Relationen haben in sich keine Trennwörter, per Definition So entspricht die MN-Relation den Äquivalenzklassen. => MN-Automat = Minimalautomat den Satz von Myhill–Nerode mit Beweis wiederzugeben, “Eine Sprache L ist genau dann regulär, wenn ihre MN-Relation einen endlichen Index hat” (Index = Anzahl Äquivalenzklassen) Beweis: Anzahl Klassen M = |ML | => |ML| endich (Anzahl Zustände) ist endlich Es gibt einen DEA für L => ∃  L(DEA ML) => L ⊆  REG L ist regulär den Table-Filling Algorithmus auszuführen, q0

q1

q2

q3

...

q0 q1 q2 ... Phase 1: Unterscheidet sich die Art (verwerfend/akzeptierend) der Zustände? Phase 2: Folge den übrigen Zuständen mit je einem Eingabesymbol um ein anderes Zustandspaar zu erhalten. Markiere das Ursprungspaar, falls das Folgepaar in einem Fall markiert ist.

das Pumpinglemma inklusive seiner Beweisidee zu beschreiben, Ist L ⊆  REG => L ist pumpbar pumpbar: Das Wort ist immer zerlegbar in xyi>0  z, sodass xyi z ∈ L i Beweis:M besitzt eine Schleife (y ), die mehrfach durchlaufen werden kann. Sie kann nur für |xy| ≤ |w| erreicht werden. Existiert so ein DEA => L  ⊆ REG das Pumpinglemma anwenden zu können, um zu zeigen, dass Sprachen nicht regulär sind. (Übung), Ist eine SPrache nicht pumpbar, ist sie nicht REG Kontextfreie Sprachen I: Kellerautomaten und Grammatiken Lernziele Nach dem Studium dieser Lerneinheit sollten Sie in der Lage sein: das Prinzip von Kellerautomaten und kontextfreien Grammatiken erklären zu können, Kellerautomat K(Q, Σ, Γ, δ, q0, F) entspricht NEA + Stack-Speicher Γ Arbeitsalphabet  δ(Zust. q, Eingebez. a, Topsymbol x) = { (neuZust.  p, push/pop y ) } cf Grammatik G (V, Σ, P, S) V Variablen Σ Terminalsymbole (!= V) P Regeln S Startvariable einen Kellerautomaten / eine kontextfreie Grammatik für eine vorgegebene Sprache zu konstruieren, (Übung) die Sprache eines Kellerautomaten / einer kontextfreien Grammatik zu beschreiben, Sprache, die ein Keller bzw. eine CFL erkennt die Beweisideen wiederzugeben, warum Kellerautomaten und kontextfreie Grammatiken äquivalente Modelle sind, - K kann CFL ableiten: Linksableitung speichert Terminalsymbole zwischen und leitet Va. ab. => CFL ⊆  K - K wird vereinfacht: nur Push/Pop, Speicher leer am Ende (evtl. “leerpumpen”, wenn akzeptiert) R1 Worte hinterlassen Keller leer, wie vorgefunden R2 Worte hinterlassen Keller, wie vorgefunden, nicht leer R3 leeres Wort => K ⊆ CFL erklären zu können, warum rechtslineare Grammatiken genau die regulären Sprachen erkennen. rechtslinear: V1 = V2| E Rechtslineare Grammatiken ⊆ NEA => DEA = REG Beweis: NEA lässt sich nach Schema konstruieren Kontextfreie Sprachen II: Das Wortproblem und die Grenzen der kontextfreien Sprachen Lernziele Nach dem Studium dieser Lerneinheit sollten Sie in der Lage sein: erklären zu können, was eine Chomsky Normalform ist, CNF ⊆  CFL, Vereinfachung einer CFL, die nur Regeln folgender Form enthält: A -> XY A -> x S -> ε auch Zusammengefasst: S -> XY | x

ein Verfahren anzugeben, mit welchem man eine kontextfreie Grammatik in Chomsky Normalform umwandeln kann, 1. S durch S’ ersetzen, Regel S -> S’ hinzufügen 2. A -> ε eliminieren durch Aufzählen der Möglichkeiten X -> xAyA => X -> xAya | xAy | xyA | xy 3. A -> B eliminieren A -> B, B -> xy | xBxy => A -> xy | xBxy, B -> xy | xBxy 4. Zerlegung aller Regeln mit langer (>2) rechter Seite, einführen von “Vi -> ...” 5. Terminalsymbole in Vx ersetzen, ausser Vx->x den CYK Algorithmus erklären und ausführen zu können, sowie dessen Korrektheit und Laufzeit zu begründen, Lösung für “ist cbbac aus einer CFL (in CNF) L(K)” Beweis Korrekt: Wenn Engabe x=a1, ... , an und A∈Vi,j => es gibt eine Ableitung (Bew. durch Induktion) Laufzeit: (On³) durch drei verschachtelte Schleifen im Algorithmus

das kontextfreie Pumpinglemma wiederzugeben und dessen Beweisidee zu skizzieren, Ist eine Sprache cf, ist sie auch cf-pumpbar Beweis: Im Ableitungsbaum lassen sich Teilbäume wiederholen mit dem kontextfreien Pumpinglemma nachzuweisen, dass Sprachen nicht kontextfrei sind, an bn cn nicht cf (, Übung) erklären zu können, unter welchen elementaren Operationen die kontextfreien Sprachen abgeschlossen sind. Vereinigung + S’ -> S1 | S2 nicht! Konkatenation + S’ -> S1S2 Schnitt: Gegenbeispiel möglich Spiegelung Komplement: weil nicht Schnitt Entscheidbare Sprachen und Turingmaschinen Lernziele Nach dem Studium dieser Lerneinheit sollten Sie in der Lage sein: das Modell der Turingmaschine erklären zu können, TuringmaschineM = (Q, Σ  , Γ, δ, q0, qA, qV) qA akzeptierender Zustand qV verwerfender Zustand Speicher ist Band (rechts u. links), Engabe ist auch Band für einfache Sprachen Turingmaschinen konkret als Zustandsdiagramm anzugeben, (Übung) für komplexere Sprachen Turingmaschinen in Modulschreibweise anzugeben, Textbeschreibung (Prosa), Befehle nummeriert (+ Übung)

die Variationen nichtdeterministische, Mehrband-, und Halbband-Turingmaschine zu erklären, und deren Äquivalenz zur 1-Band Turingmaschine zu beweisen, Mehrband-TM mehrere Arbeitsbänder ⊆  TM Jede Speicherzelle einer normalen TM kann als (Spur-)Array betrachtet werden, der diese Zelle i aller Bänder aufnehmen kann. Ansteuerung via Unterprogramm. ⊇ TM (trivial) Halbband-TM normale TM mit einseitiger linker Grenze ⊆ TM (trivial) ⊇ TM 2-spaltige Speicherzellen, positive und negative Indexe das Modell LBA zu beschreiben, linear beschränkter Automat LBA ⊆ TM, LBA ⊉ TM

nur der Speicher der Eingabe * k Spuren

definieren zu können, was berechenbare und total berechenbare Funktionen sind, berechenbar es gibt eine TM dafür total berechenbar jede EIngabe hat eine Ausgabe (zykelt nie) Funktionen nicht ausschließlich ja/nein auf Ausgabeband die Church–Turing These und deren Motivation wiederzugeben. Algorithmen = TM-Instanzen Andere Berechnungsmodelle sind äquivalent zu TMs Einfache Anahmen Motivation: Formale Beschreibung elementarer Operationen Aufzählbare Sprachen Lernziele Nach dem Studium dieser Lerneinheit sollten Sie in der Lage sein: erklären zu können, was aufzählbare und co-aufzählbare Sprachen sind, aufzählbar Es gibt eine TM, welche alle Wörter von L ausgibt co-aufzählbar alle Sprachen, deren Komplement aufzählbar ist die Äquivalenz zwischen erkennbaren und aufzählbaren Sprachen beweisen zu können, A ⊆  erkennbar Einen Aufzähler aufzählen lassen, bis das ges. Wort erscheint A ⊇  erkennbar Σ* schrittweise durch eine TM prüfen (da sonst zykel-Problem) i ≙ Eingabegrenze j ≤ i ≙ Schrittgrenze die Funktionsweise und das Prinzip der universellen Turingmaschine zu erläutern, Mu() = M(w) 1. Syntaxtest, 2. Simulation von M Programmband Codierung von M Simulationsband Arbeitsband Zustandsband Zähler nachzuweisen, dass Sprachen erkennbar oder aufzählbar sind, gibt es eine TM für eine Sprache, ist diese erkennbar = aufzählbar einfache Abschlusseigenschaften von erkennbaren und aufzählbaren Sprachen zu beweisen. A, E Vereinigung, Schnitt

A, E 

L1 ∘L2 Konkatenation M∘ Alle mögl. Wortteilungen von M∩ testen

B Unentscheidbare Sprachen Existenz von nichtaufzählbaren Sprachen Definition 1.1 Zwei Mengen X und Y heißen gleichmächtig, falls eine Bijektion zwischen X und Y existiert. Definition 1.2 Eine Menge X heißt abzählbar, falls (i) X endlich ist oder (ii) X und die Menge der natürlichen Zahlen gleichmächtig sind. Beweis für Gleichmächtigkeit: Cantornumerierung Widerlegen der Gleichmächtigkeit: Diagonalisierungsbeweis in Widerspruchsbeweis

 Die Menge Σ* ist abzählbar. (Nach Cantor) Die Menge {L ⊆ Σ*} aller Sprachen über Σ ist überabzählbar. (Nach Diagonal.) => Es gibt ene Sprache, die nicht aufzählbar (erkennbar) ist.

Konstruktion von nichtaufzählbaren Sprachen Satz: Die Sprache ATM := { | M ist Turingmaschine die w akzeptiert} ist nicht entscheidbar. Beweis: Widerspruchsbeweis. D() =

akzeptiert wenn M() verwirft verwirft wenn M() akzeptiert

Das heißt aber insbesondere, dass D() =

akzeptiert wenn D() verwirft verwirft wenn D() akzeptiert .

Dies ist offensichtlich ein Widerspruch. Somit kann D nicht existieren und deshalb kann H nicht existieren. Unsere Annahme war daher falsch und demnach gibt es keinen Entscheider für ATM. => Satz: Das Komplement der Sprache ATM (TouringMaschinen!) ist nicht aufzählbar. analog dazu: Satz: Die Sprache HALT ist nicht entscheidbar und nicht co-aufzählbar. Die Aussage aus den beiden letzten Sätzen kann man so interpretieren, dass es keinen Algorithmus gibt, mit Hilfe dessen wir andere Algorithmen verifizieren können. Zwar können wir positive Ergebnisse verifizieren, da ATM ∈ E, wir werden aber nicht in allen Fällen die negativen Ergebnisse feststellen können, da ATM < co-E. Es ist natürlich möglich, für ausgewählte Algorithmen einen Nachweis zu erbringen, dass sie korrekt arbeiten. Was wir gezeigt haben ist, dass es kein allgemeines Verfahren für die Verifikation geben kann.

Entscheidbarkeit des universellen Wortproblems ACFG = { | G ist CFG und w ∈ L(G)} ∈ E, und ADEA = { | M ist DEA und w ∈ L(M)} ∈ E Definition 1.3 Die Menge der Sprachen, die durch einen linear beschränkten Automaten (LBA) erkannt werden nennen wir DSPACE(n). REG ฀ CFL ฀ DSPACE(n) ฀ A Satz: ALBA ∈ E

Einen Entscheider für ALBA kann man nun wie folgt konstruieren. Sei die Eingabe. Wir konstruieren zuerst einen zu M äquivalenten LBA M0, der auf allen Eingaben hält. Eine solche Konstruktion können wir nach Lemma 1.6 ausführen. Nun nutzen wir die modifizierte universelle Turingmaschine und simulieren M0 (w). Da M0 auf allen Eingaben hält, wird auch die Simulation von M0 (mit dem richtigen Ergebnis) halten. 

Lernziele die Begriffe abzählbar und überabzählbar erklären zu können und mehrere Beispiele hierfür zu kennen, Die Menge der ganzen Zahlen Z ist abzählbar. Die Menge N² = N×N ist abzählbar. Die Menge der rationalen Zahlen Q ist abzählbar. Die Menge der reellen Zahlen R ist überabzählbar.  Die Menge Σ* ist abzählbar. (Nach Cantor) Die Menge {L ⊆ Σ*} aller Sprachen über Σ ist überabzählbar. zu beweisen, dass die Menge der aufzählbaren Sprachen abzählbar, die Menge aller Sprachen aber überabzählbar ist, zu zeigen, dass die Sprache ATM nicht entscheidbar ist, und dass ihr Komplement nicht aufzählbar ist, das Prinzip der Diagonalisierung wiedergeben zu können, erläutern zu können, warum das universelle Wortproblem für LBAs entscheidbar ist, Ein LBA besteht aus Arbeitsalphabet Γ (max. |Γ|n Mögl.), n möglichen Kopfpositionen, Zustandsmenge Q (max |Q|) => n|Q||Γ|n Konfigurationen = O(cn ). Ein LBA zykelt nur dann, wenn eine Konfiguration mehrfach aufgetreten ist, wenn also mehr als cn Schritte. Wird dies geprüft, kann es einen LBA geben, der auf allen EIngaben hält. Eine Mu , die den LBA M simuliert, ist nun ein Entscheider für M die negativen Konsequenzen aus der Unentscheidbarkeit von ATM und HALT zu diskutieren. wichtige Probleme (wie das universelle Wortproblem) lassen sich für die Turingmaschinen nicht mehr entscheiden.

Reduktionen Das Konzept der Reduktion Definition 2.1 — Reduktion.  Eine Reduktion der Sprache A ⊆ Σ1* auf die Sprache B ⊆ Σ2* ist eine berechenbare Funktion f : Σ1* → Σ2  , für die gilt ∀w ∈ Σ1*: w ∈ A ⇐⇒ f (w) ∈ B Existiert eine Reduktion von A auf B, nennen wir A auf B reduzierbar und schreiben kurz A ≤m B Reduktionen müssen nicht surjektiv oder injektiv sein, jedoch müssen alle w ∈ A sowie auch alle w !∈ A abgeildet werden. Es ist im Allgemeinen nicht möglich, eine Menge A auf ∅ oder Σ* zu reduzieren. Der Grund dafür ist, dass ein mögliches Bild f (x) für die Elemente x ∈ A bei A ≤m ∅ fehlt. Analog dazu fehlt bei A ≤m Σ* ein potentielles Bild f (x) für x < A. Einzig die Reduktionen ∅ ≤m Σ* und Σ* ≤m ∅ existieren in diesem Fall. Satz 2.1: Seien A und B Sprachen mit A ≤m B. Dann gilt (a) wenn B ∈ E, dann auch A ∈ E, //durch Reduktion (b) wenn B ∈ A, dann auch A ∈ A, //analog zu a) (c) wenn B ∈ co-A, dann auch A ∈ co-A. //analog zu b) und Komplement Satz 2.2: Die folgende Sprache ist nicht entscheidbar. ETM := { | M ist Turingmaschine mit L(M) = ∅}//durch Reduktion auf HALT //und Komplement Satz 2.3: Die folgenden Sprachen sind nicht entscheidbar: REGTM := { | M ist Turingmaschine mit L(M) ∈ REG} FTM := { | M ist Turingmaschine mit |L(M)| ≤ ∞} Die in der Diskussion unmittelbar vor dem Satz vorgestellte Reduktion bezeugt sowohl HALT ≤m REGTM als auch HALT ≤m FTM  . Damit sind beide Sprachen nach Korollar 2.1 (Komplement zu Satz 2.1) nicht entscheidbar. In eigenen Worten: lässt sich nachweisen, dass jedes Problem, welches durch eine Maschine durchführbar ist, auch durch eine Andere durchführen, so ist diese Andere ‘mächtiger’ und die Maschine wird auf diese Andere allgemeinere reduziert.

Der Satz von Rice “Eigenschaft” = Teilmenge U von A (U ⊆ A) triviale Eigenschaft: U = A oder U = ∅. Satz 2.4 — Satz von Rice. Für jede nichttriviale Eigenschaft U ist die Sprache LU := { | L(M) ∈ U} nicht entscheidbar.

Beweis: für Fall 1: ∅ ∈ U Es wird eine HALTendeTM für LU gebaut und das Problem darauf reduziert. Das HALT-Problem ist nicht entscheidbar. für Fall 2: ∅ !∈ U Das Komplement der Sprache LU führt auf Fall 1 und ist damit auch nicht entscheidbar

Das Äquivalenzproblem für Turingmaschinen Satz 2.5: Die Sprache EQTM := { | M1, M2 sind Turingmaschinen mit L(M1) = L(M2)} ist weder aufzählbar noch co-aufzählbar. Beweis:EQTM nicht aufzählbar ATM ≤m EQTM => EQTM nicht aufzählbar !ATM ≤m !EQTM => EQTM nicht co-aufzählbar EQTM nicht co-aufzählbar (gesuchte Reduktionen sind relativ einfach) Lernziele Nach dem Studium dieser Lerneinheit sollten Sie in der Lage sein: das Prinzip der Reduktion zu erklären, Reduktionen anzuwenden, um nachzuweisen, dass Probleme unentscheidbar, nichtaufzählbar oder nicht co-aufzählbar sind, den Satz von Rice wiederzugeben, anzuwenden und dessen Beweisidee zu erklären, zu beweisen, dass EQTM weder aufzählbar noch co-aufzählbar ist.

Weitere unentscheidbare Probleme Reduktion über Berechnungspfade Berechnungspfade stellen auflistungen der einzelnen Schritte vom TMs dar. Es gelten folgende Regeln: 1.) Die erste Konfiguration entspricht der Startkonfiguration von M(w). 2.) Jede andere Konfiguration ist die Nachfolgekonfiguration der zuvor notierten Konfiguration. 3.) Die letzte Konfiguration ist akzeptierend oder verwerfend. Lemma 3.1 Sei M eine feste Turingmaschine und w ein festes Eingabewort. Die Sprache { | β ist akzeptierender Berechnungspfad von M(w)} kann durch einen LBA erkannt werden. Beweis: 1. Prüfen, ob Berechnungspfad-Wort gültig ist (mit # getrennte Konfigurationen [wlpwr]) 2. Erster Teil = Startkonfiguration? 3. prüfen ob jede Konfig., die Nachfolgekonfig. des Vorgängers ist maximal drei Zeichen unterschiedlich (Zeichen für den Zustand +-1 und jeweils das Zeichen davor und dahinter). => Satz 3.1 Die Sprache ELBA := { | M ist LBA mit L(M) = ∅} ist nicht entscheidbar. Beweis: ATM ≤m co-(ELBA) => Satz 3.1 durch Reduktion auf Komplement Das Postsche Korrespondenzproblem (PKP) (Dominotypen) Definition 3.1 Sei Σ ein Alphabet mit mindestens zwei Zeichen. Wir nennen ein Element aus Σ* x Σ* einen Dominotypen . Ein Dominoset  ist eine endliche Folge ((u1 , v1 ), (u2 , v2 ), . . ., (uk , vk )) von Dominotypen. Wir sagen, ein Dominose...