4 Search Results for "Herter, Jörg"

Document
DOI: 10.4230/LIPIcs.FUN.2026.22
The Quaternary Gray Code and Ziggu Puzzles

Authors: Madeleine Goertz and Aaron Williams

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We investigate solutions to the new "Ziggu" family of sequential puzzles including Ziggurat, Zigguflat, Zigguhooked and so on. These puzzles have p pieces that form m mazes. We encode the state of each puzzle as a quaternary number (i.e., base 4) with n = m+1 digits, where each digit gives the horizontal or vertical position in one maze. For example, the commercial version of Zigguflat has p = 6 pieces connected into m = 4 mazes and its state requires n = 5 digits to describe. We show that the number of states on a shortest solution is 6 ⋅ 2ⁿ - 3n - 5 (Oeis A101946). There is only one solution of this length, and it is generated from the start configuration by a simple algorithm: make the leftmost modification that doesn't undo the previous modification. Replacing "leftmost" with "rightmost" instead generates the unique longest solution that visits all (3^{n+1} - 1)/2 states (Oeis A003462). In this way, Ziggu puzzles can be viewed as 4-ary, 3-ary, or 2-ary puzzles based on how the number of state encodings, valid states, or minimum states grow with each additional maze. Classic Gray code puzzles (e.g., Spin-Out) provide natural and illuminating comparisons. These puzzles with p pieces typically have 2^p (Oeis A000079) or ⌊ 2/3 ⋅ 2^p ⌋ (Oeis A000975 [Stockmeyer, 2017]) states on their unique (shortest) solution, and at most one modification doesn't undo the previous modification. The states visited in a Gray code puzzle solution follow the well-known binary reflected Gray code. We show that Ziggu puzzles instead follow the quaternary reflected Gray code. More specifically, the shortest and longest solutions are both sublists of this order, meaning that some quaternary words are skipped over but the relative order of the remaining words does not change. These results show how to solve Ziggu puzzles from the start configuration. To help solve the puzzle from an arbitrary configuration we provide O(n)-time comparison, and successor algorithms, which give the relative order of two states and the next state, respectively. While Gray code puzzles have simpler recursive descriptions and successor rules, a Ziggu puzzle has a much simpler loopless algorithm to generate its shortest solution than the Gray code puzzles do. The two families are also intimately related as they have the same comparison function.
Cite as

Madeleine Goertz and Aaron Williams. The Quaternary Gray Code and Ziggu Puzzles. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{goertz_et_al:LIPIcs.FUN.2026.22,
  author =	{Goertz, Madeleine and Williams, Aaron},
  title =	{{The Quaternary Gray Code and Ziggu Puzzles}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.22},
  URN =		{urn:nbn:de:0030-drops-257413},
  doi =		{10.4230/LIPIcs.FUN.2026.22},
  annote =	{Keywords: Puzzle, Ziggu, Ziggurat, Zigguflat, Gray Code, Loopless Algorithm}
}
Document
DOI: 10.4230/OASIcs.WCET.2013.77
PRADA: Predictable Allocations by Deferred Actions

Authors: Florian Haupenthal and Jörg Herter

Published in: OASIcs, Volume 30, 13th International Workshop on Worst-Case Execution Time Analysis (2013)

Abstract
Modern hard real-time systems still employ static memory management. However, dynamic storage allocation (DSA) can improve the flexibility and readability of programs as well as drastically shorten their development times. But allocators introduce unpredictability that makes deriving tight bounds on an application's worst-case execution time even more challenging. Especially their statically unpredictable influence on the cache, paired with zero knowledge about the cache set mapping of dynamically allocated objects leads to prohibitively large overestimations of execution times when dynamic memory allocation is employed. Recently, a cache-aware memory allocator, called CAMA, was proposed that gives strong guarantees about its cache influence and the cache set mapping of allocated objects. CAMA itself is rather complex due to its cache-aware implementations of split and merge operations. This paper proposes PRADA, a lighter but less general dynamic memory allocator with equally strong guarantees about its influence on the cache. We compare the memory consumption of PRADA and CAMA for a small set of real-time applications as well as synthetical (de-) allocation sequences to investigate whether a simpler approach to cache awareness is still sufficient for the current generation of real-time applications.
Cite as

Florian Haupenthal and Jörg Herter. PRADA: Predictable Allocations by Deferred Actions. In 13th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 30, pp. 77-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{haupenthal_et_al:OASIcs.WCET.2013.77,
  author =	{Haupenthal, Florian and Herter, J\"{o}rg},
  title =	{{PRADA: Predictable Allocations by Deferred Actions}},
  booktitle =	{13th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{77--86},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-54-5},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{30},
  editor =	{Maiza, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2013.77},
  URN =		{urn:nbn:de:0030-drops-41243},
  doi =		{10.4230/OASIcs.WCET.2013.77},
  annote =	{Keywords: Dynamic Memory Allocation, Worst-Case Execution-Time, Cache Predictability}
}
Document
DOI: 10.4230/OASIcs.WCET.2010.124
Precomputing Memory Locations for Parametric Allocations

Authors: Jörg Herter and Sebastian Altmeyer

Published in: OASIcs, Volume 15, 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)

Abstract
Current worst-case execution time (WCET) analyses do not support programs using dynamic memory allocation. This is mainly due to the unpredictability of cache performance introduced by standard memory allocators. To overcome this problem, algorithms have been proposed that precompute static allocations for dynamically allocating programs with known numeric bounds on the number and sizes of allocated memory blocks. In this paper, we present a novel algorithm for computing such static allocations that can cope with parametric bounds on the number and sizes of allocated blocks. To demonstrate the usefulness of our approach, we precompute static allocations or a set of existing real-time applications and academic examples.
Cite as

Jörg Herter and Sebastian Altmeyer. Precomputing Memory Locations for Parametric Allocations. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Open Access Series in Informatics (OASIcs), Volume 15, pp. 124-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{herter_et_al:OASIcs.WCET.2010.124,
  author =	{Herter, J\"{o}rg and Altmeyer, Sebastian},
  title =	{{Precomputing Memory Locations for Parametric Allocations}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{124--135},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{15},
  editor =	{Lisper, Bj\"{o}rn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2010.124},
  URN =		{urn:nbn:de:0030-drops-28320},
  doi =		{10.4230/OASIcs.WCET.2010.124},
  annote =	{Keywords: WCET analysis, cache analysis, dynamic/static memory allocation}
}
Document
DOI: 10.4230/OASIcs.WCET.2009.2284
Making Dynamic Memory Allocation Static to Support WCET Analysis

Authors: Jörg Herter and Jan Reineke

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)

Abstract
Current worst-case execution time (WCET) analyses do not support programs using dynamic memory allocation. This is mainly due to the unpredictable cache performance when standard memory allocators are used. We present algorithms to compute a static allocation for programs using dynamic memory allocation. Our algorithms strive to produce static allocations that lead to minimal WCET times in a subsequent WCET analyses. Preliminary experiments suggest that static allocations for hard real-time applications can be computed at reasonable computational costs.
Cite as

Jörg Herter and Jan Reineke. Making Dynamic Memory Allocation Static to Support WCET Analysis. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{herter_et_al:OASIcs.WCET.2009.2284,
  author =	{Herter, J\"{o}rg and Reineke, Jan},
  title =	{{Making Dynamic Memory Allocation Static to Support WCET Analysis}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2284},
  URN =		{urn:nbn:de:0030-drops-22846},
  doi =		{10.4230/OASIcs.WCET.2009.2284},
  annote =	{Keywords: WCET analysis, dynamic memory allocation, heap}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2013
  • 1 2010
  • 1 2009

  • Refine by Author
  • 3 Herter, Jörg
  • 1 Altmeyer, Sebastian
  • 1 Goertz, Madeleine
  • 1 Haupenthal, Florian
  • 1 Reineke, Jan
  • Show More...

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

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorics on words

  • Refine by Keyword
  • 2 WCET analysis
  • 1 Cache Predictability
  • 1 Dynamic Memory Allocation
  • 1 Gray Code
  • 1 Loopless Algorithm
  • 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