de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  New lower bounds for the expressiveness and the higher-order Matching problem in the simply typed lambda calculus

Vorobyov, S.(1999). New lower bounds for the expressiveness and the higher-order Matching problem in the simply typed lambda calculus (MPI-I-1999-3-001). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: http://hdl.handle.net/11858/00-001M-0000-0014-6F4C-1 Versions-Permalink: http://hdl.handle.net/11858/00-001M-0000-0014-7A67-0
Genre: Bericht

Dateien

einblenden: Dateien
ausblenden: Dateien
:
1999-3-001 (beliebiger Volltext), 11KB
Beschreibung:
-
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
text/html / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Vorobyov, Sergei1, Autor              
Affiliations:
1Reaktive und Hybride Systeme, escidoc:40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 1. We analyze expressiveness of the simply typed lambda calculus (STLC) over a single base type, and show how k-DEXPTIME computations can be simulated in the order k+6 STLC. This gives a double order improvement over the lower bound of [Hillebrand \& Kanellakis LICS'96], reducing k-DEXPTIME to the order 2k+3 STLC. 2. We show that k-DEXPTIME is linearly reducible to the higher-order matching problem (in STLC) of order k+7. Thus, order k+7 matching requires (lower bound) k-level exponential time. This refines over the best previously known lower bound (a stack of twos growing almost linearly, O(n / log(n)) in the length of matched terms) from [Vorobyov LICS'97], which holds in assumption that orders of types are UNBOUNDED, but does not imply any nontrivial lower bounds when the order of variables is FIXED. 3. These results are based on the new simplified and streamlined proof of Statman's famous theorem. Previous proofs in [Statman TCS'79, Mairson TCS'92, Vorobyov LICS'97] were based on a two-step reduction: proving a non-elementary lower bound for Henkin's higher-order theory Omega of propositional types and then encoding it in the STLC. We give a direct generic reduction from k-DEXPTIME to the STLC, which is conceptually much simpler, and gives stronger and more informative lower bounds for the fixed-order STLC, in contrast with the previous proofs.

Details

einblenden:
ausblenden:
Sprache(n): eng - Englisch
 Datum: 1999
 Publikationsstatus: Im Druck publiziert
 Seiten: 20 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1999-3-001
Reportnr.: MPI-I-1999-3-001
BibTex Citekey: Vorobyov99
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -