halb-Thue System

In der theoretischen Informatik und mathematischen Logik ist ein String-Rewriting-System ( SRS ), historisch auch als Semi-Thue-System bezeichnet, ein Rewriting- System für Strings aus einem (üblicherweise endlichen ) Alphabet . Gegeben sei eine binäre Relation zwischen festen Strings über dem Alphabet, die sogenannten Rewriting-Regeln , bezeichnet mit . Ein SRS erweitert die Rewriting-Relation auf alle Strings, in denen die linke und rechte Seite der Regeln als Teilstrings vorkommen , d. h . , wobei , , und Strings sind. ${\displaystyle R}$${\displaystyle s\rightarrow t}$${\displaystyle usv\rightarrow utv}$${\displaystyle s}$${\displaystyle t}$${\displaystyle u}$${\displaystyle v}$

Der Begriff eines semi-Thue-Systems deckt sich im Wesentlichen mit der Darstellung eines Monoids . Somit bilden sie einen natürlichen Rahmen zur Lösung des Wortproblems für Monoide und Gruppen.

Ein String-Rewriting-System (SRS) lässt sich direkt als abstraktes Umschreibungssystem definieren . Es kann auch als eingeschränktes Term -Rewriting- System betrachtet werden, in dem alle Funktionssymbole höchstens eine Stelligkeit von 1 haben. Formalistisch betrachtet sind String-Rewriting-Systeme Turing-vollständig . ^{[ 1 ]} Der Name „Semi-Thue“ geht auf den norwegischen Mathematiker Axel Thue zurück , der 1914 in einer Arbeit die systematische Behandlung von String-Rewriting-Systemen einführte. ^{[ 2 ]} Thue führte diesen Begriff in der Hoffnung ein, das Wortproblem für endlich präsentierte Halbgruppen zu lösen . Erst 1947 wurde gezeigt, dass das Problem unentscheidbar ist – dieses Ergebnis wurde unabhängig voneinander von Emil Post und A. A. Markov Jr. erzielt . ^{[ 3 ] [ 4 ]}

Ein String-Ersetzungssystem oder Semi-Thue-System ist ein Tupel , bei dem ${\displaystyle (\Sigma ,R)}$

• ${\displaystyle \Sigma }$ist ein Alphabet, das üblicherweise als endlich angenommen wird. ^{[ 5 ]} Die Elemente der Menge (* ist hier der Kleene-Stern ) sind endliche (möglicherweise leere) Zeichenketten auf , die in formalen Sprachen manchmal Wörter genannt werden ; wir nennen sie hier einfach Zeichenketten.${\displaystyle \Sigma ^{*}}$${\displaystyle \Sigma }$
• ${\displaystyle R}$ist eine binäre Relation auf Zeichenketten aus , d.h. Jedes Element wird als (Umschreibungs-)Regel bezeichnet und üblicherweise geschrieben .${\displaystyle \Sigma }$${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}.}$${\displaystyle (u,v)\in R}$${\displaystyle u\rightarrow v}$

Wenn die Relation symmetrisch ist , dann wird das System als Thue-System bezeichnet . ${\displaystyle R}$

Die Umschreibungsregeln in können auf natürliche Weise auf andere Zeichenketten in erweitert werden, indem man die Umschreibung von Teilzeichenketten gemäß zulässt . Formaler ausgedrückt: Die durch auf induzierte Ein-Schritt-Umschreibungsrelation für beliebige Zeichenketten lautet : ${\displaystyle R}$${\displaystyle \Sigma ^{*}}$${\displaystyle R}$${\displaystyle {\xrightarrow[{R}]{}}}$${\displaystyle R}$${\displaystyle \Sigma ^{*}}$${\displaystyle s,t\in \Sigma ^{*}}$

${\displaystyle s{\xrightarrow[{R}]{}}t}$genau dann, wenn es solche gibt, dass , , und .${\displaystyle x,y,u,v\in \Sigma ^{*}}$${\displaystyle s=xuy}$${\displaystyle t=xvy}$${\displaystyle u\rightarrow v}$

Da es sich um eine Relation auf handelt , erfüllt das Paar die Definition eines abstrakten Umschreibungssystems . Offensichtlich ist eine Teilmenge von . Manche Autoren verwenden eine andere Notation für den Pfeil in (z. B. ), um ihn von sich selbst ( ) zu unterscheiden, da sie später den Index weglassen und dennoch Verwechslungen zwischen und der durch induzierten einstufigen Umschreibung vermeiden möchten . ${\displaystyle {\xrightarrow[{R}]{}}}$${\displaystyle \Sigma ^{*}}$${\displaystyle (\Sigma ^{*},{\xrightarrow[{R}]{}})}$${\displaystyle R}$${\displaystyle {\xrightarrow[{R}]{}}}$${\displaystyle {\xrightarrow[{R}]{}}}$${\displaystyle {\underset {R}{\Rightarrow }}}$${\displaystyle R}$${\displaystyle \rightarrow }$${\displaystyle R}$${\displaystyle R}$

Offensichtlich können wir in einem semi-Thue-System eine (endliche oder unendliche) Folge von Zeichenketten bilden, indem wir mit einer Anfangszeichenkette beginnen und diese wiederholt umschreiben, indem wir jeweils eine Teilzeichenkette ersetzen: ${\displaystyle s_{0}\in \Sigma ^{*}}$

${\displaystyle s_{0}\ {\xrightarrow[{R}]{}}\ s_{1}\ {\xrightarrow[{R}]{}}\ s_{2}\ {\xrightarrow[{R}]{}}\ \ldots }$

Eine solche Umformung mit null oder mehr Schritten wird durch den reflexiven transitiven Abschluss von erfasst , der mit bezeichnet wird (siehe Abstraktes Umformungssystem#Grundbegriffe ). Dies wird als die durch induzierte Umformungsrelation oder Reduktionsrelation auf bezeichnet . ${\displaystyle {\xrightarrow[{R}]{}}}$${\displaystyle {\xrightarrow[{R}]{*}}}$${\displaystyle \Sigma ^{*}}$${\displaystyle R}$

Im Allgemeinen bildet die Menge der Zeichenketten eines Alphabets zusammen mit der binären Operation der Zeichenkettenverkettung (bezeichnet als und multiplikativ geschrieben, indem das Symbol weggelassen wird) ein freies Monoid . In einem SRS ist die Reduktionsrelation mit der Monoidoperation kompatibel, d. h., dass für alle Zeichenketten impliziert . Da per Definition eine Präordnung ist , bildet eine monoidale Präordnung . ${\displaystyle \Sigma ^{*}}$${\displaystyle \cdot }$${\displaystyle {\xrightarrow[{R}]{*}}}$${\displaystyle x{\xrightarrow[{R}]{*}}y}$${\displaystyle uxv{\xrightarrow[{R}]{*}}uyv}$${\displaystyle x,y,u,v\in \Sigma ^{*}}$${\displaystyle {\xrightarrow[{R}]{*}}}$${\displaystyle \left(\Sigma ^{*},\cdot ,{\xrightarrow[{R}]{*}}\right)}$

Analog dazu ist der reflexive transitive symmetrische Abschluss von R, bezeichnet mit (siehe Abstraktes Umschreibungssystem#Grundbegriffe ), eine Kongruenz , d. h. eine Äquivalenzrelation (per Definition) und kompatibel mit der Verkettung von Zeichenketten. Diese Relation wird als Thue-Kongruenz bezeichnet , die von R erzeugt wird . In einem Thue-System, d. h. wenn R symmetrisch ist, stimmt die Umschreibungsrelation mit der Thue-Kongruenz überein . ${\displaystyle {\xrightarrow[{R}]{}}}$${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$${\displaystyle {\xrightarrow[{R}]{*}}}$${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$

Da es sich um eine Kongruenz handelt, können wir das Faktormonoid des freien Monoids in üblicher Weise durch die Thue-Kongruenz definieren . Wenn ein Monoid isomorph zu ist , dann wird das Semi-Thue-System als Monoidpräsentation von bezeichnet . ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$${\displaystyle {\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}}$${\displaystyle \Sigma ^{*}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}_{R}}$${\displaystyle (\Sigma ,R)}$${\displaystyle {\mathcal {M}}}$

Wir erhalten unmittelbar einige sehr nützliche Verbindungen zu anderen Gebieten der Algebra. Beispielsweise ist das Alphabet { a , b } mit den Regeln { ab → ε, ba → ε}, wobei ε die leere Zeichenkette ist , eine Präsentation der freien Gruppe auf einem Erzeuger. Lauten die Regeln stattdessen einfach { ab → ε}, so erhalten wir eine Präsentation des bizyklischen Monoids .

Die Bedeutung von Semi-Thue-Systemen als Darstellung von Monoiden wird durch Folgendes unterstrichen:

Satz : Jedes Monoid besitzt eine Präsentation der Form , daher kann es stets durch ein semi-Thue-System präsentiert werden, möglicherweise über einem unendlichen Alphabet. ^{[ 6 ]}${\displaystyle (\Sigma ,R)}$

In diesem Kontext wird die Menge als Erzeugermenge von bezeichnet , und wird als Menge der definierenden Relationen bezeichnet . Monoide lassen sich unmittelbar anhand ihrer Darstellung klassifizieren. wird als bezeichnet ${\displaystyle \Sigma }$${\displaystyle {\mathcal {M}}}$${\displaystyle R}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$

• endlich erzeugt, wenn endlich ist.${\displaystyle \Sigma }$
• endlich präsentiert, wenn sowohl als auch endlich sind.${\displaystyle \Sigma }$${\displaystyle R}$

Post bewies, dass das Wortproblem (für Halbgruppen) im Allgemeinen unentscheidbar ist, indem er im Wesentlichen das Halteproblem ^{[ 7 ]} für Turingmaschinen auf eine Instanz des Wortproblems reduzierte (siehe Post Korrespondenzproblem ).

Konkret entwickelte Post eine Kodierung als endliche Zeichenkette des Zustands einer Turingmaschine plus Band, sodass die Aktionen dieser Maschine durch ein auf diese Kodierung wirkendes Zeichenketten-Umschreibsystem ausgeführt werden können. Das Alphabet der Kodierung besteht aus einem Satz von Buchstaben für Symbole auf dem Band (wobei für leer steht), einem weiteren Satz von Buchstaben für Zustände der Turingmaschine und schließlich drei Buchstaben mit speziellen Rollen in der Kodierung. und sind intuitiv zusätzliche interne Zustände der Turingmaschine, in die sie beim Anhalten wechselt, während das Ende des nicht leeren Teils des Bandes markiert; eine Maschine, die ein erreicht, sollte sich so verhalten, als ob sich dort eine leere Zelle befände und das Ende in der nächsten Zelle wäre. Die Zeichenketten, die gültige Kodierungen von Turingmaschinenzuständen darstellen, beginnen mit einem , gefolgt von null oder mehr Symbolbuchstaben, gefolgt von genau einem internen Zustandsbuchstaben (der den Zustand der Maschine kodiert), gefolgt von einem oder mehreren Symbolbuchstaben und schließlich einem abschließenden . Die Symbolbuchstaben stammen direkt aus dem Inhalt des Bandes, und der interne Zustandsbuchstabe markiert die Position des Lesekopfes. Das Symbol nach dem internen Zustandsbuchstaben ist dasjenige der Zelle, die sich aktuell unter dem Kopf der Turingmaschine befindet. ${\displaystyle S_{0},S_{1},\dotsc ,S_{m}}$${\displaystyle S_{0}}$${\displaystyle q_{1},\dotsc ,q_{r}}$${\displaystyle q_{r+1},q_{r+2},h}$${\displaystyle q_{r+1}}$${\displaystyle q_{r+2}}$${\displaystyle h}$${\displaystyle h}$${\displaystyle h}$${\displaystyle h}$${\displaystyle q_{i}}$${\displaystyle h}$

Ein Übergang, bei dem die Maschine, nachdem sie sich im Zustand befindet und das Symbol sieht , das Symbol zurückschreibt , sich nach rechts bewegt und in den Zustand übergeht, wird durch das Umschreiben implementiert. ${\displaystyle q_{i}}$${\displaystyle S_{k}}$${\displaystyle S_{l}}$${\displaystyle q_{j}}$

${\displaystyle q_{i}S_{k}\to S_{l}q_{j}}$

wohingegen dieser Übergang, der sich stattdessen nach links bewegt, durch die Umschreibung implementiert wird.

${\displaystyle S_{p}q_{i}S_{k}\to q_{j}S_{p}S_{l}}$

mit einer Instanz für jedes Symbol in dieser Zelle links davon. Falls wir das Ende des besuchten Abschnitts des Bandes erreichen, verwenden wir stattdessen ${\displaystyle S_{p}}$

${\displaystyle hq_{i}S_{k}\to hq_{j}S_{0}S_{l}}$,

Die Zeichenkette wird um einen Buchstaben verlängert. Da alle Umschreibungen einen internen Zustandsbuchstaben beinhalten , enthalten die gültigen Kodierungen nur einen solchen Buchstaben, und jede Umschreibung erzeugt genau einen solchen Buchstaben. Der Umschreibungsprozess entspricht exakt dem Ablauf der kodierten Turingmaschine. Dies beweist, dass Systeme zur Umschreibung von Zeichenketten Turing-vollständig sind. ${\displaystyle q_{i}}$

Der Grund für die zwei angehaltenen Symbole ist , dass alle anhaltenden Turingmaschinen im selben Gesamtzustand terminieren sollen , nicht nur in einem bestimmten internen Zustand. Dies erfordert das Löschen des Bandes nach dem Anhalten. Daher wird das Symbol links davon gelöscht, bis das Symbol erreicht ist , das dann in übergeht und das Symbol rechts davon löscht. (In dieser Phase simuliert das String-Umschreibsystem keine Turingmaschine mehr, da diese keine Zellen vom Band entfernen kann.) Nachdem alle Symbole gelöscht wurden, ist die Terminalzeichenkette erreicht . ${\displaystyle q_{r+1}}$${\displaystyle q_{r+2}}$${\displaystyle q_{r+1}}$${\displaystyle h}$${\displaystyle q_{r+2}}$${\displaystyle hq_{r+2}h}$

Ein Entscheidungsverfahren für das Wortproblem würde dann auch ein Verfahren liefern, um zu entscheiden, ob die gegebene Turingmaschine terminiert, wenn sie in einem bestimmten Gesamtzustand gestartet wird , indem geprüft wird, ob und bezüglich dieses String-Umschreibungssystems zur selben Kongruenzklasse gehören. Technisch gesehen haben wir Folgendes: ${\displaystyle t}$${\displaystyle t}$${\displaystyle hq_{r+2}h}$

Lemma. Sei eine deterministische Turingmaschine und das String-Umschreibungssystem, das implementiert , wie oben beschrieben. Dann hält genau dann an, wenn vom Gesamtzustand aus gestartet wird, der als kodiert ist (d. h. genau dann, wenn und Thue-kongruent für sind ). ${\displaystyle M}$${\displaystyle R}$${\displaystyle M}$${\displaystyle M}$${\displaystyle t}$${\displaystyle t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h}$${\displaystyle t}$${\displaystyle hq_{r+2}h}$${\displaystyle R}$

Dass die Turingmaschine beim Start von Punkt 0 anhält, folgt unmittelbar aus der Konstruktion von (einfaches Ausführen bis zum Anhalten liefert einen Beweis für ), erlaubt ihr aber auch , Schritte rückwärts auszuführen. Hierbei ist die Deterministik von 0 relevant, da dann alle Vorwärtsschritte eindeutig sind. Bei einem Pfad von Punkt 0 zu Punkt 0 muss auf den letzten Rückwärtsschritt dessen Gegenstück als Vorwärtsschritt folgen, sodass sich diese beiden aufheben. Per Induktion lassen sich alle Rückwärtsschritte aus einem solchen Pfad eliminieren. Hält die Turingmaschine also beim Start von Punkt 0 nicht an , d . h., wenn wir nicht haben , dann haben wir auch nicht . Die Entscheidung für 0 liefert uns daher die Antwort auf das Halteproblem für . ${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$${\displaystyle M}$${\displaystyle t}$${\displaystyle R}$${\displaystyle M}$${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$${\displaystyle M}$${\displaystyle M}$${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$${\displaystyle t}$${\displaystyle hq_{r+2}h}$${\displaystyle M}$${\displaystyle t}$${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$${\displaystyle t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h}$${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$${\displaystyle M}$

Eine scheinbare Einschränkung dieses Arguments besteht darin, dass man zur Konstruktion einer Halbgruppe mit unentscheidbarem Wortproblem zunächst ein konkretes Beispiel einer Turingmaschine benötigt, deren Halteproblem unentscheidbar ist. Da jedoch die verschiedenen Turingmaschinen, die im Beweis der Unentscheidbarkeit des allgemeinen Halteproblems eine Rolle spielen, alle eine hypothetische Turingmaschine als Komponente enthalten, die das Halteproblem löst, kann keine dieser Maschinen tatsächlich existieren. Der Beweis zeigt lediglich, dass es eine Turingmaschine gibt, deren Entscheidungsproblem unentscheidbar ist. Die Existenz einer Turingmaschine mit unentscheidbarem Halteproblem bedeutet jedoch, dass das Halteproblem einer universellen Turingmaschine unentscheidbar ist (da diese jede Turingmaschine simulieren kann), und es wurden bereits konkrete Beispiele universeller Turingmaschinen konstruiert. ${\displaystyle \Sigma ^{*}{\big /}{\overset {*}{\underset {R}{\leftrightarrow }}}}$${\displaystyle M}$

Ein Semi-Thue-System ist auch ein Termersetzungssystem – eines, bei dem monadische Wörter (Funktionen) in der gleichen Variablen enden wie die Terme auf der linken und rechten Seite, ^{[ 8 ]} z.B. ist eine Termregel äquivalent zur Zeichenkettenregel . ${\displaystyle f_{2}(f_{1}(x))\rightarrow g(x)}$${\displaystyle f_{1}f_{2}\rightarrow g}$

A semi-Thue system is also a special type of Post canonical system, but every Post canonical system can also be reduced to an SRS. Both formalisms are Turing complete, and thus equivalent to Noam Chomsky's unrestricted grammars, which are sometimes called semi-Thue grammars.^[9] A formal grammar only differs from a semi-Thue system by the separation of the alphabet into terminals and non-terminals, and the fixation of a starting symbol amongst non-terminals. A minority of authors actually define a semi-Thue system as a triple ${\displaystyle (\Sigma ,A,R)}$, where ${\displaystyle A\subseteq \Sigma ^{*}}$ is called the set of axioms. Under this "generative" definition of semi-Thue system, an unrestricted grammar is just a semi-Thue system with a single axiom in which one partitions the alphabet into terminals and non-terminals, and makes the axiom a nonterminal.^[10] The simple artifice of partitioning the alphabet into terminals and non-terminals is a powerful one; it allows the definition of the Chomsky hierarchy based on what combination of terminals and non-terminals the rules contain. This was a crucial development in the theory of formal languages.

In quantum computing, the notion of a quantum Thue system can be developed.^[11] Since quantum computation is intrinsically reversible, the rewriting rules over the alphabet ${\displaystyle \Sigma }$ are required to be bidirectional (i.e. the underlying system is a Thue system, not a semi-Thue system). On a subset of alphabet characters ${\displaystyle Q\subseteq \Sigma }$ one can attach a Hilbert space ${\displaystyle \mathbb {C} ^{d}}$, and a rewriting rule taking a substring to another one can carry out a unitary operation on the tensor product of the Hilbert space attached to the strings; this implies that they preserve the number of characters from the set ${\displaystyle Q}$. Similar to the classical case one can show that a quantum Thue system is a universal computational model for quantum computation, in the sense that the executed quantum operations correspond to uniform circuit classes (such as those in BQP when e.g. guaranteeing termination of the string rewriting rules within polynomially many steps in the input size), or equivalently a Quantum Turing machine.

Semi-Thue-Systeme wurden im Rahmen eines Programms zur Erweiterung der Logik um zusätzliche Konstrukte entwickelt , um Systeme wie die Aussagenlogik zu schaffen, die es ermöglichen, allgemeine mathematische Theoreme in einer formalen Sprache auszudrücken und anschließend automatisch zu beweisen und zu verifizieren. Die Hoffnung bestand darin, den Beweisvorgang auf eine Menge definierter Manipulationen an einer Menge von Zeichenketten zu reduzieren. Später erkannte man, dass Semi-Thue-Systeme isomorph zu uneingeschränkten Grammatiken sind , welche wiederum bekanntermaßen isomorph zu Turingmaschinen sind . Diese Forschungsmethode war erfolgreich, und heute können Computer zur Verifizierung von Beweisen mathematischer und logischer Theoreme eingesetzt werden.

Auf Anregung von Alonzo Church bewies Emil Post in einer 1947 veröffentlichten Arbeit erstmals die Unlösbarkeit eines bestimmten Problems von Thue, was Martin Davis als „…den ersten Unlösbarkeitsbeweis für ein Problem der klassischen Mathematik – in diesem Fall das Wortproblem für Halbgruppen“ bezeichnet. ^{[ 12 ]}

Davis behauptet außerdem, dass der Beweis unabhängig von AA Markov erbracht wurde . ^{[ 13 ]}

• L-System
• Markov-Algorithmus – eine Variante von String-Umschreibungssystemen
• MU-Rätsel

• Ronald V. Book und Friedrich Otto, String-rewriting Systems , Springer, 1993, ISBN 0-387-97965-4Die
• Matthias Jantzen, Confluent string rewriting , Birkhäuser, 1988, ISBN 0-387-13715-7Die

• Martin Davis , Ron Sigal, Elaine J. Weyuker, Berechenbarkeit, Komplexität und Sprachen: Grundlagen der theoretischen Informatik , 2. Aufl., Academic Press, 1994, ISBN 0-12-206382-1, Kapitel 7
• Elaine Rich , Automaten, Berechenbarkeit und Komplexität: Theorie und Anwendungen , Prentice Hall, 2007, ISBN 0-13-228806-0, Kapitel 23.5.

• Samson Abramsky, Dov M. Gabbay, Thomas SE Maibaum (Hrsg.), Handbook of Logic in Computer Science: Semantic modelling , Oxford University Press, 1995, ISBN 0-19-853780-8Die
• Grzegorz Rozenberg, Arto Salomaa (Hrsg.), Handbuch der formalen Sprachen: Wort, Sprache, Grammatik , Springer, 1997, ISBN 3-540-60420-0Die

• Post, Emil (1947). „Rekursive Unlösbarkeit eines Problems von Thue“ . The Journal of Symbolic Logic . 12 (1): 1–11 . doi : 10.2307/2267170 . JSTOR  2267170. S2CID  30320278. Archiviert vom Original am 29.09.2019 . Abgerufen am 29.09.2019 .