cl-banner

The Hydra Battle Revisited

Nachum Dershowitz and Georg Moser

Rewriting, Computation and Proof; Essays Dedicated to Jean-Pierre Jouannaud on the Occasion of his 60th Birthday, Lecture Notes in Computer Science 4600, pp. 1 – 27, 2007.

Abstract

Showing termination of the Battle of Hercules and Hydra is a challenge. We present the battle both as a rewrite system and as an arithmetic while program, provide proofs of their termination, and recall why their termination cannot be proved within Peano arithmetic.

 

  PDF |    doi:10.1007/978-3-540-73147-4_1  |  © Springer

BibTeX 

@inproceedings{DM-JPJ60,
author = "Nachum Dershowitz and Georg Moser",
title = "The Hydra Battle Revisited",
booktitle = "Rewriting, Computation and Proof; Essays Dedicated to
Jean-Pierre Jouannaud on the Occasion of his 60th Birthday",
series = "Lecture Notes in Computer Science",
volume = 4600,
pages = "1--27",
publisher = "Springer-Verlag",
year = 2007
}
Nach oben scrollen