Provability, complexity, grammars

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 equi...

Descripción completa

Detalles Bibliográficos
Autores principales: Beklemishev, Lev, Pentus, Mati, Vereshchagin, Nikolai
Lenguaje:eng
Publicado: American Mathematical Society 1999
Materias:
Mathematical Physics and Mathematics
Acceso en línea:http://cds.cern.ch/record/2264266
_version_ 1780954346883645440
author Beklemishev, Lev
Pentus, Mati
Vereshchagin, Nikolai
author_facet Beklemishev, Lev
Pentus, Mati
Vereshchagin, Nikolai
author_sort Beklemishev, Lev
collection CERN
description 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.
id cern-2264266
institution Organización Europea para la Investigación Nuclear
language eng
publishDate 1999
publisher American Mathematical Society
record_format invenio
spelling cern-22642662021-04-21T19:13:16Zhttp://cds.cern.ch/record/2264266engBeklemishev, LevPentus, MatiVereshchagin, NikolaiProvability, complexity, grammarsMathematical Physics and MathematicsThe 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.American Mathematical Societyoai:cds.cern.ch:22642661999
spellingShingle Mathematical Physics and Mathematics
Beklemishev, Lev
Pentus, Mati
Vereshchagin, Nikolai
Provability, complexity, grammars
title Provability, complexity, grammars
title_full Provability, complexity, grammars
title_fullStr Provability, complexity, grammars
title_full_unstemmed Provability, complexity, grammars
title_short Provability, complexity, grammars
title_sort provability, complexity, grammars
topic Mathematical Physics and Mathematics
url http://cds.cern.ch/record/2264266
work_keys_str_mv AT beklemishevlev provabilitycomplexitygrammars
AT pentusmati provabilitycomplexitygrammars
AT vereshchaginnikolai provabilitycomplexitygrammars

Ejemplares similares