| dc.date.accessioned | 2013-07-31T05:31:01Z | |
| dc.date.available | 2013-07-31T05:31:01Z | |
| dc.date.issued | 2013-07-31 | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2013073143236 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2013073143236 | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | parallel communicating | eng |
| dc.subject | restarting automata | eng |
| dc.subject | automata systems | eng |
| dc.subject | cooperating systems | eng |
| dc.subject | formal languages | eng |
| dc.subject.ddc | 004 | |
| dc.title | Systems of Parallel Communicating Restarting Automata | eng |
| dc.type | Dissertation | |
| dcterms.abstract | In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components).
Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird.
Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke.
Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen.
Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist. | ger |
| dcterms.abstract | In this thesis, systems of parallel communicating restarting automata (PCRA systems, for short) are introduced and studied. For this, two known concepts from formal language theory and automata theory are connected: the so-called PC systems (systems of parallel communicating components) and the model of restarting automata.
A PCRA system consists of finitely many restarting automata that, on the one hand, execute local computations independently of each other and, on the other hand, are allowed to communicate with each other. The communication is specified by a communication protocol and it is realized by specific communication states.
A basic property of the communication structure in systems of cooperating components is whether the communication is performed in a centralized or non-centralized manner. While in a non-centralized communication structure each component is allowed to communicate with each other component, in a centralized communication structure all communications have to include a fixed master component. One of the most important results of this thesis is that centralized and non-centralized PCRA systems have the same computational power (this does not hold for PC systems in general). Moreover, the usage of multicast or broadcast communications besides the point-to-point communications does not increase the computational power.
Further, the computational power of PCRA systems is investigated and compared with that of PC systems of finite automata and with that of multi-head finite automata. It is known that PC systems of finite automata have the same computational power as one-way multi-head finite automata and they form a lower bound for the computational power of PCRA systems of one-way restarting automata. Indeed, PCRA systems have even more power than PC systems of finite automata although the power of the components themselves is equal, i.e. they characterize the regular languages. For PCRA systems of two-way restarting automata, the language classes of two-way multi-head finite automata are shown to be lower bounds, which coincide with the known complexity classes L (deterministic logarithmically space bounded languages) and NL (nondeterministic logarithmically space bounded languages). As an upper bound, the class of context-sensitive languages is shown. In addition, extensions of restarting automata are considered (nonforgetting property, shrinking property) that increase the computational power of single restarting automata, but do not influence the power of systems.
The language classes that are characterized by PCRA systems are closed under many language operations and some classes are even abstract families of languages (so-called AFL's). Finally, some specific problems are considered with respect to their decidability. It is shown that emptiness, universality, inclusion, equality, and finiteness are not semi-decidable for systems with two restarting automata of the weakest type. The membership problem is decidable in quadratic time in the deterministic case and in exponential time in the nondeterministic case. | eng |
| dcterms.accessRights | open access | |
| dcterms.creator | Vollweiler, Marcel | |
| dc.contributor.corporatename | Kassel, Univ., Fachbereich Elektrotechnik / Informatik | |
| dc.contributor.referee | Otto, Friedrich (Prof. Dr.) | |
| dc.contributor.referee | Dassow, Jürgen (Prof. Dr.) | |
| dc.subject.ccs | F.1.1 | |
| dc.subject.ccs | F.1.2 | |
| dc.subject.msc | 68Q45 | ger |
| dc.subject.swd | Restart-Automat | ger |
| dc.date.examination | 2013-07-03 | |
