Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  The Recognition of Deterministic CFL's in Small Time and Space

von Braunmühl, B., Cook, S., Mehlhorn, K., & Verbeek, R. (1983). The Recognition of Deterministic CFL's in Small Time and Space. Information and Control, 56, 34-51.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
von Braunmühl, Burchard, Autor
Cook, Stephen, Autor
Mehlhorn, Kurt1, Autor           
Verbeek, Rutger, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Let S(n) be a nice space bound such that log2 n S(n) n. Then every DCFL is recognized by a multitape Turing machine simultaneously in time O(n2/S(n)) and space O(S(n)), and this time bound is optimal. If the machine is allowed a random access input, then the time bound can be improved so that the time-space product is O(n1 + ).

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2008-03-061983
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 344634
Anderer: Local-ID: C1256428004B93B8-3ECB4E3035DE4038C12571C2005B6BB6-mehlhorn83e
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Information and Control
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 56 Artikelnummer: - Start- / Endseite: 34 - 51 Identifikator: -