# Reverse mathematics of some topics from algorithmic graph theory

Fundamenta Mathematicae (1998)

- Volume: 157, Issue: 1, page 1-13
- ISSN: 0016-2736

## Access Full Article

top## Abstract

top## How to cite

topClote, Peter, and Hirst, Jeffry. "Reverse mathematics of some topics from algorithmic graph theory." Fundamenta Mathematicae 157.1 (1998): 1-13. <http://eudml.org/doc/212275>.

@article{Clote1998,

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.},

author = {Clote, Peter, Hirst, Jeffry},

journal = {Fundamenta Mathematicae},

keywords = {reverse mathematics; proof theory; recursion theory; graph theory; reachability matrices; topological sorting; spanning trees},

language = {eng},

number = {1},

pages = {1-13},

title = {Reverse mathematics of some topics from algorithmic graph theory},

url = {http://eudml.org/doc/212275},

volume = {157},

year = {1998},

}

TY - JOUR

AU - Clote, Peter

AU - Hirst, Jeffry

TI - Reverse mathematics of some topics from algorithmic graph theory

JO - Fundamenta Mathematicae

PY - 1998

VL - 157

IS - 1

SP - 1

EP - 13

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

LA - eng

KW - reverse mathematics; proof theory; recursion theory; graph theory; reachability matrices; topological sorting; spanning trees

UR - http://eudml.org/doc/212275

ER -

## References

top- [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. Zbl0725.03039
- [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. Zbl0584.03039
- [4] S. Simpson, Subsystems of ${Z}_{2}$, 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.