| dc.date.accessioned | 2018-07-11T11:33:52Z | |
| dc.date.available | 2018-07-11T11:33:52Z | |
| dc.date.issued | 2018-07-10 | |
| dc.identifier.isbn | 978-3-746741-27-7 | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2018071155827 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2018071155827 | |
| dc.language.iso | eng | |
| dc.publisher | epubli | ger |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | restarting automata | eng |
| dc.subject | ordered rewriting | eng |
| dc.subject | descriptional complexity | eng |
| dc.subject | decision problems | eng |
| dc.subject | pumping lemma | eng |
| dc.subject | Theoretische Informatik | ger |
| dc.subject | Automatentheorie | ger |
| dc.subject | Restart-Automat | ger |
| dc.subject.ddc | 004 | |
| dc.title | Ordered Restarting Automata | eng |
| dc.type | Dissertation | |
| dcterms.abstract | 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. | ger |
| dcterms.abstract | 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. | eng |
| dcterms.accessRights | open access | |
| dcterms.creator | Kwee, Kent | |
| dc.contributor.corporatename | Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatik | |
| dc.contributor.referee | Otto, Friedrich (Prof. Dr.) | |
| dc.contributor.referee | Kutrib, Martin (Prof. Dr.) | |
| dc.subject.msc | 68Q05 | ger |
| dc.subject.msc | 68Q42 | ger |
| dc.subject.msc | 68Q45 | ger |
| dc.subject.msc | 68Q25 | ger |
| dc.subject.swd | Theoretische Informatik | ger |
| dc.subject.swd | Automatentheorie | ger |
| dc.subject.swd | Restart-Automat | ger |
| dc.date.examination | 2018-06-08 | |
