American Mathematical Society TranslationsSeries 2 1999; 172 pp; hardcover Volume: 192 ISBN10: 0821810782 ISBN13: 9780821810781 List Price: US$103 Member Price: US$82.40 Order Code: TRANS2/192
 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. Readership Researchers and graduate student working in mathematical logic and complexity theory; computer scientists. Reviews "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
