Habilitation HABIL-2003-02

Bibliograph.
Daten
Petersen, Holger: Gegenseitige Simulation von Datenstrukturen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Habilitation (2003).
114 Seiten, deutsch.
CR-Klassif.F.1.1 (Models of Computation)
F.1.3 (Complexity Measures and Classes)
F.4.1 (Mathematical Logic)
KeywordsKomplexitätstheorie; Berechnungskomplexität
Kurzfassung

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.

Volltext und
andere Links
PDF (728538 Bytes)
Opus Uni Stuttgart
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum22. Juli 2005
   Publ. Informatik