Verification of Automata with Storage Mechanisms
Seiten
2022
TU Ilmenau Universitätsbibliothek (Verlag)
978-3-86360-265-9 (ISBN)
TU Ilmenau Universitätsbibliothek (Verlag)
978-3-86360-265-9 (ISBN)
An important question in computer science is to ask, whether a given system conforms to a specification. Often this question is equivalent to ask whether a finite automaton with certain memory like a stack or queue can reach some given state. In this thesis we focus this reachability problem of automata having one or more lossy or reliable stacks or queues as their memory. Unfortunately, the reachability problem is undecidable or of high complexity in most of these cases. We circumvent this by several approximation methods. So we extend the exploration algorithm by Boigelot and Godefroid under-approximating the reachability problem of queue automata. We also study some automata having multiple stacks with a restricted behavior. These “asynchronous pushdown systems” have an efficiently decidable reachability problem. To show our results we first have to gain knowledge of several algebraic properties of the so-called transformation monoid of the studied storage mechanisms.
| Erscheinungsdatum | 09.12.2022 |
|---|---|
| Verlagsort | Ilmenau |
| Sprache | englisch |
| Maße | 170 x 240 mm |
| Themenwelt | Mathematik / Informatik ► Informatik ► Theorie / Studium |
| Schlagworte | Algorithmus • Automat <Automatentheorie> • Erreichbarkeit • Monoid |
| ISBN-10 | 3-86360-265-X / 386360265X |
| ISBN-13 | 978-3-86360-265-9 / 9783863602659 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Grundlagen – Anwendungen – Perspektiven
Buch | Softcover (2022)
Springer Vieweg (Verlag)
CHF 48,95
Eine Einführung in die Systemtheorie
Buch | Softcover (2022)
UTB (Verlag)
CHF 34,95
