Provability, Complexity, Grammars

Provability, Complexity, Grammars

by Lev Dmitrievich Beklemishev, Nikolai K. Vereshchagin, Mati R. Pentus, Nikolai Konstantinovich Vereshchagin
     
 

ISBN-10: 0821810782

ISBN-13: 9780821810781

Pub. Date: 05/04/1999

Publisher: American Mathematical Society

The book contains English translations of three outstanding dissertations in mathematical logic and complexity theory. L. Beklemishev proves that all provability logics must belong to one of the four previously known classes. The dissertation of M. Pentus proves the Chomsky conjecture about the equivalence of two approaches to formal languages: the Chomsky

…  See more details below

Overview

The book contains English translations of three outstanding dissertations in mathematical logic and complexity theory. L. Beklemishev proves that all provability logics must belong to one of the four previously known classes. The dissertation of M. Pentus proves the Chomsky conjecture about the equivalence of two approaches to formal languages: the Chomsky hierarchy and the Lambek calculus. The dissertation of N. Vereshchagin describes a general framework for criteria of reversability in complexity theory.

Product Details

ISBN-13:
9780821810781
Publisher:
American Mathematical Society
Publication date:
05/04/1999
Series:
American Mathematical Society Translations Series, #2
Pages:
172
Product dimensions:
7.09(w) x 10.63(h) x (d)

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >