Provability, Complexity, Grammars
( American Mathematical Society Translations - Series 2 )
Publication series ：American Mathematical Society Translations - Series 2
Author： Lev Beklemishev;Mati Pentus;Nikolai Vereshchagin
Publisher： American Mathematical Society
Publication year： 1999
E-ISBN: 9781470434038
P-ISBN(Hardback): 9780821810781
Subject： O141 (mathematical logic) symbolic logic.
Keyword： 暂无分类
Language： ENG
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Provability, Complexity, Grammars
Description
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.
Chapter