**American Mathematical Society Translations - Series 2**

1999;
172 pp;
Hardcover

MSC: Primary 68; 03;

Print ISBN: 978-0-8218-1078-1

Product Code: TRANS2/192

List Price: $109.00

Individual Member Price: $87.20

**Electronic ISBN: 978-1-4704-3403-8
Product Code: TRANS2/192.E**

List Price: $109.00

Individual Member Price: $87.20

# Provability, Complexity, Grammars

Share this page
*Lev Beklemishev; Mati Pentus; Nikolai Vereshchagin*

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.

#### Table of Contents

# Table of Contents

## Provability, Complexity, Grammars

#### 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