Contains three doctoral dissertations in mathematical logic, mathematical linguistics, and complexity theory, translated from the Russian:
Lev Beklemishev - Classification of Propositional Provability Logics (PhD Thesis, 1992)
Mati Pentus - Lambek Calculus and Formal Grammars (PhD Thesis, 1996)
Nikolai Vershchagin - Relativizability in Complexity Theory (Habilit. Thesis, 1995)
Author(s): Lev Beklemishev, Mati Pentus, Nikolai Vereschagin
Series: American Mathematical Society translations, Series 2, Volume 192
Publisher: American Mathematical Society
Year: 1999
Language: English
Commentary: Scanned, DjVu'ed, OCR'ed, TOC by Envoy
Pages: 183
Cover ......Page 1
Table of contents ......Page 5
Preface ......Page 7
Introduction ......Page 9
1. Preliminaries ......Page 15
2. Semantics for S, D, and A ......Page 22
3. Trace classification of provability logics ......Page 29
4. Prime А-models and their characteristic formulas ......Page 38
5. Provability logics containing D ......Page 43
6. Provability logics containing A ......Page 46
7. Main results ......Page 51
8. Examples, comments, and related results ......Page 56
References ......Page 63
Introduction ......Page 65
1. Preliminaries ......Page 68
2. Free group interpretation ......Page 71
3. Thin sequents ......Page 73
4. Interpolation ......Page 74
5. Main theorem ......Page 77
6. Interpolation in fragments ......Page 81
7. Construction of a context-free grammar for a product-free Lambek grammar ......Page 87
8. Conjoinable types in the Lambek calculus ......Page 88
9. Multiplicative cyclic linear logic ......Page 89
References ......Page 94
1. Introduction ......Page 95
2. A uniform way to define complexity classes ......Page 97
3. General criteria ......Page 100
4. Relativizable inclusions between particular complexity classes ......Page 112
5. Turing reducibility between particular complexity classes ......Page 122
6. Complete languages in particular complexity classes ......Page 129
7. Perceptrons and oracle separation of AM П со-AM from PP ......Page 134
8. The universum method ......Page 140
9. Relations between complexity classes relativized with a random oracle ......Page 167
References ......Page 178
Selected titles in this series ......Page 181
