Date
2008-09-10Metadata
Show full item record
Dissertation
CD-Systems of Restarting Automata
Abstract
Die vorliegende Arbeit behandelt Restartautomaten und Erweiterungen von Restartautomaten.
Restartautomaten sind ein Werkzeug zum Erkennen formaler Sprachen. Sie sind motiviert durch
die linguistische Methode der Analyse durch Reduktion und wurden 1995 von Jancar, Mráz, Plátek und Vogel eingeführt.
Restartautomaten bestehen aus einer endlichen Kontrolle, einem Lese/Schreibfenster fester Größe und einem flexiblen Band. Anfänglich enthält dieses sowohl die Eingabe als auch Bandbegrenzungssymbole.
Die Berechnung eines Restartautomaten läuft in so genannten Zyklen ab. Diese beginnen am linken Rand im Startzustand, in ihnen wird eine lokale Ersetzung auf dem Band durchgeführt und sie enden mit einem Neustart, bei dem das Lese/Schreibfenster wieder an den linken Rand bewegt wird und der Startzustand wieder eingenommen wird.
Die vorliegende Arbeit beschäftigt sich hauptsächlich mit zwei Erweiterungen der Restartautomaten:
CD-Systeme von Restartautomaten und nichtvergessende Restartautomaten. Nichtvergessende Restartautomaten können einen Zyklus in einem beliebigen Zustand beenden und CD-Systeme
von Restartautomaten bestehen aus einer Menge von Restartautomaten, die zusammen die Eingabe verarbeiten. Dabei wird ihre Zusammenarbeit durch einen Operationsmodus, ähnlich wie bei CD-Grammatik Systemen, geregelt.
Für beide Erweiterungen zeigt sich, dass die deterministischen Modelle mächtiger sind als deterministische Standardrestartautomaten. Es wird gezeigt, dass CD-Systeme von Restartautomaten in vielen Fällen durch nichtvergessende Restartautomaten simuliert werden können und andererseits lassen sich auch nichtvergessende Restartautomaten durch CD-Systeme von Restartautomaten simulieren.
Des Weiteren werden Restartautomaten und nichtvergessende Restartautomaten untersucht, die nichtdeterministisch sind, aber keine Fehler machen. Es zeigt sich, dass diese Automaten durch deterministische (nichtvergessende) Restartautomaten simuliert werden können, wenn sie direkt nach der Ersetzung einen neuen Zyklus beginnen, oder ihr Fenster nach links und rechts bewegen können. Außerdem gilt, dass alle (nichtvergessenden) Restartautomaten, die zwar Fehler machen dürfen, diese aber nach endlich vielen Zyklen erkennen, durch (nichtvergessende) Restartautomaten simuliert werden können, die keine Fehler machen.
Ein weiteres wichtiges Resultat besagt, dass die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt den Zyklus beenden, genau die deterministischen kontextfreien Sprachen erkennen, wohingegen die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen ohne diese Einschränkung echt mehr, nämlich die links-rechts regulären Sprachen, erkennen. Damit werden zum ersten Mal Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt ihren Zyklus beenden, von Restartautomaten desselben Typs ohne diese Einschränkung getrennt. Besonders erwähnenswert ist hierbei, dass beide Automatentypen wohlbekannte Sprachklassen beschreiben.
Restartautomaten sind ein Werkzeug zum Erkennen formaler Sprachen. Sie sind motiviert durch
die linguistische Methode der Analyse durch Reduktion und wurden 1995 von Jancar, Mráz, Plátek und Vogel eingeführt.
Restartautomaten bestehen aus einer endlichen Kontrolle, einem Lese/Schreibfenster fester Größe und einem flexiblen Band. Anfänglich enthält dieses sowohl die Eingabe als auch Bandbegrenzungssymbole.
Die Berechnung eines Restartautomaten läuft in so genannten Zyklen ab. Diese beginnen am linken Rand im Startzustand, in ihnen wird eine lokale Ersetzung auf dem Band durchgeführt und sie enden mit einem Neustart, bei dem das Lese/Schreibfenster wieder an den linken Rand bewegt wird und der Startzustand wieder eingenommen wird.
Die vorliegende Arbeit beschäftigt sich hauptsächlich mit zwei Erweiterungen der Restartautomaten:
CD-Systeme von Restartautomaten und nichtvergessende Restartautomaten. Nichtvergessende Restartautomaten können einen Zyklus in einem beliebigen Zustand beenden und CD-Systeme
von Restartautomaten bestehen aus einer Menge von Restartautomaten, die zusammen die Eingabe verarbeiten. Dabei wird ihre Zusammenarbeit durch einen Operationsmodus, ähnlich wie bei CD-Grammatik Systemen, geregelt.
Für beide Erweiterungen zeigt sich, dass die deterministischen Modelle mächtiger sind als deterministische Standardrestartautomaten. Es wird gezeigt, dass CD-Systeme von Restartautomaten in vielen Fällen durch nichtvergessende Restartautomaten simuliert werden können und andererseits lassen sich auch nichtvergessende Restartautomaten durch CD-Systeme von Restartautomaten simulieren.
Des Weiteren werden Restartautomaten und nichtvergessende Restartautomaten untersucht, die nichtdeterministisch sind, aber keine Fehler machen. Es zeigt sich, dass diese Automaten durch deterministische (nichtvergessende) Restartautomaten simuliert werden können, wenn sie direkt nach der Ersetzung einen neuen Zyklus beginnen, oder ihr Fenster nach links und rechts bewegen können. Außerdem gilt, dass alle (nichtvergessenden) Restartautomaten, die zwar Fehler machen dürfen, diese aber nach endlich vielen Zyklen erkennen, durch (nichtvergessende) Restartautomaten simuliert werden können, die keine Fehler machen.
Ein weiteres wichtiges Resultat besagt, dass die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt den Zyklus beenden, genau die deterministischen kontextfreien Sprachen erkennen, wohingegen die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen ohne diese Einschränkung echt mehr, nämlich die links-rechts regulären Sprachen, erkennen. Damit werden zum ersten Mal Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt ihren Zyklus beenden, von Restartautomaten desselben Typs ohne diese Einschränkung getrennt. Besonders erwähnenswert ist hierbei, dass beide Automatentypen wohlbekannte Sprachklassen beschreiben.
In this work restarting automata and extensions of restarting automata are studied. Restarting automata are a tool to recognize formal languages. They are motivated by the linguistic method of analysis by reduction and were introduced 1995 by Jancar, Mráz, Plátek and Vogel. Restarting automata consist of a finite control, a read/write window of fixed size and a flexible tape. Initially the tape contains the input as well as border markers. A computation of a restarting automaton consists of so-called cycles. Each cycle starts at the left end of the tape in an initial state. In each cycle a local rewrite on the tape is performed and a cycle ends with a restart, which
causes the automaton to move its window to the left end of the tape and to re-enter the initial state.
The present work studies mainly two extensions of restarting automata: CD-systems of restarting automata and nonforgetting restarting automata. Nonforgetting restarting automata can end a cycle in any state and CD-systems of restarting automata consist of finitely many restarting automata, that work together in order to accept the input. The cooperation is controlled by a mode of operation similar to CD-grammar systems. For both extensions it is shown that the deterministic models are more expressive than normal restarting automata. It is shown that in many cases CD-systems of restarting automata can be simulated by nonforgetting restarting automata and vice versa. In addition restarting automata and nonforgetting restarting automata that are nondeterministic but make no mistakes are studied. It is shown that these automata can be simulated by deterministic (nonforgetting) restarting automata, if they are forced to restart immediately after the rewrite or if they are able to move to the left and to the right. Furthermore, (nonforgetting) restarting automata that are allowed to make mistakes, but detect their mistakes after finitely many cycles can be simulated by (nonforgetting) restarting automata that make no mistakes. Another important result states that deterministic monotone nonforgetting restarting automata that restart immediately after the rewrite recognize exactly the context free languages, while deterministic monotone nonforgetting restarting automata without that restriction recognize strictly
moretlanguages, namely those generated by left-right regular grammars. This is the first time that restarting automata with the restriction of joined rewrite and restart are separated from those without this restriction. In particular both types of automata describe well known language classes.
causes the automaton to move its window to the left end of the tape and to re-enter the initial state.
The present work studies mainly two extensions of restarting automata: CD-systems of restarting automata and nonforgetting restarting automata. Nonforgetting restarting automata can end a cycle in any state and CD-systems of restarting automata consist of finitely many restarting automata, that work together in order to accept the input. The cooperation is controlled by a mode of operation similar to CD-grammar systems. For both extensions it is shown that the deterministic models are more expressive than normal restarting automata. It is shown that in many cases CD-systems of restarting automata can be simulated by nonforgetting restarting automata and vice versa. In addition restarting automata and nonforgetting restarting automata that are nondeterministic but make no mistakes are studied. It is shown that these automata can be simulated by deterministic (nonforgetting) restarting automata, if they are forced to restart immediately after the rewrite or if they are able to move to the left and to the right. Furthermore, (nonforgetting) restarting automata that are allowed to make mistakes, but detect their mistakes after finitely many cycles can be simulated by (nonforgetting) restarting automata that make no mistakes. Another important result states that deterministic monotone nonforgetting restarting automata that restart immediately after the rewrite recognize exactly the context free languages, while deterministic monotone nonforgetting restarting automata without that restriction recognize strictly
moretlanguages, namely those generated by left-right regular grammars. This is the first time that restarting automata with the restriction of joined rewrite and restart are separated from those without this restriction. In particular both types of automata describe well known language classes.
Citation
@phdthesis{urn:nbn:de:hebis:34-2008091023548,
author={Messerschmidt, Hartmut},
title={CD-Systems of Restarting Automata},
school={Kassel, Universität, FB 16, Elektrotechnik/Informatik},
month={09},
year={2008}
}
0500 Oax
0501 Text $btxt$2rdacontent
0502 Computermedien $bc$2rdacarrier
1100 2008$n2008
1500 1/eng
2050 ##0##urn:nbn:de:hebis:34-2008091023548
3000 Messerschmidt, Hartmut
4000 CD-Systems of Restarting Automata / Messerschmidt, Hartmut
4030
4060 Online-Ressource
4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2008091023548=x R
4204 \$dDissertation
4170
5550 {{Theoretische Informatik}}
5550 {{Automatentheorie}}
7136 ##0##urn:nbn:de:hebis:34-2008091023548
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2008-09-10T11:41:33Z 2008-09-10T11:41:33Z 2008-09-10T11:41:33Z urn:nbn:de:hebis:34-2008091023548 http://hdl.handle.net/123456789/2008091023548 879116 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Automatentheorie Restartautomaten CD-Systeme Sprachklassen 004 CD-Systems of Restarting Automata Dissertation Die vorliegende Arbeit behandelt Restartautomaten und Erweiterungen von Restartautomaten. Restartautomaten sind ein Werkzeug zum Erkennen formaler Sprachen. Sie sind motiviert durch die linguistische Methode der Analyse durch Reduktion und wurden 1995 von Jancar, Mráz, Plátek und Vogel eingeführt. Restartautomaten bestehen aus einer endlichen Kontrolle, einem Lese/Schreibfenster fester Größe und einem flexiblen Band. Anfänglich enthält dieses sowohl die Eingabe als auch Bandbegrenzungssymbole. Die Berechnung eines Restartautomaten läuft in so genannten Zyklen ab. Diese beginnen am linken Rand im Startzustand, in ihnen wird eine lokale Ersetzung auf dem Band durchgeführt und sie enden mit einem Neustart, bei dem das Lese/Schreibfenster wieder an den linken Rand bewegt wird und der Startzustand wieder eingenommen wird. Die vorliegende Arbeit beschäftigt sich hauptsächlich mit zwei Erweiterungen der Restartautomaten: CD-Systeme von Restartautomaten und nichtvergessende Restartautomaten. Nichtvergessende Restartautomaten können einen Zyklus in einem beliebigen Zustand beenden und CD-Systeme von Restartautomaten bestehen aus einer Menge von Restartautomaten, die zusammen die Eingabe verarbeiten. Dabei wird ihre Zusammenarbeit durch einen Operationsmodus, ähnlich wie bei CD-Grammatik Systemen, geregelt. Für beide Erweiterungen zeigt sich, dass die deterministischen Modelle mächtiger sind als deterministische Standardrestartautomaten. Es wird gezeigt, dass CD-Systeme von Restartautomaten in vielen Fällen durch nichtvergessende Restartautomaten simuliert werden können und andererseits lassen sich auch nichtvergessende Restartautomaten durch CD-Systeme von Restartautomaten simulieren. Des Weiteren werden Restartautomaten und nichtvergessende Restartautomaten untersucht, die nichtdeterministisch sind, aber keine Fehler machen. Es zeigt sich, dass diese Automaten durch deterministische (nichtvergessende) Restartautomaten simuliert werden können, wenn sie direkt nach der Ersetzung einen neuen Zyklus beginnen, oder ihr Fenster nach links und rechts bewegen können. Außerdem gilt, dass alle (nichtvergessenden) Restartautomaten, die zwar Fehler machen dürfen, diese aber nach endlich vielen Zyklen erkennen, durch (nichtvergessende) Restartautomaten simuliert werden können, die keine Fehler machen. Ein weiteres wichtiges Resultat besagt, dass die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt den Zyklus beenden, genau die deterministischen kontextfreien Sprachen erkennen, wohingegen die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen ohne diese Einschränkung echt mehr, nämlich die links-rechts regulären Sprachen, erkennen. Damit werden zum ersten Mal Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt ihren Zyklus beenden, von Restartautomaten desselben Typs ohne diese Einschränkung getrennt. Besonders erwähnenswert ist hierbei, dass beide Automatentypen wohlbekannte Sprachklassen beschreiben. In this work restarting automata and extensions of restarting automata are studied. Restarting automata are a tool to recognize formal languages. They are motivated by the linguistic method of analysis by reduction and were introduced 1995 by Jancar, Mráz, Plátek and Vogel. Restarting automata consist of a finite control, a read/write window of fixed size and a flexible tape. Initially the tape contains the input as well as border markers. A computation of a restarting automaton consists of so-called cycles. Each cycle starts at the left end of the tape in an initial state. In each cycle a local rewrite on the tape is performed and a cycle ends with a restart, which causes the automaton to move its window to the left end of the tape and to re-enter the initial state. The present work studies mainly two extensions of restarting automata: CD-systems of restarting automata and nonforgetting restarting automata. Nonforgetting restarting automata can end a cycle in any state and CD-systems of restarting automata consist of finitely many restarting automata, that work together in order to accept the input. The cooperation is controlled by a mode of operation similar to CD-grammar systems. For both extensions it is shown that the deterministic models are more expressive than normal restarting automata. It is shown that in many cases CD-systems of restarting automata can be simulated by nonforgetting restarting automata and vice versa. In addition restarting automata and nonforgetting restarting automata that are nondeterministic but make no mistakes are studied. It is shown that these automata can be simulated by deterministic (nonforgetting) restarting automata, if they are forced to restart immediately after the rewrite or if they are able to move to the left and to the right. Furthermore, (nonforgetting) restarting automata that are allowed to make mistakes, but detect their mistakes after finitely many cycles can be simulated by (nonforgetting) restarting automata that make no mistakes. Another important result states that deterministic monotone nonforgetting restarting automata that restart immediately after the rewrite recognize exactly the context free languages, while deterministic monotone nonforgetting restarting automata without that restriction recognize strictly moretlanguages, namely those generated by left-right regular grammars. This is the first time that restarting automata with the restriction of joined rewrite and restart are separated from those without this restriction. In particular both types of automata describe well known language classes. open access Messerschmidt, Hartmut Kassel, Universität, FB 16, Elektrotechnik/Informatik Otto, Friedrich (Prof. Dr.) Dassow, Jürgen (Prof. Dr.) F.4.3 Formal Languages Theoretische Informatik Automatentheorie 2008-05-08 </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt