6 Search Results for "Sachenbacher, Martin"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.71
Faster All-Pairs Optimal Electric Car Routing

Authors: Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, and Uri Zwick

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present a randomized Õ(n^{3.5})-time algorithm for computing optimal energetic paths for an electric car between all pairs of vertices in an n-vertex directed graph with positive and negative costs, or gains, which are defined to be the negatives of the costs. The optimal energetic paths are finite and well-defined even if the graph contains negative-cost, or equivalently, positive-gain, cycles. This makes the problem much more challenging than standard shortest paths problems. More specifically, for every two vertices s and t in the graph, the algorithm computes α_B(s,t), the maximum amount of charge the car can reach t with, if it starts at s with full battery, i.e., with charge B, where B is the capacity of the battery. The algorithm also outputs a concise description of the optimal energetic paths that achieve these values. In the presence of positive-gain cycles, optimal paths are not necessarily simple. For dense graphs, our new Õ(n^{3.5}) time algorithm improves on a previous Õ(mn²)-time algorithm of Dorfman et al. [ESA 2023] for the problem. The gain of an arc is the amount of charge added to the battery of the car when traversing the arc. The charge in the battery can never exceed the capacity B of the battery and can never be negative. An arc of positive gain may correspond, for example, to a downhill road segment, while an arc with a negative gain may correspond to an uphill segment. A positive-gain cycle, if one exists, can be used in certain cases to charge the battery to its capacity. This makes the problem more interesting and more challenging. As mentioned, optimal energetic paths are well-defined even in the presence of positive-gain cycles. Positive-gain cycles may arise when certain road segments have magnetic charging strips, or when the electric car has solar panels. Combined with a result of Dorfman et al. [SOSA 2024], this also provides a randomized Õ(n^{3.5})-time algorithm for computing minimum-cost paths between all pairs of vertices in an n-vertex graph when the battery can be externally recharged, at varying costs, at intermediate vertices.
Cite as

Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, and Uri Zwick. Faster All-Pairs Optimal Electric Car Routing. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 71:1-71:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dorfman_et_al:LIPIcs.ICALP.2025.71,
  author =	{Dorfman, Dani and Kaplan, Haim and Tarjan, Robert E. and Thorup, Mikkel and Zwick, Uri},
  title =	{{Faster All-Pairs Optimal Electric Car Routing}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{71:1--71:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.71},
  URN =		{urn:nbn:de:0030-drops-234486},
  doi =		{10.4230/LIPIcs.ICALP.2025.71},
  annote =	{Keywords: EV routing, Shortest Paths, Shortcuts, Sampling}
}
Artifact
Software
DOI: 10.4230/artifacts.22521
FDIR for Digital Twins

Authors: Lars B. Vosteen

Abstract
Cite as

Lars B. Vosteen. FDIR for Digital Twins (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22521,
   title = {{FDIR for Digital Twins}}, 
   author = {Vosteen, Lars B.},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:1972d8d2373f5d9c6e127fa16aec1a79755b056a;origin=https://github.com/vosteen/FDIR;visit=swh:1:snp:c9a73730361a36994df71bab5b2150024588732e;anchor=swh:1:rev:46a2b9be2315daba026bacbf9f97d0bbaf6ba8c8}{\texttt{swh:1:dir:1972d8d2373f5d9c6e127fa16aec1a79755b056a}} (visited on 2024-11-28)},
   url = {https://github.com/vosteen/FDIR},
   doi = {10.4230/artifacts.22521},
}
Document
DOI: 10.4230/OASIcs.DX.2024.2
A Model-Based Approach for Monitoring and Diagnosing Digital Twin Discrepancies

Authors: Elaheh Hosseinkhani, Martin Leucker, Martin Sachenbacher, Hendrik Streichhahn, and Lars B. Vosteen

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
Recent decades have seen the increasing use of Digital Twins (DTs) - that is, digital models used over the lifetime of a physical product or system for tasks such as predictive maintenance or optimization - in a number of domains such as buildings, manufacturing, or design. DTs face a challenge known as the DT synchronization problem; a DT, often based on machine-learned, or complex simulation models, needs to adequately mirror the physical product or system at all times, as any deviations might affect the quality of predictions or control actions. In this paper, we present a model-based approach that aims to add a level of awareness to DT models by supervising if they are in sync with the physical counterpart. The approach is agnostic to the type of models used in the DT, as long as they are compositional, and based on monitoring critical properties (behavioral or functional aspects) of the system at run-time. In the case violations are detected, it reasons on the DT’s structure to localize and identify parts of the model that cause deviations and need to be adapted. We give a formal description and an implementation of this approach, and illustrate it with an example from building climatisation.
Cite as

Elaheh Hosseinkhani, Martin Leucker, Martin Sachenbacher, Hendrik Streichhahn, and Lars B. Vosteen. A Model-Based Approach for Monitoring and Diagnosing Digital Twin Discrepancies. In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hosseinkhani_et_al:OASIcs.DX.2024.2,
  author =	{Hosseinkhani, Elaheh and Leucker, Martin and Sachenbacher, Martin and Streichhahn, Hendrik and Vosteen, Lars B.},
  title =	{{A Model-Based Approach for Monitoring and Diagnosing Digital Twin Discrepancies}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{2:1--2:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.2},
  URN =		{urn:nbn:de:0030-drops-220944},
  doi =		{10.4230/OASIcs.DX.2024.2},
  annote =	{Keywords: Digital Twins, Runtime Verification, Diagnosis, FDIR, TeSSLa}
}
Document
Short Paper
DOI: 10.4230/OASIcs.DX.2024.19
Achieving Complete Structural Test Coverage in Embedded Systems Using Trace-Based Monitoring (Short Paper)

Authors: Alexander Weiss, Albert Schulz, Martin Heininger, Martin Sachenbacher, and Martin Leucker

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
This paper presents a systematic approach to achieving, in a well-defined sense, 100% structural test coverage for large embedded software projects. In embedded systems, high code coverage is a critical part of the testing process to ensure that the system works correctly. Measuring code coverage provides insight into the effectiveness of the testing process, the quality of the software, and can help identify untested or partially tested areas of the code. Traditionally, coverage is often measured when unit tests are executed. The proposed approach instead uses integration tests as the starting point for determining test completeness. Measuring code coverage at the integration test level in embedded systems can be challenging due to the limitations of software instrumentation (additional memory requirements and additional CPU load). To overcome these limitations, embedded trace technology is used to measure code coverage continuously and non-intrusively. The use of these techniques will help to increase the reliability of embedded software and reduce the likelihood of missed integration tests, missed high-level requirements, and undetected software defects.
Cite as

Alexander Weiss, Albert Schulz, Martin Heininger, Martin Sachenbacher, and Martin Leucker. Achieving Complete Structural Test Coverage in Embedded Systems Using Trace-Based Monitoring (Short Paper). In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{weiss_et_al:OASIcs.DX.2024.19,
  author =	{Weiss, Alexander and Schulz, Albert and Heininger, Martin and Sachenbacher, Martin and Leucker, Martin},
  title =	{{Achieving Complete Structural Test Coverage in Embedded Systems Using Trace-Based Monitoring}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{19:1--19:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.19},
  URN =		{urn:nbn:de:0030-drops-221115},
  doi =		{10.4230/OASIcs.DX.2024.19},
  annote =	{Keywords: structural tests, integration tests, code coverage, embedded trace}
}
Document
DOI: 10.4230/DagSemProc.10451.1
10451 Abstracts Collection – Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems

Authors: Klaus Havelund, Martin Leucker, Martin Sachenbacher, Oleg Sokolsky, and Brian C. Williams

Published in: Dagstuhl Seminar Proceedings, Volume 10451, Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems (2011)

Abstract
From November 7 to 12, 2010, the Dagstuhl Seminar 10451 ``Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, 35 participants presented their current research and discussed ongoing work and open problems. This document puts together abstracts of the presentations given during the seminar, and provides links to extended abstracts or full papers, if available.
Cite as

Klaus Havelund, Martin Leucker, Martin Sachenbacher, Oleg Sokolsky, and Brian C. Williams. 10451 Abstracts Collection – Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems. In Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems. Dagstuhl Seminar Proceedings, Volume 10451, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{havelund_et_al:DagSemProc.10451.1,
  author =	{Havelund, Klaus and Leucker, Martin and Sachenbacher, Martin and Sokolsky, Oleg and Williams, Brian C.},
  title =	{{10451 Abstracts Collection – Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems}},
  booktitle =	{Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10451},
  editor =	{Klaus Havelund and Martin Leucker and Martin Sachenbacher and Oleg Sokolsky and Brian C. Williams},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10451.1},
  URN =		{urn:nbn:de:0030-drops-29487},
  doi =		{10.4230/DagSemProc.10451.1},
  annote =	{Keywords: Runtime Verification, Model-based Diagnosis, Planning, Control, Autonomous Systems}
}
Document
DOI: 10.4230/DagSemProc.10451.2
10451 Executive Summary – Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems

Authors: Klaus Havelund, Martin Leucker, Martin Sachenbacher, Oleg Sokolsky, and Brian C. Williams

Published in: Dagstuhl Seminar Proceedings, Volume 10451, Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems (2011)

Abstract
From November 7 to 12, 2010, the Dagstuhl Seminar 10451 'Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems' was held in Schloss Dagstuhl – Leibniz Center for Informatics. During the seminar, 35 participants presented their current research and discussed ongoing work and open problems. This document puts together abstracts of the presentations given during the seminar, and provides links to extended abstracts or full papers, if available.
Cite as

Klaus Havelund, Martin Leucker, Martin Sachenbacher, Oleg Sokolsky, and Brian C. Williams. 10451 Executive Summary – Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems. In Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems. Dagstuhl Seminar Proceedings, Volume 10451, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{havelund_et_al:DagSemProc.10451.2,
  author =	{Havelund, Klaus and Leucker, Martin and Sachenbacher, Martin and Sokolsky, Oleg and Williams, Brian C.},
  title =	{{10451 Executive Summary – Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems}},
  booktitle =	{Runtime Verification, Diagnosis, Planning and Control for Autonomous Systems},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10451},
  editor =	{Klaus Havelund and Martin Leucker and Martin Sachenbacher and Oleg Sokolsky and Brian C. Williams},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10451.2},
  URN =		{urn:nbn:de:0030-drops-29476},
  doi =		{10.4230/DagSemProc.10451.2},
  annote =	{Keywords: Runtime Verification, Model-based Diagnosis, Planning, Control, Autonomous Systems}
}
  • Refine by Type
  • 5 Document/PDF
  • 1 Artifact
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 3 2024
  • 2 2011

  • Refine by Author
  • 4 Leucker, Martin
  • 4 Sachenbacher, Martin
  • 2 Havelund, Klaus
  • 2 Sokolsky, Oleg
  • 2 Vosteen, Lars B.
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 2 OASIcs
  • 2 DagSemProc

  • Refine by Classification
  • 1 Computer systems organization → Reliability
  • 1 Hardware → Coverage metrics
  • 1 Hardware → Reconfigurable logic applications
  • 1 Software and its engineering → Software testing and debugging
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 3 Runtime Verification
  • 2 Autonomous Systems
  • 2 Control
  • 2 Model-based Diagnosis
  • 2 Planning
  • 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