New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

Provability, Complexity, Grammars
Lev Beklemishev, Steklov Institute of Mathematics, Moscow, Russia, and Mati Pentus and Nikolai Vereshchagin, Moscow State University, Russia
 SEARCH THIS BOOK:
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$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.

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

• L. D. Beklemishev -- Classification of propositional provability logics
• M. Pentus -- Lambek calculus and formal grammars
• N. K. Vereshchagin -- Relativizability in complexity theory