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 by Envoy
Pages: 183
Preface (by Sergei Artemov)
Classification of Propositional Provability Logics - Lev Beklemishev
Introduction
1. Preliminaries
2. Semantics for S, D, and A
3. Trace classification of provability logics
4. Prime А-models and their characteristic formulas
5. Provability logics containing D
6. Provability logics containing A
7. Main results
8. Examples, comments, and related results
References
Lambek Calculus and Formal Grammars - Mati Pentus
Introduction
1. Preliminaries
2. Free group interpretation
3. Thin sequents
4. Interpolation
5. Main theorem
6. Interpolation in fragments
7. Construction of a context-free grammar for a product-free Lambek grammar
8. Conjoinable types in the Lambek calculus
9. Multiplicative cyclic linear logic
References
Relativizability in Complexity Theory - Nikolai Vershchagin
Notation
1. Introduction
2. A uniform way to define complexity classes
3. General criteria
4. Relativizable inclusions between particular complexity classes
5. Turing reducibility between particular complexity classes
6. Complete languages in particular complexity classes
7. Perceptrons and oracle separation of AM П со-AM from PP
8. The universum method
9. Relations between complexity classes relativized with a random oracle
