1 Search Results for "Dufourd, Jean-Francois"

Document
DOI: 10.4230/LIPIcs.STACS.2008.1349
Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps

Authors: Jean-Francois Dufourd

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
This paper presents a formalized proof of a discrete form of the Jordan Curve Theorem. It is based on a hypermap model of planar subdivisions, formal specifications and proofs assisted by the Coq system. Fundamental properties are proven by structural or noetherian induction: Genus Theorem, Euler's Formula, constructive planarity criteria. A notion of ring of faces is inductively defined and a Jordan Curve Theorem is stated and proven for any planar hypermap.
Cite as

Jean-Francois Dufourd. Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 253-264, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dufourd:LIPIcs.STACS.2008.1349,
  author =	{Dufourd, Jean-Francois},
  title =	{{Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{253--264},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1349},
  URN =		{urn:nbn:de:0030-drops-13493},
  doi =		{10.4230/LIPIcs.STACS.2008.1349},
  annote =	{Keywords: Formal specifications, Computational topology, Computer-aided proofs, Coq, Planar subdivisions, Hypermaps, Jordan Curve Theorem}
}
  • Refine by Author
  • 1 Dufourd, Jean-Francois

  • Refine by Classification

  • Refine by Keyword
  • 1 Computational topology
  • 1 Computer-aided proofs
  • 1 Coq
  • 1 Formal specifications
  • 1 Hypermaps
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2008

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact