Provability, Complexity, Grammars

by Lev D. Beklemishev, Nikolai Konstantinovich Vereshchagin

Contains English translations of three outstanding dissertations by Russian mathematicians in mathematical logic, mathematical linguistics, and complexity theory. Areas discussed include classification of propositional provability logics, Lambek calculus and formal grammars, the Chomsky hierarchy and the Lambek categorical grammars, a general framework for formulating the relativizability criteria and for analyzing their limits, and relativizable inclusions for some of the known complexity classes. No index. Annotation c. Book News, Inc., Portland, OR (booknews.com)

172 pages, Hardcover

First published April 1, 1999