Postdoctoral Qualification HABIL-2003-02

BibliographyPetersen, Holger: Gegenseitige Simulation von Datenstrukturen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Postdoctoral Qualification (2003).
114 pages, german.
CR-SchemaF.1.1 (Models of Computation)
F.1.3 (Complexity Measures and Classes)
F.4.1 (Mathematical Logic)
KeywordsKomplexitätstheorie; Berechnungskomplexität
Abstract

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.

Full text and
other links
PDF (728538 Bytes)
Opus Uni Stuttgart
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateJuly 22, 2005
   Publ. Computer Science