7 Search Results for "Gruber, Hermann"

Document
DOI: 10.4230/LIPIcs.LICS.2026.69
The Complexity of Downward Closures of Indexed Languages

Authors: Richard Mandel, Corto Mascle, and Georg Zetzsche

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
Indexed languages are a classical notion in formal language theory, which has attracted attention in recent decades due to its role in higher-order model checking: They are precisely the languages accepted by order-2 pushdown automata. The downward closure of an indexed language - the set of all (scattered) subwords of its members - is well-known to be a regular over-approximation. It is known since 2015 that the downward closure of a given indexed language is effectively computable. However, the algorithm comes with no complexity bounds, and it has remained open whether a primitive-recursive construction exists. We settle this question and provide a triply (resp. quadruply) exponential construction of a non-deterministic (resp. deterministic) automaton. We also prove (asymptotically) matching lower bounds. For the upper bounds, we rely on recent advances in semigroup theory, which let us compute bounded-size summaries of words with respect to a finite semigroup. By replacing stacks with their summaries, we are able to transform an indexed grammar into a context-free one with the same downward closure, and then apply existing bounds for context-free grammars.
Cite as

Richard Mandel, Corto Mascle, and Georg Zetzsche. The Complexity of Downward Closures of Indexed Languages. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 69:1-69:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mandel_et_al:LIPIcs.LICS.2026.69,
  author =	{Mandel, Richard and Mascle, Corto and Zetzsche, Georg},
  title =	{{The Complexity of Downward Closures of Indexed Languages}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{69:1--69:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.69},
  URN =		{urn:nbn:de:0030-drops-268562},
  doi =		{10.4230/LIPIcs.LICS.2026.69},
  annote =	{Keywords: Higher-order pushdown automata, well quasi-orders, semigroup algebra}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.24
ZOR Filters: Fast and Smaller Than Fuse Filters

Authors: Antoine Limasset

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Probabilistic membership filters support fast approximate membership queries with controlled false-positive probability ε and are widely used across storage, analytics, networking, and bioinformatics [Chang et al., 2008; Niv Dayan et al., 2018; Broder and Mitzenmacher, 2004; Harris and Medvedev, 2020; Marchet and Limasset, 2023; Chikhi et al., 2025; Hernandez-Courbevoie et al., 2025]. In the static setting, low-overhead methods such as XOR, Fuse, and BuRR have been proposed [Graf and Lemire, 2020; Graf and Lemire, 2022; Dillinger et al., 2022; Ulrich and Renard, 2023]. Among these, Fuse filters are known for near-optimal query throughput. For XOR/Fuse-style peeling constructions, however, build success is only high probability, which complicates deterministic builds. We introduce ZOR filters, a deterministic continuation of XOR/Fuse-style constructions that guarantees termination while preserving the same XOR-based query mechanism. ZOR replaces restart-on-failure with deterministic peeling that abandons a small fraction of keys, and restores false-positive-only semantics by storing the remainder in a compact auxiliary structure. In our experiments, the abandoned fraction drops below 1% for moderate arity (e.g., N ≥ 5), so the auxiliary handles a negligible fraction of keys. As a result, ZOR filters can be substantially more memory-efficient than Fuse filters, with overhead below 1%, while not yet matching the near-optimal overhead of BuRR (below 0.1%). In query performance, ZOR-pure is close to Fuse and faster than BuRR on positive queries, while the complete interleaved variant trades additional negative-query latency for deterministic continuation. Relative to optimised Fuse/BuRR implementations [Graf and Lemire, 2022; Dillinger et al., 2022], the current ZOR prototype remains slower in construction because deterministic peeling requires explicit incidence handling; reducing this construction gap is an important direction for future work.
Cite as

Antoine Limasset. ZOR Filters: Fast and Smaller Than Fuse Filters. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{limasset:LIPIcs.SEA.2026.24,
  author =	{Limasset, Antoine},
  title =	{{ZOR Filters: Fast and Smaller Than Fuse Filters}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.24},
  URN =		{urn:nbn:de:0030-drops-260281},
  doi =		{10.4230/LIPIcs.SEA.2026.24},
  annote =	{Keywords: Data structure, Approximate Set Membership, Static filter}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.17
Sorting Magazines and Boxes

Authors: Gabriele Fici, Manal Mohamed, and Jakub Radoszewski

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

Abstract
It is a rainy Sunday. Agata has decided to sort the magazines on her shelf. Because the magazines are quite thin, she refuses to insert one between two others, preferring to move them only to the ends of the shelf. She has conceived a strategy for this but is unsure of its efficiency. Meanwhile, in the adjacent room, her three-year-old son, Szymon, has just finished his Montessori tower puzzle and is figuring out how to put it away. He has adopted a very intuitive approach to nesting the boxes, though he is not certain it will ultimately succeed. Agata and Szymon are employing very primitive strategies. While many sorting algorithms are remarkably simple to explain and implement-specifically, the class of in-place sorting algorithms with 𝒪(n²) worst-case and average-case running time and constant space requirements (e.g., Bubble Sort, Gnome Sort)-the strategies discussed here offer a unique perspective on "intuitive" sorting. Our contribution aims to enrich the field of simple sorting algorithms. Interestingly, determining the exact worst-case complexity of some of the proposed algorithms remains an open problem.
Cite as

Gabriele Fici, Manal Mohamed, and Jakub Radoszewski. Sorting Magazines and Boxes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:LIPIcs.FUN.2026.17,
  author =	{Fici, Gabriele and Mohamed, Manal and Radoszewski, Jakub},
  title =	{{Sorting Magazines and Boxes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{17:1--17:13},
  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.17},
  URN =		{urn:nbn:de:0030-drops-257368},
  doi =		{10.4230/LIPIcs.FUN.2026.17},
  annote =	{Keywords: Sorting algorithm, analysis of algorithms, intuitive sorting}
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.44
Minimal DFAs Witnessing Language Inequivalence

Authors: Jan Martens

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
We study small witnesses for the inequivalence of two regular languages. A natural witness is a distinguishing word, e.g. a word in exactly one of the two languages. We propose using more succinct witnesses in the form of witnessing DFAs. A witnessing DFA recognizes a subset of one of the languages and contains at least one distinguishing word. In this way the DFA expresses behaviour contained in the first language but not the second. We show witnessing DFAs can be used to present more concise witnesses for the inequivalence of two regular languages. We show that the decision problem for the existence of a witnessing DFA of certain size is NP-complete in general, and in P in the special case of unary DFAs. Besides these computational aspects, we study structural properties of witnessing DFAs. Not all languages can be a minimal witness. It turns out that minimal witnesses are exactly the languages that are not decomposable in the union of languages with smaller state-complexity, the so-called prime languages as studied earlier by Kupferman and Mosheiff.
Cite as

Jan Martens. Minimal DFAs Witnessing Language Inequivalence. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{martens:LIPIcs.CSL.2026.44,
  author =	{Martens, Jan},
  title =	{{Minimal DFAs Witnessing Language Inequivalence}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{44:1--44:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.44},
  URN =		{urn:nbn:de:0030-drops-254691},
  doi =		{10.4230/LIPIcs.CSL.2026.44},
  annote =	{Keywords: Deterministic Finite Automata, Language Inequivalence, DFA decomposition, Prime languages}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.69
Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing

Authors: David Eppstein, Michael T. Goodrich, and Songyu (Alfred) Liu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We provide the first approximation quality guarantees for the Cuthull-McKee heuristic for reordering symmetric matrices to have low bandwidth, and we provide an algorithm for reconstructing bounded-bandwidth graphs from distance oracles with near-linear query complexity. To prove these results we introduce a new width parameter, BFS width, and we prove polylogarithmic upper and lower bounds on the BFS width of graphs of bounded bandwidth. Unlike other width parameters, such as bandwidth, pathwidth, and treewidth, BFS width can easily be computed in polynomial time. Bounded BFS width implies bounded bandwidth, pathwidth, and treewidth, which in turn imply fixed-parameter tractable algorithms for many problems that are NP-hard for general graphs. In addition to their applications to matrix ordering, we also provide applications of BFS width to graph reconstruction, to reconstruct graphs from distance queries, and graph drawing, to construct arc diagrams of small height.
Cite as

David Eppstein, Michael T. Goodrich, and Songyu (Alfred) Liu. Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 69:1-69:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ESA.2025.69,
  author =	{Eppstein, David and Goodrich, Michael T. and Liu, Songyu (Alfred)},
  title =	{{Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{69:1--69:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.69},
  URN =		{urn:nbn:de:0030-drops-245373},
  doi =		{10.4230/LIPIcs.ESA.2025.69},
  annote =	{Keywords: Graph algorithms, graph theory, graph width, bandwidth, treewidth}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.5
Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion

Authors: Da-Jung Cho, Szilárd Zsolt Fazekas, Shinnosuke Seki, and Max Wiedenhöft

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
RNA co-transcriptionality, where RNA is spliced or folded during transcription from DNA templates, offers promising potential for molecular programming. It enables programmable folding of nanoscale RNA structures and has recently been shown to be Turing universal. While post-transcriptional splicing is well studied, co-transcriptional splicing is gaining attention for its efficiency, though its unpredictability still remains a challenge. In this paper, we focus on engineering co-transcriptional splicing, not only as a natural phenomenon but as a programmable mechanism for generating specific RNA target sequences from DNA templates. The problem we address is whether we can encode a set of RNA sequences for a given system onto a DNA template word, ensuring that all the sequences are generated through co-transcriptional splicing. Given that finding the optimal encoding has been shown to be NP-complete under the various energy models considered [Da-Jung Cho et al., 2025], we propose a practical alternative approach under the logarithmic energy model. More specifically, we provide a construction that encodes an arbitrary nondeterministic finite automaton (NFA) into a circular DNA template from which co-transcriptional splicing produces all sequences accepted by the NFA. As all finite languages can be efficiently encoded as NFA, this framework solves the problem of finding small DNA templates for arbitrary target sets of RNA sequences. The quest to obtain the smallest possible such templates naturally leads us to consider the problem of minimizing NFAs and certain practically motivated variants of it, but as we show, those minimization problems are computationally intractable.
Cite as

Da-Jung Cho, Szilárd Zsolt Fazekas, Shinnosuke Seki, and Max Wiedenhöft. Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.DNA.31.5,
  author =	{Cho, Da-Jung and Fazekas, Szil\'{a}rd Zsolt and Seki, Shinnosuke and Wiedenh\"{o}ft, Max},
  title =	{{Programmable Co‑Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.5},
  URN =		{urn:nbn:de:0030-drops-238548},
  doi =		{10.4230/LIPIcs.DNA.31.5},
  annote =	{Keywords: RNA Transcription, Co-Transcriptional Splicing, Finite Automata Simulation, NFA Minimization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.52
Optimal Regular Expressions for Palindromes of Given Length

Authors: Hermann Gruber and Markus Holzer

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
The language P_n (P̃_n, respectively) consists of all words that are palindromes of length 2n (2n-1, respectively) over a fixed binary alphabet. We construct a regular expression that specifies P_n (P̃_n, respectively) of alphabetic width 4⋅ 2ⁿ-4 (3⋅ 2ⁿ-4, respectively) and show that this is optimal, that is, the expression has minimum alphabetic width among all expressions that describe P_n (P̃_n, respectively). To this end we give optimal expressions for the first k palindromes in lexicographic order of odd and even length, proving that the optimal bound is 2n+4(k-1)-2 S₂(k-1) in case of odd length and 2n+3(k-1)-2 S₂(k-1)-1 for even length, respectively. Here S₂(n) refers to the Hamming weight function, which denotes the number of ones in the binary expansion of the number n.
Cite as

Hermann Gruber and Markus Holzer. Optimal Regular Expressions for Palindromes of Given Length. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gruber_et_al:LIPIcs.MFCS.2021.52,
  author =	{Gruber, Hermann and Holzer, Markus},
  title =	{{Optimal Regular Expressions for Palindromes of Given Length}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.52},
  URN =		{urn:nbn:de:0030-drops-144921},
  doi =		{10.4230/LIPIcs.MFCS.2021.52},
  annote =	{Keywords: regular expression, descriptional complexity, lower bound, upper bound, recurrence, sum of digits}
}
  • Refine by Type
  • 7 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 2 2025
  • 1 2021

  • Refine by Author
  • 1 Cho, Da-Jung
  • 1 Eppstein, David
  • 1 Fazekas, Szilárd Zsolt
  • 1 Fici, Gabriele
  • 1 Goodrich, Michael T.
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Regular languages
  • 1 Applied computing → Bioinformatics
  • 1 Mathematics of computing → Nonlinear equations
  • 1 Theory of computation
  • 1 Theory of computation → Data structures design and analysis
  • Show More...

  • Refine by Keyword
  • 1 Approximate Set Membership
  • 1 Co-Transcriptional Splicing
  • 1 DFA decomposition
  • 1 Data structure
  • 1 Deterministic Finite Automata
  • 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