Download PDF - Reverse mathematics of some topics from algorithmic graph theoryAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Reverse mathematics of some topics from algorithmic graph theory

Authors 1, 2

Affiliations

  1. Department of Computer Science, Boston College, Chestnut Hill, Massachusetts 02167, U.S.A.
  2. Department of Mathematical Sciences, Appalachian State University, Boone, North Carolina 28608, U.S.A.

Abstract

This paper analyzes the proof-theoretic strength of an infinite version of several theorems from algorithmic graph theory. In particular, theorems on reachability matrices, shortest path matrices, topological sorting, and minimal spanning trees are considered.

Keywords

ENG
recursion theory, reverse mathematics, proof theory, graph theory

Bibliography

  1. J. Hirst, Combinatorics in subsystems of second order arithmetic, Ph.D. Thesis, The Pennsylvania State University, 1987.
  2. J. Hirst, Connected components of graphs and reverse mathematics, Arch. Math. Logic 31 (1992), 183-192.
  3. S. Simpson, Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?, J. Symbolic Logic 49 (1984), 783-802.
  4. S. Simpson, Subsystems of Z2, in: Proof Theory, G. Takeuti (ed.), North-Holland, Amsterdam, New York, 1985, 434-448.
  5. R. Soare, Recursively Enumerable Sets and Degrees, Springer, Berlin, 1987.
Fundamenta Mathematicae
1998/157/1
Export to PBN, Opens in new tab
Pages:
1-13
Main language of publication
English
Received
1997-01-19
Accepted
1998-01-23
Published
1998
Exact and natural sciences