05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Filters

2002 - 200932020 - 20211

Settings

Institute: search.filters.UBSInstitut.Institut für Formale Methoden der InformatikPublication Type: search.filters.UBSTyp.Habilitation

Search Results

Now showing 1 - 4 of 4
  • Thumbnail Image
    ItemOpen Access
    Computational and logical aspects of infinite monoids
    (2003) Lohrey, Markus; Diekert, Volker (Prof. Dr.)
    The present work contains a treatise of several computational and logical aspects of infinite monoids. The first chapter is devoted to the word problem for finitely generated monoids. In particular, the relationship between the the computational complexity of the word problem and the syntactical properties of monoid presentations is investigated. The second chapter studies Cayley-graphs of finitely generated monoids under a logical point of view. Cayley-graphs of groups play an important role in combinatorial group theory. We will study first-order and monadic second-order theories of Cayley-graphs for both groups and monoids. The third chapter deals with word equations over monoids. Using the graph product operation, which generalizes both the free and the direct product, we generalize the seminal decidability results of Makanin on free monoids and groups to larger classes of monoids.
  • Thumbnail Image
    ItemOpen Access
    Analysis and verification of systems with dynamically evolving structure
    (2004) König, Barbara; Esparza, Javier (Prof. Dr.)
    This thesis is concerned with verification and analysis techniques for software systems characterized by dynamically evolving structure, such as dynamic creation and deletion of objects, mobility and variable topology. Examples for such systems are pointer structures, object-based systems and communication protocols in which the number of participants is not constant. The approach taken here is based on graph transformation systems, an intuitive and---at the same time---powerful formalism for the modelling of distributed and mobile systems. So far there exists comparatively little research concerning the verification of graph rewriting. We will---in the first part of this thesis---introduce graph transformations and give an overview of existing analysis and verification methods, with a focus on the verification of systems with dynamically evolving structure. Then we will describe three original lines of research: behavioural equivalences, type systems and approximation by Petri nets, all of them concerned with the analysis of graph transformation systems. The second part consists of eight refereed research papers treating the previously introduced analysis and verification techniques in depth.
  • Thumbnail Image
    ItemOpen Access
    Circuit complexity of group theoretic problems
    (2021) Weiß, Armin; Diekert, Volker (Prof. Dr. rer. nat.)
    In dieser kumulativen Habilitationsschrift werden sechs Arbeiten zum Thema "Schaltkreiskomplexität von Gruppentheoretischen Problemen" zusammengefasst. An vorderster Stelle steht hierbei das Wortproblem: Gegeben ein Wort über den Erzeugern einer Gruppe, ist die Frage, ob das Wort das Einselement der Gruppe darstellt. Daneben werden noch weitere Probleme, wie das Konjugationsproblem, das Power-Wortproblem (wie das Wortproblem, aber die Eingabe wird in komprimierter Form gegeben) und das Lösen von Gleichungen betrachtet. Die meisten der hier zusammengefassten Arbeiten betrachten die genannten Probleme für spezielle Klassen von Gruppen und klassifizieren deren Komplexität mit Methoden der Schaltkreiskomplexität. Eine Ausnahme bildet die letzte Arbeit zum Thema Gleichungen: hier liegt der Zusammenhang zur Schaltkreiskomplexität darin, dass sich das Erfüllbarkeitsproblem für Gleichungen in endlichen auslösbaren Gruppen ähnlich verhält wie das Erfüllbarkeitsproblem für CC^0 Schaltkreise.
  • Thumbnail Image
    ItemOpen Access
    Gegenseitige Simulation von Datenstrukturen
    (2002) Petersen, Holger; Diekert, Volker (Prof. Dr.)
    Die vorliegende Arbeit stellt einige Ergebnisse zusammen, welche das Verhältnis verschiedener Berechenbarkeitsmodelle zueinander betreffen. Hierbei wird einerseits der Zusatzaufwand (im Bezug auf die Zeitkomplexität) bei der gegenseitigen Simulation solcher Modelle untersucht. Andererseits werden untere Schranken bewiesen oder auch die Unmöglichkeit einer Simulation. Diese Untersuchungen lassen sich einem Bereich zuordnen, der als konkrete Komplexitätstheorie bezeichnet wird.