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.
Reihe
Sprache
Verlagsort
Zielgruppe
Für höhere Schule und Studium
Für Beruf und Forschung
Gewicht
ISBN-13
978-0-8218-1078-1 (9780821810781)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Klassifikation
Classification of propositional provability logics by L. D. Beklemishev Lambek calculus and formal grammars by M. Pentus Relativizability in complexity theory by N. K. Vereshchagin.
