Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26447
Titel: Four results on the complexity of VLSI computations
Verfasser: Lengauer, Thomas
Mehlhorn, Kurt
Sprache: Englisch
Erscheinungsjahr: 1983
Freie Schlagwörter: complexity theory
lower bounds
VLSI models
switching energy
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: We present four results on the complexity of VLSI computations: a) We further justify the Boolean circuit model [Vu, Sa, LS] by showing that it is able to model multi-directional VLSI devices (e.g. pass transistors, pre-charged bus drivers). b) We prove a general cutting theorem for compact regions in R^{d} (d\geq2) that allows us to drop the convexity assumption in lower bound proofs based on the crossing sequence argument. c) We exhibit an \Omega(n^{1/3}) asymptotically tight lower bound on the area of strongly where-oblivious chips for transitive functions. d) We prove a lower bound on the switching energy needed for computing transitive functions.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-51384
hdl:20.500.11880/26503
http://dx.doi.org/10.22028/D291-26447
Schriftenreihe: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Band: 1983/01
SciDok-Publikation: 3-Apr-2013
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1983_01.pdf12,69 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.