Dissertation
Ordered Restarting Automata
Zusammenfassung
In der folgenden Arbeit geht es um geordnete Restartautomaten. Restartautomaten sind ein theoretisches Modell, das in der Linguistik bei der Analyse durch Reduktion Verwendung findet. Die geordneten Restartautomaten wurden im Zusammenhang von zweidimensionalen Bildsprachen eingeführt und bilden das zugrundeliegende eindimensionale Modell.
Von diesem eindimensionalen Modell betrachten wir verschiedene Varianten und untersuchen und vergleichen hauptsächlich Sprachklassen und Beschreibungskomplexität. Eine Gemeinsamkeit all dieser Varianten ist die feste Fenstergröße von 3, und dass beim Schreiben das mittlere Zeichen durch ein kleineres Zeichen ersetzt wird. Wir untersuchen zunächst die Modelle, bei der Schreibvorgang immer gleichzeitig mit einem Restart verbunden ist.
Ausgehend von deterministischen Modell mit Zuständen betrachten wir recht bald die zustandslose Variante, da diese ebenso die regulären Sprachen charakterisiert. Damit haben wir eine Charakterisierung der regulären Sprachen, die ähnlich einfach ist, wie die eines DEA. Statt der Zustände haben wir Bandsymbole. Zusätzlich können wir viele Sprachen und auch Sprachoperation deutlich prägnanter darstellen. Zudem geben wir ausgehend von einem zustandslosen geordneten Restartautomaten, der sowohl deterministisch als auch nicht-deterministisch sein darf, eine allgemeine Konstruktion für einen NEA mit exponentiell vielen Zuständen an, der die selbe Sprache beschreibt, und zeigen dass die Konstruktion bis auf eine Konstante im Exponenten optimal ist.
Diese Konstruktion verwenden wir nun, um zu zeigen, dass viele interessante Entscheidungsprobleme unserer zustandsloser Restartautomaten PSPACE-vollständig sind. Die Idee dieser Konstruktion nutzen wir schließlich, um Reversibilität mit unserem Modell zu nutzen.
Einen weitere interessante Variante stellen schließlich die nicht-deterministischen geordneten Restartautomaten mit Zuständen dar. Dessen Sprachklasse ist recht ungewöhnlich, da sie Sprachen enthält die nicht einmal wachsend kontextsenstiv sind, aber wiederum nicht mal sehr einfache lineare Sprachen. Wir beweisen ein Pumping-Lemma, das es uns erlaubt Leerheit und Endlichkeit zu entscheiden.
Schließlich betrachten wir noch Varianten mit separater Rewrite- und Restartoperation. Während die Automaten mit Nichtdeterminismus und Zuständen alle kontextfreien Sprachen darstellen können, landen wir bei einer Einschränkung, sei es bei den Zuständen oder dem Determinismus, wieder bei den regulären Sprachen.
Wir konnten zeigen, dass alle interessanten Entscheidungsprobleme außer natürlich dem Wortproblem, unentscheidbar sind.
Von diesem eindimensionalen Modell betrachten wir verschiedene Varianten und untersuchen und vergleichen hauptsächlich Sprachklassen und Beschreibungskomplexität. Eine Gemeinsamkeit all dieser Varianten ist die feste Fenstergröße von 3, und dass beim Schreiben das mittlere Zeichen durch ein kleineres Zeichen ersetzt wird. Wir untersuchen zunächst die Modelle, bei der Schreibvorgang immer gleichzeitig mit einem Restart verbunden ist.
Ausgehend von deterministischen Modell mit Zuständen betrachten wir recht bald die zustandslose Variante, da diese ebenso die regulären Sprachen charakterisiert. Damit haben wir eine Charakterisierung der regulären Sprachen, die ähnlich einfach ist, wie die eines DEA. Statt der Zustände haben wir Bandsymbole. Zusätzlich können wir viele Sprachen und auch Sprachoperation deutlich prägnanter darstellen. Zudem geben wir ausgehend von einem zustandslosen geordneten Restartautomaten, der sowohl deterministisch als auch nicht-deterministisch sein darf, eine allgemeine Konstruktion für einen NEA mit exponentiell vielen Zuständen an, der die selbe Sprache beschreibt, und zeigen dass die Konstruktion bis auf eine Konstante im Exponenten optimal ist.
Diese Konstruktion verwenden wir nun, um zu zeigen, dass viele interessante Entscheidungsprobleme unserer zustandsloser Restartautomaten PSPACE-vollständig sind. Die Idee dieser Konstruktion nutzen wir schließlich, um Reversibilität mit unserem Modell zu nutzen.
Einen weitere interessante Variante stellen schließlich die nicht-deterministischen geordneten Restartautomaten mit Zuständen dar. Dessen Sprachklasse ist recht ungewöhnlich, da sie Sprachen enthält die nicht einmal wachsend kontextsenstiv sind, aber wiederum nicht mal sehr einfache lineare Sprachen. Wir beweisen ein Pumping-Lemma, das es uns erlaubt Leerheit und Endlichkeit zu entscheiden.
Schließlich betrachten wir noch Varianten mit separater Rewrite- und Restartoperation. Während die Automaten mit Nichtdeterminismus und Zuständen alle kontextfreien Sprachen darstellen können, landen wir bei einer Einschränkung, sei es bei den Zuständen oder dem Determinismus, wieder bei den regulären Sprachen.
Wir konnten zeigen, dass alle interessanten Entscheidungsprobleme außer natürlich dem Wortproblem, unentscheidbar sind.
The following thesis deals with ordered restarting automata. Restarting automata are a theoretical model used in linguistics for the analysis by reduction. The ordered restarting automata were introduced in the context of two-dimensional picture languages and form the underlying one-dimensional model.
Here we look at different variants of this one-dimensional model and examine issues related to language classes and descriptional complexity.
A common feature of all these variants is the fixed window size of 3, and that the middle character is replaced by a smaller character in a rewrite step. First of all, we examine the models in which the rewriting process is always connected to a restart.
Starting from the deterministic model with states we will soon consider the stateless variant, as it also characterizes the regular languages. This gives us a characterization of the regular languages, which is as simple as that by a DFA. Instead of the states we use tape symbols to measure the size of such an automaton. In addition, we are able to present many languages and language operations more concisely. Moreover, starting from a stateless ordered restarting automaton, which may be deterministic or non-deterministic, we specify a general construction of an NFA with exponentially many states that describes the same language and we show that the construction is optimal except for the constant in the exponent.
We then use this construction to show that many interesting decision problems for our stateless restarting automata are PSPACE-complete. Finally, we use the idea of this construction to introduce reversibility for our model.
Another interesting variant is the nondeterministic restarting automaton with states. Its language class is quite unusual, since it contains languages that are not even context-sensitive, but on the other hand, it does not even contain some simple linear languages. Additionally, we prove a pumping lemma that allows us to decide emptiness and finiteness.
Finally, we consider the variants with separate rewrite and restart operations. While restarting automata with nondeterminism and states can express all context-free languages, we end up with regular languages, whenever we do not allow states or nondeterminism.
We were able to show that all interesting decision problems except the word problem are undecidable in this setting.
Here we look at different variants of this one-dimensional model and examine issues related to language classes and descriptional complexity.
A common feature of all these variants is the fixed window size of 3, and that the middle character is replaced by a smaller character in a rewrite step. First of all, we examine the models in which the rewriting process is always connected to a restart.
Starting from the deterministic model with states we will soon consider the stateless variant, as it also characterizes the regular languages. This gives us a characterization of the regular languages, which is as simple as that by a DFA. Instead of the states we use tape symbols to measure the size of such an automaton. In addition, we are able to present many languages and language operations more concisely. Moreover, starting from a stateless ordered restarting automaton, which may be deterministic or non-deterministic, we specify a general construction of an NFA with exponentially many states that describes the same language and we show that the construction is optimal except for the constant in the exponent.
We then use this construction to show that many interesting decision problems for our stateless restarting automata are PSPACE-complete. Finally, we use the idea of this construction to introduce reversibility for our model.
Another interesting variant is the nondeterministic restarting automaton with states. Its language class is quite unusual, since it contains languages that are not even context-sensitive, but on the other hand, it does not even contain some simple linear languages. Additionally, we prove a pumping lemma that allows us to decide emptiness and finiteness.
Finally, we consider the variants with separate rewrite and restart operations. While restarting automata with nondeterminism and states can express all context-free languages, we end up with regular languages, whenever we do not allow states or nondeterminism.
We were able to show that all interesting decision problems except the word problem are undecidable in this setting.
Zitieren
@phdthesis{urn:nbn:de:hebis:34-2018071155827,
author={Kwee, Kent},
title={Ordered Restarting Automata},
school={Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik},
month={07},
year={2018}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2018$n2018 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2018071155827 3000 Kwee, Kent 4000 Ordered Restarting Automata / Kwee, Kent 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2018071155827=x R 4204 \$dDissertation 4170 5550 {{Theoretische Informatik}} 5550 {{Automatentheorie}} 5550 {{Restart-Automat}} 7136 ##0##urn:nbn:de:hebis:34-2018071155827
2018-07-11T11:33:52Z 2018-07-11T11:33:52Z 2018-07-10 978-3-746741-27-7 urn:nbn:de:hebis:34-2018071155827 http://hdl.handle.net/123456789/2018071155827 eng epubli Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ restarting automata ordered rewriting descriptional complexity decision problems pumping lemma Theoretische Informatik Automatentheorie Restart-Automat 004 Ordered Restarting Automata Dissertation In der folgenden Arbeit geht es um geordnete Restartautomaten. Restartautomaten sind ein theoretisches Modell, das in der Linguistik bei der Analyse durch Reduktion Verwendung findet. Die geordneten Restartautomaten wurden im Zusammenhang von zweidimensionalen Bildsprachen eingeführt und bilden das zugrundeliegende eindimensionale Modell. Von diesem eindimensionalen Modell betrachten wir verschiedene Varianten und untersuchen und vergleichen hauptsächlich Sprachklassen und Beschreibungskomplexität. Eine Gemeinsamkeit all dieser Varianten ist die feste Fenstergröße von 3, und dass beim Schreiben das mittlere Zeichen durch ein kleineres Zeichen ersetzt wird. Wir untersuchen zunächst die Modelle, bei der Schreibvorgang immer gleichzeitig mit einem Restart verbunden ist. Ausgehend von deterministischen Modell mit Zuständen betrachten wir recht bald die zustandslose Variante, da diese ebenso die regulären Sprachen charakterisiert. Damit haben wir eine Charakterisierung der regulären Sprachen, die ähnlich einfach ist, wie die eines DEA. Statt der Zustände haben wir Bandsymbole. Zusätzlich können wir viele Sprachen und auch Sprachoperation deutlich prägnanter darstellen. Zudem geben wir ausgehend von einem zustandslosen geordneten Restartautomaten, der sowohl deterministisch als auch nicht-deterministisch sein darf, eine allgemeine Konstruktion für einen NEA mit exponentiell vielen Zuständen an, der die selbe Sprache beschreibt, und zeigen dass die Konstruktion bis auf eine Konstante im Exponenten optimal ist. Diese Konstruktion verwenden wir nun, um zu zeigen, dass viele interessante Entscheidungsprobleme unserer zustandsloser Restartautomaten PSPACE-vollständig sind. Die Idee dieser Konstruktion nutzen wir schließlich, um Reversibilität mit unserem Modell zu nutzen. Einen weitere interessante Variante stellen schließlich die nicht-deterministischen geordneten Restartautomaten mit Zuständen dar. Dessen Sprachklasse ist recht ungewöhnlich, da sie Sprachen enthält die nicht einmal wachsend kontextsenstiv sind, aber wiederum nicht mal sehr einfache lineare Sprachen. Wir beweisen ein Pumping-Lemma, das es uns erlaubt Leerheit und Endlichkeit zu entscheiden. Schließlich betrachten wir noch Varianten mit separater Rewrite- und Restartoperation. Während die Automaten mit Nichtdeterminismus und Zuständen alle kontextfreien Sprachen darstellen können, landen wir bei einer Einschränkung, sei es bei den Zuständen oder dem Determinismus, wieder bei den regulären Sprachen. Wir konnten zeigen, dass alle interessanten Entscheidungsprobleme außer natürlich dem Wortproblem, unentscheidbar sind. The following thesis deals with ordered restarting automata. Restarting automata are a theoretical model used in linguistics for the analysis by reduction. The ordered restarting automata were introduced in the context of two-dimensional picture languages and form the underlying one-dimensional model. Here we look at different variants of this one-dimensional model and examine issues related to language classes and descriptional complexity. A common feature of all these variants is the fixed window size of 3, and that the middle character is replaced by a smaller character in a rewrite step. First of all, we examine the models in which the rewriting process is always connected to a restart. Starting from the deterministic model with states we will soon consider the stateless variant, as it also characterizes the regular languages. This gives us a characterization of the regular languages, which is as simple as that by a DFA. Instead of the states we use tape symbols to measure the size of such an automaton. In addition, we are able to present many languages and language operations more concisely. Moreover, starting from a stateless ordered restarting automaton, which may be deterministic or non-deterministic, we specify a general construction of an NFA with exponentially many states that describes the same language and we show that the construction is optimal except for the constant in the exponent. We then use this construction to show that many interesting decision problems for our stateless restarting automata are PSPACE-complete. Finally, we use the idea of this construction to introduce reversibility for our model. Another interesting variant is the nondeterministic restarting automaton with states. Its language class is quite unusual, since it contains languages that are not even context-sensitive, but on the other hand, it does not even contain some simple linear languages. Additionally, we prove a pumping lemma that allows us to decide emptiness and finiteness. Finally, we consider the variants with separate rewrite and restart operations. While restarting automata with nondeterminism and states can express all context-free languages, we end up with regular languages, whenever we do not allow states or nondeterminism. We were able to show that all interesting decision problems except the word problem are undecidable in this setting. open access Kwee, Kent Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik Otto, Friedrich (Prof. Dr.) Kutrib, Martin (Prof. Dr.) 68Q05 68Q42 68Q45 68Q25 Theoretische Informatik Automatentheorie Restart-Automat 2018-06-08
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden:
:Urheberrechtlich geschützt