English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  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

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Vorobyov, Sergei1, 2, Author           
Affiliations:
1Computational Biology and Applied Algorithmics, MPI for Informatics, Max Planck Society, ou_40046              
2Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2010-03-121997
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : IEEE
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 519561
Other: Local-ID: C1256104005ECAFC-8AE1EBA7A40BED5BC1256457004B4935-Vorobyov97LICS97
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Warsaw, Poland
Start-/End Date: 2003-07-08 - 2003-07-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the Twelfth Annual IEEE Symposium on Logic in Computer Science (LICS-97)
Source Genre: Proceedings
 Creator(s):
Winskel, Glynn, Editor
Affiliations:
-
Publ. Info: New York, USA : IEEE
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 294 - 305 Identifier: ISBN: 0-8186-7925-5