Operations on Graphs, Arrays and Automata

Operationen auf Graphen, Arrays und Automaten

  • 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.
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Meenakshi Paramasivan
URN:urn:nbn:de:hbz:385-11184
Advisor:Henning Fernau
Document Type:Doctoral Thesis
Language:English
Date of completion:2018/01/30
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2017/09/25
Release Date:2018/01/30
Tag:(regulär: regulär) Array-Grammati; Graphen mit Eulerschen Pfaden; endliche Boustrophedon-Automaten; jumping endliche Automaten; zurückkehrende(RFA)
(general) boustrophedon (returning) finite automata; (general) jumping finite automata; (regular : regular) array grammars; Eulerian trails
GND Keyword:(regulär: regulär) Array-Grammati; Graphen mit Eulerschen Pfaden; endliche Boustrophedon-Automaten; jumping endliche Automaten; zurückkehrende(RFA)
Institutes:Fachbereich 4 / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik

$Rev: 13581 $