Jumping Computation

ISBN-13: 9780367620936 / Twarda / 2024 / 296 str.

Crezh Republic) Brno Zbynek (Brno University of Technology

Opis

This book is primarily a theoretically oriented treatment of jumping automata and grammars, covering all essential theoretical topics concerning them, including their power, properties, and transformations. 

Spis treści

Part I Introduction. 1 Mathematical Background. 1.1 Logic. 1.2 Sets and Languages. 1.3 Relations and Translations. 1.4 Graphs. 2 Automata and Grammars. 2.1 Language Models of Computation. 2.2 Automata. 2.3 Grammars. Part II Jumping Automata. 3 Jumping One-Head Automata. 3.1 Basic and Generalized Jumping Finite Automata. 3.2 One-way Jumping Finite Automata. 4 Jumping Multi-Head Automata. 4.1 Double-Jumping Finite Automata. 4.2 Multi-Parallel Jumping Finite Automata. 4.3 Jumping Watson–Crick Finite Automata. 4.4 Jumping 5′ → 3′ Watson–Crick Finite Automata. Part III Jumping Grammar. 5 Sequential Jumping Grammars. 5.1 Introduction. 5.2 Definitions and Examples. 5.3 Results. 6 Parallel Jumping Grammars. 6.1 Introduction. 6.2 Definitions. 6.3 Results. 7 Pure Jumping Grammars. 7.1 Introduction. 7.2 Definitions. 7.3 Results. Part IV Conclusion. 8 Other Models of Discontinuous Computation. 8.1 Deep Pushdown Automata. 8.2 Computation over unordered strings. 8.3 Permutation Grammars. 9 Remarks on Applications and Their Perspectives. 9.1 Jumping Automata Used as Language-Defining Devices. 9.2 Jumping Grammars Used as Models of DNA Computation. 9.3 Theoretically Oriented Applications. 10 Summarizing and Bibliographical Remarks. Bibliography. Index.

O autorze

Alexander Meduna (born 1957 in Olomouc, Czech Republic) is a theoretical computer scientist and expert on the theory of computation. He is a full professor of Computer Science at the Brno University of Technology. Formerly, he taught theoretical computer science at various American, Asian and European universities, including the University of Missouri, where he spent a decade teaching advanced topics of formal language theory and Kyoto Sangyo University, where he spent several months teaching these topics, too. Concerning the subject of this book, he is the author of over ninety papers and several books, listed at http://www.fit.vutbr.cz/~meduna/work.

Zbyněk Křivka is both a theoretically and pragmatically oriented computer scientist. Being a former PhD student of Alexander Meduna and, currently, his colleague at the Brno University of Technology, he has published several journal papers with strong focus on jumping models, and his PhD thesis, which also deals with formal languages, has been published as a book.