Suche   SiteMap
Home
A bis Z
BIB-KAT
Andere Bibliothekskataloge
Digitale Medien
Dokumentlieferung
Fachspezifische Informationen
Suchhilfen und Datenbanken
 
Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:hbz:385-11184
URL: http://ubt.opus.hbz-nrw.de/volltexte/2018/1118/


Operations on Graphs, Arrays and Automata

Operationen auf Graphen, Arrays und Automaten

Paramasivan, Meenakshi

pdf-Format:
Dokument 1.pdf (1.792 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Graphen mit Eulerschen Pfaden, jumping endliche Automaten, endliche Boustrophedon-Automaten, zurückkehrende(RFA), (regulär: regulär) Array-Grammati
Freie Schlagwörter (Deutsch): Graphen mit Eulerschen Pfaden, jumping endliche Automaten, endliche Boustrophedon-Automaten, zurückkehrende(RFA), (regulär: regulär) Array-Grammati
Freie Schlagwörter (Englisch): Eulerian trails, (general) jumping finite automata, (general) boustrophedon (returning) finite automata, (regular : regular) array grammars
Institut: Informatik
Fakultät: Fachbereich 4
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Fernau, Henning (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 25.09.2017
Erstellungsjahr: 2017
Publikationsdatum: 30.01.2018
Kurzfassung auf Englisch: Automata theory is the study of abstract machines. It is a theory in theoretical computer science and discrete mathematics (a subject of study in mathematics and computer science). The word automata (the plural of automaton) comes from a Greek word which means “self-acting”. Automata theory is closely related to formal language theory [99, 101]. The theory of formal languages constitutes the backbone of the field of science now generally known as theoretical computer science. This thesis aims to introduce a few types of automata and studies then class of languages recognized by them.
Chapter 1 is the road map with introduction and preliminaries. In Chapter 2 we consider few formal languages associated to graphs that has Eulerian trails. We place few languages in the Chomsky hierarchy that has some other properties together with the Eulerian property. In Chapter 3 we consider jumping finite automata, i. e., finite automata in which input head after reading and consuming a symbol, can jump to an arbitrary position of the remaining input. We characterize the class of languages described by jumping finite automata in terms of special shuffle expressions and survey other equivalent notions from the existing literature. We could also characterize some super classes of this language class. In Chapter 4 we introduce boustrophedon finite automata, i. e., finite automata working on rectangular shaped arrays (i. e., pictures) in a boustrophedon mode and we also introduce returning finite automata that reads the input, line after line, does not alters the direction like boustrophedon finite automata i. e., reads always from left to right, line after line. We provide close relationships with the well-established class of regular matrix (array) languages. We sketch possible applications to character recognition and kolam patterns. Chapter 5 deals with general boustrophedon finite automata, general returning finite automata that read with different scanning strategies. We show that all 32 different variants only describe two different classes of array languages. We also introduce Mealy machines working on pictures and show how these can be used in a modular design of picture processing devices. In Chapter 6 we compare three different types of regular grammars of array languages introduced in the literature, regular matrix grammars, (regular : regular) array grammars, isometric regular array grammars, and variants thereof, focusing on hierarchical questions. We also refine the presentation of (regular : regular) array grammars in order to clarify the interrelations. In Chapter 7 we provide further directions of research with respect to the study that we have done in each of the chapters.
Kurzfassung auf Deutsch: Automatentheorie ist das Studium der abstrakten Maschinen. Es ist ein Teilgebiet der theoretischen Informatik und diskreten Mathematik. Das Wort Automat stammt dem Griechischen und bedeutet "selbsttätig denkend". Die Automatentheorie ist eng mit der formalen Sprachtheorie verwandt [95, 97]. Die Theorie der formalen Sprachen bildet die Grundlage des Wissenschaftsfeldes, welches heute allgemein als theoretische Informatik bekannt ist. Diese Doktorarbeit zielt darauf ab, diverse Arten von Automaten einzuführen und die von ihnen erkannte Klasse von Sprachen zu studieren.
Kapitel 1 gibt eine allgemeine Einführung und stellt die für die Arbeit relevanten Begriffe vor. In Kapitel 2 werden formale Sprachen untersucht, die eng mit der Klasse der Graphen mit Eulerschen Pfaden verbunden sind. Einige dieser Sprachen werden in die Chomsky Hierarchie eingeordnet. Kapitel 3 behandelt endliche Automaten, deren Eingangskopf nach dem Lesen und Verarbeiten eines Symbols zu einer beliebigen Position des verbleibenden Eingangs springen kann. Die Klasse der Sprachen, die durch das Springen von endlichen Automaten in Form von speziellen Shuffle-Ausdrücken beschrieben werden können wird charakterisiert. Des weiteren werden äquivalente Begriffe aus der vorhandenen Literatur untersucht und einige Oberklassen dieser Sprachklasse charakterisiert. Kapitel 4 stellt verallgemeinerte endliche Boustrophedon-Automaten und verallgemeinerte zurückkehrende endliche Automaten (RFA) vor, die mit verschiedenen Scan-Strategien lesen können. Es wird gezeigt, dass die 32 betrachteten Varianten nur zwei verschiedene Klassen von Array-Sprachen beschreiben. Des weiteren werden an Bildern arbeitende Mealy-Maschinen vorgestellt und gezeigt, wie diese in einem modularen Design von Bildverarbeitungsgeräten verwendet werden können. Kapitel 5 befasst sich mit endlichen Boustrophedon Automaten und zurückkehrenden endlichen Automaten und stellt eine enge Beziehung dieser zu der etablierten Klasse regulärer Matrix- (Array-)Sprachen her. Es werden mögliche Anwendungen für Zeichenerkennung und Kolam-Muster skizziert. In Kapitel 6 werden drei verschiedene in der Literatur eingeführte Arten regulärer Grammatiken von Array-Sprachen verglichen: regelmäßige Matrix-Grammatiken, (regulär: regulär) Array-Grammatiken, isometrische reguläre Array-Grammatiken und Varianten dieser, die sich auf hierarchische Fragen konzentrieren. Außerdem wird die Präsentation von (regulär: regulär) Array-Grammatiken verfeinert, um Zusammenhänge zu anderen Grammatiken zu verdeutlichen. In Kapitel 7 wird aufgezeigt, wie die in der Doktorarbeit vorgestellten Forschungsergebnisse weitergeführt werden können.

Home | Suchen | Veröffentlichen | Hilfe | Viewer