Provability, complexity, grammars

著者

書誌事項

Provability, complexity, grammars

Lev Beklemishev, Mati Pentus, Nikolai Vereshchagin

（American Mathematical Society translations, ser. 2, v. 192）

American Mathematical Society, c1999

  • : hbk. : alk. paper

大学図書館所蔵 件 / 全52件

この図書・雑誌をさがす

注記

Contains three doctoral dissertations in mathematical logic, mathematical linguistics, and complexity theory, translated from the Russian

Includes bibliographical references

内容説明・目次

内容説明

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.

目次

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.

「Nielsen BookData」 より

関連文献： 1件中  1-1を表示

  • American Mathematical Society translations

    American Mathematical Society 1955-

    Ser. 2, v. 1 , Ser. 2, v. 2 , Ser. 2, v. 3 , Ser. 2, v. 4 , Ser. 2, v. 5 , Ser. 2, v. 6 , Ser. 2, v. 7 , Ser. 2, v. 8 , Ser. 2, v. 9 , Ser. 2, v. 10 , Ser. 2, v. 11 , Ser. 2, v. 12 , Ser. 2, v. 13 , Ser. 2, v. 14 , Ser. 2, v. 15 , Ser. 2, v. 16 , Ser. 2, v. 17 , Ser. 2, v. 18

    所蔵館95館

詳細情報

ページトップへ