ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twelfth Annual IEEE Symposium on

Logic in Computer Science (LICS 1997)

Paper: The "Hardest" Natural Decidable Theory (at LICS 1997)

Authors: Sergei G. Vorobyov


We prove that any decision procedure for a modest fragment of L. Henkin's theory of pure propositional types requires time exceeding a tower of 2's of height exponential in the length of input. Until now the highest known lower bounds for natural decidable theories were at most linearly high towers of 2's and since mid-seventies it was an open problem whether natural decidable theories requiring more than that exist . We give the affirmative answer. As an application of this today's strongest lower bound we improve known and settle new lower bounds for several problems in the simply typed lambda calculus.


    author = 	 {Sergei G. Vorobyov},
    title = 	 {The "Hardest" Natural Decidable Theory},
    booktitle =  {Proceedings of the Twelfth Annual IEEE Symposium on Logic in Computer Science (LICS 1997)},
    year =	 {1997},
    month =	 {June}, 
    pages =      {294--305},
    location =   {Warsaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}

Last modified: 2022-10-3113:49
Sam Staton