AMS Bookstore LOGO amslogo
Return to List  Item: 1 of 1   
Provability, Complexity, Grammars
Lev Beklemishev, Steklov Institute of Mathematics, Moscow, Russia, and Mati Pentus and Nikolai Vereshchagin, Moscow State University, Russia

American Mathematical Society Translations--Series 2
1999; 172 pp; hardcover
Volume: 192
ISBN-10: 0-8218-1078-2
ISBN-13: 978-0-8218-1078-1
List Price: US$109
Member Price: US$87.20
Order Code: TRANS2/192
[Add Item]

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.


Researchers and graduate student working in mathematical logic and complexity theory; computer scientists.


"Contains English translations of three outstanding dissertations by Russian mathematicians in mathematical logic, mathematical linguistics, and complexity theory."

-- SciTech Book News

Table of Contents

  • L. D. Beklemishev -- Classification of propositional provability logics
  • M. Pentus -- Lambek calculus and formal grammars
  • N. K. Vereshchagin -- Relativizability in complexity theory
Powered by MathJax
Return to List  Item: 1 of 1   

  AMS Home | Comments:
© Copyright 2014, American Mathematical Society
Privacy Statement

AMS Social

AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia