2 Search Results for "Aristiz�bal, Andr�s"

Document
DOI: 10.4230/LIPIcs.FSCD.2016.9
Environmental Bisimulations for Delimited-Control Operators with Dynamic Prompt Generation

Authors: Andrés Aristizábal, Dariusz Biernacki, Sergueï Lenglet, and Piotr Polesiuk

Published in: LIPIcs, Volume 52, 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)

Abstract
We present sound and complete environmental bisimilarities for a variant of Dybvig et al.'s calculus of multi-prompted delimited-control operators with dynamic prompt generation. The reasoning principles that we obtain generalize and advance the existing techniques for establishing program equivalence in calculi with single-prompted delimited control. The basic theory that we develop is presented using Madiot et al.'s framework that allows for smooth integration and composition of up-to techniques facilitating bisimulation proofs. We also generalize the framework in order to express environmental bisimulations that support equivalence proofs of evaluation contexts representing continuations. This change leads to a novel and powerful up-to technique enhancing bisimulation proofs in the presence of control operators.
Cite as

Andrés Aristizábal, Dariusz Biernacki, Sergueï Lenglet, and Piotr Polesiuk. Environmental Bisimulations for Delimited-Control Operators with Dynamic Prompt Generation. In 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 52, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aristizabal_et_al:LIPIcs.FSCD.2016.9,
  author =	{Aristiz\'{a}bal, Andr\'{e}s and Biernacki, Dariusz and Lenglet, Sergue\"{i} and Polesiuk, Piotr},
  title =	{{Environmental Bisimulations for Delimited-Control Operators with Dynamic Prompt Generation}},
  booktitle =	{1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-010-1},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{52},
  editor =	{Kesner, Delia and Pientka, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2016.9},
  URN =		{urn:nbn:de:0030-drops-59756},
  doi =		{10.4230/LIPIcs.FSCD.2016.9},
  annote =	{Keywords: delimited continuation, dynamic prompt generation, contextual equivalence, environmental bisimulation, up-to technique}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.5
Coloring Points with Respect to Squares

Authors: Eyal Ackerman, Balázs Keszegh, and Máté Vizer

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We consider the problem of 2-coloring geometric hypergraphs. Specifically, we show that there is a constant m such that any finite set S of points in the plane can be 2-colored such that every axis-parallel square that contains at least m points from S contains points of both colors. Our proof is constructive, that is, it provides a polynomial-time algorithm for obtaining such a 2-coloring. By affine transformations this result immediately applies also when considering homothets of a fixed parallelogram.
Cite as

Eyal Ackerman, Balázs Keszegh, and Máté Vizer. Coloring Points with Respect to Squares. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2016.5,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs and Vizer, M\'{a}t\'{e}},
  title =	{{Coloring Points with Respect to Squares}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.5},
  URN =		{urn:nbn:de:0030-drops-58972},
  doi =		{10.4230/LIPIcs.SoCG.2016.5},
  annote =	{Keywords: Geometric hypergraph coloring, Polychromatic coloring, Homothets, Cover-decomposability}
}
  • Refine by Author
  • 1 Ackerman, Eyal
  • 1 Aristizábal, Andrés
  • 1 Biernacki, Dariusz
  • 1 Keszegh, Balázs
  • 1 Lenglet, Sergueï
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Cover-decomposability
  • 1 Geometric hypergraph coloring
  • 1 Homothets
  • 1 Polychromatic coloring
  • 1 contextual equivalence
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2016

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