3 Search Results for "Van Wyk, Eric"

Document
DOI: 10.4230/LIPIcs.SoCG.2025.18
Finding a Shortest Curve That Separates Few Objects from Many

Authors: Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that encloses a set of k required objects in the plane while paying a penalty for enclosing unwanted objects. The input is a set of interior-disjoint simple polygons in the plane, where k of the polygons are required to be enclosed and the remaining optional polygons have non-negative penalties. The goal is to find a closed curve that is disjoint from the polygon interiors and encloses the k required polygons, while minimizing the length of the curve plus the penalties of the enclosed optional polygons. If the penalties are high, the output is a shortest curve that separates the required polygons from the others. The problem is NP-hard if k is not fixed, even in very special cases. The runtime of our algorithm is O(3^k n³), where n is the number of vertices of the input polygons. We extend the result to a graph version of the problem where the input is a connected plane graph with positive edge weights. There are k required faces; the remaining faces are optional and have non-negative penalties. The goal is to find a closed walk in the graph that encloses the k required faces, while minimizing the weight of the walk plus the penalties of the enclosed optional faces. We also consider an inverted version of the problem where the required objects must lie outside the curve. Our algorithms solve some other well-studied problems, such as geometric knapsack.
Cite as

Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote. Finding a Shortest Curve That Separates Few Objects from Many. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SoCG.2025.18,
  author =	{Biedl, Therese and Colin de Verdi\`{e}re, \'{E}ric and Frati, Fabrizio and Lubiw, Anna and Rote, G\"{u}nter},
  title =	{{Finding a Shortest Curve That Separates Few Objects from Many}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.18},
  URN =		{urn:nbn:de:0030-drops-231701},
  doi =		{10.4230/LIPIcs.SoCG.2025.18},
  annote =	{Keywords: Enclosure, curve, separation, weakly simple polygon, Euler tour}
}
Document
DOI: 10.4230/OASIcs.EVCS.2023.30
Context in Parsing: Techniques and Applications

Authors: Eric Van Wyk

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
This paper discusses two approaches to parsing: Eelco Visser’s scannerless generalized LR parsing and our context-aware scanning paired with deterministic LR parsing. We compare the underlying techniques, specifically how parser context is used to disambiguate lexical syntax, and their use in the context of language evolution and composition applications. We also reflect on the many discussions shared with Eelco on these topics, and on our shared realization that our different assumptions about the contexts in which our approaches were used drove and justified the technical decisions made in each.
Cite as

Eric Van Wyk. Context in Parsing: Techniques and Applications. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 30:1-30:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanwyk:OASIcs.EVCS.2023.30,
  author =	{Van Wyk, Eric},
  title =	{{Context in Parsing: Techniques and Applications}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{30:1--30:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.30},
  URN =		{urn:nbn:de:0030-drops-178001},
  doi =		{10.4230/OASIcs.EVCS.2023.30},
  annote =	{Keywords: Parsing, Generalized LR Parsing, Context-aware Scanning}
}
Document
DOI: 10.4230/DagRep.7.8.45
SLEBOK: The Software Language Engineering Body of Knowledge (Dagstuhl Seminar 17342)

Authors: Benoît Combemale, Ralf Lämmel, and Eric Van Wyk

Published in: Dagstuhl Reports, Volume 7, Issue 8 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17342 "SLEBOK: The Software Language Engineering Body of Knowledge". Software Language Engineering (SLE) has emerged as a scientific field, with a strong motivation to connect and integrate different research disciplines such as compiler construction, reverse engineering, software transformation, model-driven engineering, and ontologies. This seminar supported further integration of said communities with the clear objective of assembling a Body of Knowledge on SLE (SLEBoK). The BoK features artifacts, definitions, methods, techniques, best practices, open challenges, case studies, teaching material, and other components that will afterwards help students, researchers, teachers, and practitioners to learn from, to better leverage, to better contribute to, and to better disseminate the intellectual contributions and practical tools and techniques coming from the SLE field.
Cite as

Benoît Combemale, Ralf Lämmel, and Eric Van Wyk. SLEBOK: The Software Language Engineering Body of Knowledge (Dagstuhl Seminar 17342). In Dagstuhl Reports, Volume 7, Issue 8, pp. 45-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{combemale_et_al:DagRep.7.8.45,
  author =	{Combemale, Beno\^{i}t and L\"{a}mmel, Ralf and Van Wyk, Eric},
  title =	{{SLEBOK: The Software Language Engineering Body of Knowledge (Dagstuhl Seminar 17342)}},
  pages =	{45--54},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{8},
  editor =	{Combemale, Beno\^{i}t and L\"{a}mmel, Ralf and Van Wyk, Eric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.8.45},
  URN =		{urn:nbn:de:0030-drops-84296},
  doi =		{10.4230/DagRep.7.8.45},
  annote =	{Keywords: body of knowledge, language design and implementation, metaprogramming, software languages}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023
  • 1 2018

  • Refine by Author
  • 2 Van Wyk, Eric
  • 1 Biedl, Therese
  • 1 Colin de Verdière, Éric
  • 1 Combemale, Benoît
  • 1 Frati, Fabrizio
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 OASIcs
  • 1 DagRep

  • Refine by Classification
  • 1 Software and its engineering → Domain specific languages
  • 1 Software and its engineering → Parsers
  • 1 Software and its engineering → Syntax
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Context-aware Scanning
  • 1 Enclosure
  • 1 Euler tour
  • 1 Generalized LR Parsing
  • 1 Parsing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact