Lev Gordeev ; Andreas Weiermann - Phase transitions in Proof Theory

dmtcs:2771 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2771
Phase transitions in Proof Theory

Authors: Lev Gordeev 1; Andreas Weiermann 2

  • 1 Eberhard Karls Universität Tübingen = Eberhard Karls University of Tuebingen
  • 2 Universiteit Gent = Ghent University

Using standard methods of analytic combinatorics we elaborate critical points (thresholds) of phase transitions from provability to unprovability of arithmetical well-partial-ordering assertions in several familiar theories occurring in the reverse mathematics program.

https://doi.org/10.46298/dmtcs.2771
Source: HAL:hal-01185569v1
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: phase transitions,proof theory,reverse mathematics,asymptotics,analytic combinatorics,well partial orderings,Higman-Kruskal-Friedman theorems,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1002/malq.200610022
  • 10.1002/malq.200610022
Phase transition thresholds for some Friedman‐style independence results

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 166 times.
This article's PDF has been downloaded 458 times.