Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Fleischer, Rudolf License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-7652

Die Another Day



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

BibTeX - Entry

  author =	{Fleischer, Rudolf},
  title =	{{Die Another Day}},
  booktitle =	{Data Structures},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-7652},
  doi =		{10.4230/DagSemProc.06091.3},
  annote =	{Keywords: Hydra, Koenig's Lemma, Peano Arithmetic}

Keywords: Hydra, Koenig's Lemma, Peano Arithmetic
Seminar: 06091 - Data Structures
Issue date: 2006
Date of publication: 30.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI