PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1998 | 157 | 1 | 1-13
Tytuł artykułu

Reverse mathematics of some topics from algorithmic graph theory

Treść / Zawartość
Warianty tytułu
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.
Rocznik
Tom
157
Numer
1
Strony
1-13
Opis fizyczny
Daty
wydano
1998
otrzymano
1997-01-19
poprawiono
1998-01-23
Twórcy
  • Department of Computer Science, Boston College, Chestnut Hill, Massachusetts 02167, U.S.A., clote@cs.bc.edu
  • Department of Mathematical Sciences, Appalachian State University, Boone, North Carolina 28608, U.S.A., jlh@math.appstate.edu
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-fmv157i1p1bwm
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.