Reverse mathematics of some topics from algorithmic graph theory

• Autorzy: Peter G. Clote , Jeffry L. Hirst
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

reverse mathematics; proof theory; recursion theory; graph theory

Kategorie tematyczne

• 03F35: Second- and higher-order arithmetic and fragments
• 03D45: Theory of numerations, effectively presented structures

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 1998
• Tom: 157
• Numer: 1
• Strony: 1-13

Daty

wydano

1998

otrzymano

1997-01-19

poprawiono

1998-01-23

Twórcy

autor

Peter G. Clote

• Department of Computer Science, Boston College, Chestnut Hill, Massachusetts 02167, U.S.A.

autor

Jeffry L. Hirst

• Department of Mathematical Sciences, Appalachian State University, Boone, North Carolina 28608, U.S.A.

Bibliografia

• [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 $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.