KIT | KIT-Bibliothek | Impressum | Datenschutz

Sublinear-Time Cellular Automata and Connections to Complexity Theory

Casagrande Viapiana Modanese, Augusto 1
1 Kompetenzzentrum für angewandte Sicherheitstechnologie (KASTEL), Karlsruher Institut für Technologie (KIT)

Abstract:

Im Gebiet des verteilten Rechnens werden Modelle untersucht, in denen sich mehrere Berechnungseinheiten koordinieren, um zusammen ein gemeinsames Ziel zu erreichen, wobei sie aber nur über begrenzte Ressourcen verfügen — sei diese Zeit-, Platz- oder Kommunikationskapazitäten. Das Hauptuntersuchungsobjekt dieser Dissertation ist das wohl einfachste solche Modell überhaupt: (eindimensionale) Zellularautomaten. Unser Ziel ist es, einen besseren Überblick über die Fähigkeiten und Einschränkungen des Modells und ihrer Varianten zu erlangen in dem Fall, dass die gesamte Bearbeitungszeit deutlich kleiner als die Größe der Eingabe ist (d. ... mehr

Abstract (englisch):

Distributed computing studies models in which multiple computational units coordinate themselves to work towards some common goal while having only limited resources at their disposal—be it time, space, or communication. The main object of study of this dissertation is the arguably simplest such model there is: (one-dimensional) cellular automata. Our goal is to obtain a better picture of the capabilities and limitations of the model and its variants in the case where the overall processing time is significantly smaller than the size of the input (i.e., sublinear time). ... mehr


Volltext §
DOI: 10.5445/IR/1000153071
Veröffentlicht am 30.11.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Kompetenzzentrum für angewandte Sicherheitstechnologie (KASTEL)
Publikationstyp Hochschulschrift
Publikationsdatum 30.11.2022
Sprache Englisch
Identifikator KITopen-ID: 1000153071
Verlag Karlsruher Institut für Technologie (KIT)
Umfang ix, 160 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Kompetenzzentrum für angewandte Sicherheitstechnologie (KASTEL)
Prüfungsdatum 11.11.2022
Externe Relationen Siehe auch
Konferenz
Konferenz
Konferenz
Schlagwörter Cellular automata, computational complexity theory, distributed models, language recognition, sliding-window algorithms, sublinear time
Referent/Betreuer Müller-Quade, Jörn
Kutrib, Martin
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page