5 Search Results for "Werner, Nils"

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.146
Saturation Problems for Families of Automata

Authors: León Bohn, Yong Li, Christof Löding, and Sven Schewe

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

Abstract
Families of deterministic finite automata (FDFA) represent regular ω-languages through their ultimately periodic words (UP-words). An FDFA accepts pairs of words, where the first component corresponds to a prefix of the UP-word, and the second component represents a period of that UP-word. An FDFA is termed saturated if, for each UP-word, either all or none of the pairs representing that UP-word are accepted. We demonstrate that determining whether a given FDFA is saturated can be accomplished in polynomial time, thus improving the known PSPACE upper bound by an exponential. We illustrate the application of this result by presenting the first polynomial learning algorithms for representations of the class of all regular ω-languages. Furthermore, we establish that deciding a weaker property, referred to as almost saturation, is PSPACE-complete. Since FDFAs do not necessarily define regular ω-languages when they are not saturated, we also address the regularity problem and show that it is PSPACE-complete. Finally, we explore a variant of FDFAs called families of deterministic weak automata (FDWA), where the semantics for the periodic part of the UP-word considers ω-words instead of finite words. We demonstrate that saturation for FDWAs is also decidable in polynomial time, that FDWAs always define regular ω-languages, and we compare the succinctness of these different models.
Cite as

León Bohn, Yong Li, Christof Löding, and Sven Schewe. Saturation Problems for Families of Automata. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 146:1-146:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bohn_et_al:LIPIcs.ICALP.2025.146,
  author =	{Bohn, Le\'{o}n and Li, Yong and L\"{o}ding, Christof and Schewe, Sven},
  title =	{{Saturation Problems for Families of Automata}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{146:1--146:19},
  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.146},
  URN =		{urn:nbn:de:0030-drops-235239},
  doi =		{10.4230/LIPIcs.ICALP.2025.146},
  annote =	{Keywords: Families of Automata, automata learning, FDFAs}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.83
French Onion Soup, Ipelets for Points and Polygons (Media Exposition)

Authors: Klint Faber, Auguste H. Gezalyan, Adam Martinson, Aniruddh Mutnuru, Nithin Parepally, Ryan Parker, Mihil Sreenilayam, Aram Zaprosyan, and David M. Mount

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

Abstract
There are many structures, both classical and modern, involving point-sets and polygons whose deeper understanding can be facilitated through interactive visualizations. The Ipe extensible drawing editor, developed by Otfried Cheong, is a widely used software system for generating geometric figures. One of its features is the capability to extend its functionality through programs called Ipelets. In this media submission, we showcase a collection of new Ipelets that construct a variety of geometric structures based on point sets and polygons. These include quadtrees, trapezoidal maps, beta skeletons, floating bodies of convex polygons, onion graphs, fractals (Sierpiński triangle and carpet), simple polygon triangulations, and random point sets in simple polygons. All our Ipelets are programmed in Lua and are freely available.
Cite as

Klint Faber, Auguste H. Gezalyan, Adam Martinson, Aniruddh Mutnuru, Nithin Parepally, Ryan Parker, Mihil Sreenilayam, Aram Zaprosyan, and David M. Mount. French Onion Soup, Ipelets for Points and Polygons (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 83:1-83:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{faber_et_al:LIPIcs.SoCG.2025.83,
  author =	{Faber, Klint and Gezalyan, Auguste H. and Martinson, Adam and Mutnuru, Aniruddh and Parepally, Nithin and Parker, Ryan and Sreenilayam, Mihil and Zaprosyan, Aram and Mount, David M.},
  title =	{{French Onion Soup, Ipelets for Points and Polygons}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{83:1--83:6},
  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.83},
  URN =		{urn:nbn:de:0030-drops-232350},
  doi =		{10.4230/LIPIcs.SoCG.2025.83},
  annote =	{Keywords: Hilbert metric, Macbeath Regions, Polar Bodies, convexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.89
Combining Predicted and Live Traffic with Time-Dependent A* Potentials

Authors: Nils Werner and Tim Zeitz

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study efficient and exact shortest path algorithms for routing on road networks with realistic traffic data. For navigation applications, both current (i.e., live) traffic events and predictions of future traffic flows play an important role in routing. While preprocessing-based speedup techniques have been employed successfully to both settings individually, a combined model poses significant challenges. Supporting predicted traffic typically requires expensive preprocessing while live traffic requires fast updates for regular adjustments. We propose an A*-based solution to this problem. By generalizing A* potentials to time dependency, i.e. the estimate of the distance from a vertex to the target also depends on the time of day when the vertex is visited, we achieve significantly faster query times than previously possible. Our evaluation shows that our approach enables interactive query times on continental-sized road networks while allowing live traffic updates within a fraction of a minute. We achieve a speedup of at least two orders of magnitude over Dijkstra’s algorithm and up to one order of magnitude over state-of-the-art time-independent A* potentials.
Cite as

Nils Werner and Tim Zeitz. Combining Predicted and Live Traffic with Time-Dependent A* Potentials. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 89:1-89:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{werner_et_al:LIPIcs.ESA.2022.89,
  author =	{Werner, Nils and Zeitz, Tim},
  title =	{{Combining Predicted and Live Traffic with Time-Dependent A* Potentials}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{89:1--89:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.89},
  URN =		{urn:nbn:de:0030-drops-170271},
  doi =		{10.4230/LIPIcs.ESA.2022.89},
  annote =	{Keywords: realistic road networks, shortest paths, live traffic, time-dependent routing}
}
Document
DOI: 10.4230/LITES.7.1.1
Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication

Authors: Kristin Krüger, Nils Vreman, Richard Pates, Martina Maggio, Marcus Völp, and Gerhard Fohler

Published in: LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security. Leibniz Transactions on Embedded Systems, Volume 7, Issue 1

Abstract
Time-triggered real-time systems achieve deterministic behavior using schedules that are constructed offline, based on scheduling constraints. Their deterministic behavior makes time-triggered systems suitable for usage in safety-critical environments, like avionics. However, this determinism also allows attackers to fine-tune attacks that can be carried out after studying the behavior of the system through side channels, targeting safety-critical victim tasks. Replication -- i.e., the execution of task variants across different cores -- is inherently able to tolerate both accidental and malicious faults (i.e. attacks) as long as these faults are independent of one another. Yet, targeted attacks on the timing behavior of tasks which utilize information gained about the system behavior violate the fault independence assumption fault tolerance is based on. This violation may give attackers the opportunity to compromise all replicas simultaneously, in particular if they can mount the attack from already compromised components. In this paper, we analyze vulnerabilities of time-triggered systems, focusing on safety-certified multicore real-time systems. We introduce two runtime mitigation strategies to withstand directed timing inference based attacks: (i) schedule randomization at slot level, and (ii) randomization within a set of offline constructed schedules. We evaluate these mitigation strategies with synthetic experiments and a real case study to show their effectiveness and practicality.
Cite as

Kristin Krüger, Nils Vreman, Richard Pates, Martina Maggio, Marcus Völp, and Gerhard Fohler. Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication. In LITES, Volume 7, Issue 1 (2021): Special Issue on Embedded System Security. Leibniz Transactions on Embedded Systems, Volume 7, Issue 1, pp. 01:1-01:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{kruger_et_al:LITES.7.1.1,
  author =	{Kr\"{u}ger, Kristin and Vreman, Nils and Pates, Richard and Maggio, Martina and V\"{o}lp, Marcus and Fohler, Gerhard},
  title =	{{Randomization as Mitigation of Directed Timing Inference Based Attacks on Time-Triggered Real-Time Systems with Task Replication}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:29},
  ISSN =	{2199-2002},
  year =	{2021},
  volume =	{7},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.7.1.1},
  URN =		{urn:nbn:de:0030-drops-192847},
  doi =		{10.4230/LITES.7.1.1},
  annote =	{Keywords: real-time systems, time-triggered systems, security}
}
Document
DOI: 10.4230/OASIcs.KiVS.2011.26
A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems

Authors: Martin Lipphardt, Nils Glombitza, Jana Neumann, Christian Werner, and Stefan Fischer

Published in: OASIcs, Volume 17, 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)

Abstract
The paradigm of service-orientation promises a significant ease of use in creating and managing distributed software systems. A very important aspect here is that also application domain experts and stakeholders, who are not necessarily skilled in computer programming, get a chance to create, analyze, and adapt distributed applications. However, up to now, service-oriented architectures have been mainly discussed in the context of complex business applications. In this paper we will investigate how to transfer the benefits of a service-oriented architecture into the field of embedded systems, so that this technology gets accessible to a much wider range of users. As an example, we will demonstrate this scheme for sensor network applications. In order to address the problem of limited device resources we will introduce a minimal operating system for such devices. It organizes all pieces of code running on a sensor node in a service-oriented fashion and also features the relocation of code to a different node at runtime. We will demonstrate that it is possible to design a sensor network application from a set of already existing services in a highly modular way by employing already existing technologies and standards.
Cite as

Martin Lipphardt, Nils Glombitza, Jana Neumann, Christian Werner, and Stefan Fischer. A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 26-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{lipphardt_et_al:OASIcs.KiVS.2011.26,
  author =	{Lipphardt, Martin and Glombitza, Nils and Neumann, Jana and Werner, Christian and Fischer, Stefan},
  title =	{{A Service-Oriented Operating System and an Application Development Infrastructure for Distributed Embedded Systems}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{26--37},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-27-9},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{17},
  editor =	{Luttenberger, Norbert and Peters, Hagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.26},
  URN =		{urn:nbn:de:0030-drops-29550},
  doi =		{10.4230/OASIcs.KiVS.2011.26},
  annote =	{Keywords: service-oriented OS, sensor network, distributed embedded systems}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2022
  • 1 2021
  • 1 2011

  • Refine by Author
  • 1 Bohn, León
  • 1 Faber, Klint
  • 1 Fischer, Stefan
  • 1 Fohler, Gerhard
  • 1 Gezalyan, Auguste H.
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 1 OASIcs
  • 1 LITES

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Computer systems organization → Real-time systems
  • 1 Computer systems organization → Redundancy
  • 1 Mathematics of computing → Graph algorithms
  • 1 Security and privacy → Operating systems security
  • Show More...

  • Refine by Keyword
  • 1 FDFAs
  • 1 Families of Automata
  • 1 Hilbert metric
  • 1 Macbeath Regions
  • 1 Polar Bodies
  • 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