Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  The `hardest´ natural decidable theory

Vorobyov, S. (1997). The `hardest´ natural decidable theory. In G. Winskel (Ed.), Proceedings of the Twelfth Annual IEEE Symposium on Logic in Computer Science (LICS-97) (pp. 294-305). New York, USA: IEEE.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3A20-F Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3A21-D
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Vorobyov, Sergei1, 2, Autor           
Affiliations:
1Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society, ou_40046              
2Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Since mid-seventies it was an open problem as to whether there exist natural decidable theories requiring time (lower bound) exceeding any linearly growing towers of 2s to decide. It was conjectured that all natural decidable theories can be decided (upper bound) within time bounded by a tower of 2s growing linearly with the length of input. Although it happens to be true for the majority of non-elementary theories (Rabin's S2S, theory of term algebras, extended regular expressions, etc), the conjecture fails. We demonstrate that a modest fragment of L.Henkin's theory of propositional types (1963) has the tower of 2s growing *exponentially* with the length of input as a lower bound. This new unprecedentedly high lower bound allows us to considerably improve the known lower bounds and to settle the new ones for other theories.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121997
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: New York, USA : IEEE
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 519561
Anderer: Local-ID: C1256104005ECAFC-8AE1EBA7A40BED5BC1256457004B4935-Vorobyov97LICS97
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Warsaw, Poland
Start-/Enddatum: 2003-07-08 - 2003-07-12

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the Twelfth Annual IEEE Symposium on Logic in Computer Science (LICS-97)
Genre der Quelle: Konferenzband
 Urheber:
Winskel, Glynn, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: New York, USA : IEEE
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 294 - 305 Identifikator: ISBN: 0-8186-7925-5