Reachability over word rewriting systems [Elektronische Ressource] / vorgelegt von Jan-Henrik Altenbernd

Reachability overWord Rewriting SystemsVon der Fakultät für Mathematik, Informatik undNaturwissenschaften der RWTH Aachen University zurErlangung des akademischen Grades eines Doktors derNaturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-InformatikerJan-Henrik Altenberndaus Hannover, NiedersachsenBerichter: Univ.-Prof. Dr. Wolfgang ThomasDr.habil. Didier CaucalTag der mündlichen Prüfung: 11. Dezember 2009Diese Dissertation ist auf den Internetseitender Hochschulbibliothek online verfügbar.AbstractWord rewriting systems have been studied over the last century under sev-eral aspects. In the beginning, they were considered as a framework for therepresentation of computation processes and as a tool for generating formallanguages. In more recent years, they have also been investigated as a mech-anism to represent infinite graphs by a finite formalism. This thesis has itsmain focus in the latter domain.In the first part of the thesis, we investigate mixed prefix/suffix rewriting(MPSR) systems, which combine prefix and suffix rewriting in a nondeter-ministic way. We study central algorithmic properties of the graphs that canbe generated by such systems, with an emphasis on the reachability problem(as a master problem in model-checking), and we determine the connectionbetweentheclassesofsuchgraphsandotherwell-studiedgraphclasses, suchas the classes of prefix recognizable and of automatic graphs.