Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 DetailsÜbersicht
  Metastability-Containing Circuits, Parallel Distance Problems, and Terrain Guarding

Friedrichs, S. (2017). Metastability-Containing Circuits, Parallel Distance Problems, and Terrain Guarding. PhD Thesis, Unversität des Saarlandes, Saarbrücken.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-002D-E9A7-B Versions-Permalink: https://hdl.handle.net/21.11116/0000-0001-8A56-3
Genre: Hochschulschrift

Externe Referenzen

einblenden:
ausblenden:
externe Referenz:
http://scidok.sulb.uni-saarland.de/volltexte/2017/6966/ (beliebiger Volltext)
Beschreibung:
-
OA-Status:
Grün
externe Referenz:
http://scidok.sulb.uni-saarland.de/doku/lic_ohne_pod.php?la=de (Verlagsvertrag)
Beschreibung:
-
OA-Status:
Keine Angabe

Urheber

einblenden:
ausblenden:
 Urheber:
Friedrichs, Stephan1, 2, Autor           
Lenzen, Christoph1, Ratgeber           
Mehlhorn, Kurt1, Gutachter           
Ghaffari, Mohsen3, Gutachter
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551              
3External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We study three problems. The first is the phenomenon of metastability in digital circuits. This is a state of bistable storage elements, such as registers, that is neither logical 0 nor 1 and breaks the abstraction of Boolean logic. We propose a time- and value-discrete model for metastability in digital circuits and show that it reflects relevant physical properties. Further, we propose the fundamentally new approach of using logical masking to perform meaningful computations despite the presence of metastable upsets and analyze what functions can be computed in our model. Additionally, we show that circuits with masking registers grow computationally more powerful with each available clock cycle. The second topic are parallel algorithms, based on an algebraic abstraction of the Moore-Bellman-Ford algorithm, for solving various distance problems. Our focus are distance approximations that obey the triangle inequality while at the same time achieving polylogarithmic depth and low work. Finally, we study the continuous Terrain Guarding Problem. We show that it has a rational discretization with a quadratic number of guard candidates, establish its membership in NP and the existence of a PTAS, and present an efficient implementation of a solver.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2017-09-112017-09-142017
 Publikationsstatus: Erschienen
 Seiten: x, 226 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Unversität des Saarlandes
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Friedrichsphd2017
URN: urn:nbn:de:bsz:291-scidok-69660
 Art des Abschluß: Doktorarbeit

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: