Relations and Transductions Realized by Restarting Automata
| dc.contributor.corporatename | Kassel, Universität, FB 16, Elektrotechnik/Informatik | |
| dc.contributor.referee | Otto, Friedrich (Prof. Dr.) | |
| dc.contributor.referee | Kutrib, Martin (Prof. Dr.) | |
| dc.date.accessioned | 2013-10-09T06:48:25Z | |
| dc.date.available | 2013-10-09T06:48:25Z | |
| dc.date.examination | 2013-05-17 | |
| dc.date.issued | 2013-10-09 | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2013100944207 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2013100944207 | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | restarting automata | eng |
| dc.subject | restarting transducers | eng |
| dc.subject | transducers | eng |
| dc.subject | word relations | eng |
| dc.subject | transductions | eng |
| dc.subject | observer systems | eng |
| dc.subject.ccs | F.1.1 | |
| dc.subject.ccs | F.4.3 | |
| dc.subject.ddc | 004 | |
| dc.subject.msc | 68Q05 | ger |
| dc.subject.msc | 68Q45 | ger |
| dc.subject.swd | Theoretische Informatik | ger |
| dc.subject.swd | Automatentheorie | ger |
| dc.subject.swd | Restart-Automat | ger |
| dc.title | Relations and Transductions Realized by Restarting Automata | eng |
| dc.type | Dissertation | |
| dcterms.abstract | Gegenstand der vorliegenden Arbeit ist die Analyse verschiedener Formalismen zur Berechnung binärer Wortrelationen. Dabei ist die Grundlage aller hier ausgeführten Betrachtungen das Modell der Restart-Automaten, welches 1995 von Jancar et. al. eingeführt wurde. Zum einen wird das bereits für Restart-Automaten bekannte Konzept der input/output- und proper-Relationen weiterführend untersucht, sowie auf Systeme von zwei parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (PC-Systeme) erweitert. Zum anderen wird eine Variante der Restart-Automaten eingeführt, die sich an klassischen Automatenmodellen zur Berechnung von Relationen orientiert. Mit Hilfe dieser Mechanismen kann gezeigt werden, dass einige Klassen, die durch input/output- und proper-Relationen von Restart Automaten definiert werden, mit den traditionellen Relationsklassen der Rationalen Relationen und der Pushdown-Relationen übereinstimmen. Weiterhin stellt sich heraus, dass das Konzept der parallel kommunizierenden Automaten äußerst mächtig ist, da bereits die Klasse der proper-Relationen von monotonen PC-Systemen alle berechenbaren Relationen umfasst. Der Haupteil der Arbeit beschäftigt sich mit den so genannten Restart-Transducern, welche um eine Ausgabefunktion erweiterte Restart-Automaten sind. Es zeigt sich, dass sich insbesondere dieses Modell mit seinen verschiedenen Erweiterungen und Einschränkungen dazu eignet, eine umfassende Hierarchie von Relationsklassen zu etablieren. In erster Linie seien hier die verschiedenen Typen von monotonen Restart-Transducern erwähnt, mit deren Hilfe viele interessante neue und bekannte Relationsklassen innerhalb der längenbeschränkten Pushdown-Relationen charakterisiert werden. Abschließend wird, im Kontrast zu den vorhergehenden Modellen, das nicht auf Restart-Automaten basierende Konzept des Übersetzens durch Beobachtung ("Transducing by Observing") zur Relationsberechnung eingeführt. Dieser, den Restart-Transducern nicht unähnliche Mechanismus, wird im weitesten Sinne dazu genutzt, einen anderen Blickwinkel auf die von Restart-Transducern definierten Relationen einzunehmen, sowie eine obere Schranke für die Berechnungskraft der Restart-Transducer zu gewinnen. | ger |
| dcterms.abstract | In the present thesis we introduce several ways of extending restarting automata to devices for realizing binary (word) relations, which is mainly motivated by linguistics. In particular, we adapt the notion of input/output-relations and proper-relations to restarting automata and to parallel communicating systems of two restarting automata (PC-systems). Further, we introduce a new model, called restarting transducer. Concerning input/output- and proper-relations we show equivalences of relation classes defined by restarting automata to the well-known classes of rational relations and pushdown relations. Further, regarding the proper-relations realized by certain PC-systems of two restarting automata, we show that this class includes all computable relations. The main part of this work concerns restarting transducers. A restarting transducer is a restarting automaton equipped with an output function. In this way we show that the hierarchy of language classes defined by restarting automata can be partly transfered to a corresponding hierarchy of relation classes. Moreover, by using results from the concepts introduced before, we prove that monotone types of restarting transducers define a hierachy of relation classes within the length-bounded pushdown relations. We conclude this thesis by establishing an upper bound and a different point of view on relations realized by restarting transducers through the concept of Transducing by Observing. | eng |
| dcterms.accessRights | open access | |
| dcterms.creator | Hundeshagen, Norbert |