Die Another Day

Author Rudolf Fleischer



PDF
Thumbnail PDF

File

DagSemProc.06091.3.pdf
  • Filesize: 153 kB
  • 8 pages

Document Identifiers

Author Details

Rudolf Fleischer

Cite AsGet BibTex

Rudolf Fleischer. Die Another Day. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06091.3

Abstract

The hydra was a many-headed monster from Greek mythology that could grow one or two new heads when one of its heads got cut off. It was the second task of Hercules to kill this monster. In an abstract sense a hydra can be modeled by a tree where the leaves are the heads, and when a head is cut off some subtrees get duplicated. Different hydra species differ by the location of subtrees to be duplicated and by the number of new subtrees grown in each step. Using some deep mathematics, it had been shown that two classes of rather restricted hydra species must always die, independent of the order in which heads are cut off. In this paper we provide an elementary proof which actually gives a complete classification of all hydra species as immortal or doomed. Now, if Hercules had known this...
Keywords
  • Hydra
  • Koenig's Lemma
  • Peano Arithmetic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail