DROPS

Artifact

Software

JGDoerrer/selection_generator

Authors: Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, and Florian Stober

Abstract

Cite as

Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, Florian Stober. JGDoerrer/selection_generator (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23788,
   title = {{JGDoerrer/selection\underlinegenerator}}, 
   author = {D\"{o}rrer, Josua and Gendle, Konrad and Betz, Johanna and von Smercek, Julius and Steding, Andreas and Stober, Florian},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:abb8051290f859ac8ff2ff5b01f18f4cef1d05ae;origin=https://github.com/JGDoerrer/selection_generator;visit=swh:1:snp:748620e215c47e1e425f3d4c244336c97afc8341;anchor=swh:1:rev:ca3b75668047a916a9801d12ac4f8d77b5feda3c}{\texttt{swh:1:dir:abb8051290f859ac8ff2ff5b01f18f4cef1d05ae}} (visited on 2025-07-15)},
   url = {https://github.com/JGDoerrer/selection_generator},
   doi = {10.4230/artifacts.23788},
}

Document

DOI: 10.4230/LIPIcs.SEA.2025.16

Exact Lower Bounds for the Number of Comparisons in Selection

Authors: Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, and Florian Stober

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

Selection is the problem of finding the i-th smallest element among n elements. We apply computer search to find optimal algorithms for small instances of the selection problem. Using new algorithmic ideas, we establish tighter lower bounds for the number of comparisons required, denoted as V_i(n). Our results include optimal algorithms for n up to 15 and arbitrary i, and for n = 16 when i ≤ 6. We determine the precise values V₇(14) = 25, V₆(15) = V₇(15) = 26, and V₈(15) = 27, where previously, only a range was known.

Cite as

Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, and Florian Stober. Exact Lower Bounds for the Number of Comparisons in Selection. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dorrer_et_al:LIPIcs.SEA.2025.16,
  author =	{D\"{o}rrer, Josua and Gendle, Konrad and Betz, Johanna and von Smercek, Julius and Steding, Andreas and Stober, Florian},
  title =	{{Exact Lower Bounds for the Number of Comparisons in Selection}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.16},
  URN =		{urn:nbn:de:0030-drops-232547},
  doi =		{10.4230/LIPIcs.SEA.2025.16},
  annote =	{Keywords: selection, lower bounds, exhaustive computer search}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2025.156

Membership and Conjugacy in Inverse Semigroups

Authors: Lukas Fleischer, Florian Stober, Alexander Thumm, and Armin Weiß

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

Abstract

The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the membership problem, as well as the conjugacy problem, for finite inverse semigroups. The closely related membership problem for finite semigroups has been shown to be PSPACE-complete in the transformation model by Kozen (1977) and NL-complete in the Cayley table model by Jones, Lien, and Laaser (1976). More recently, both the membership and the conjugacy problem for finite inverse semigroups were shown to be PSPACE-complete in the partial bijection model by Jack (2023). Here we present a more detailed analysis of the complexity of the membership and conjugacy problems parametrized by varieties of finite inverse semigroups. We establish dichotomy theorems for the partial bijection model and for the Cayley table model. In the partial bijection model these problems are in NC (resp. NP for conjugacy) for strict inverse semigroups and PSPACE-complete otherwise. In the Cayley table model we obtain general 𝖫-algorithms as well as NPOLYLOGTIME upper bounds for Clifford semigroups and 𝖫-completeness otherwise. Furthermore, by applying our findings, we show the following: the intersection non-emptiness problem for inverse automata is PSPACE-complete even for automata with only two states; the subpower membership problem is in NC for every strict inverse semigroup and PSPACE-complete otherwise; the minimum generating set and the equation satisfiability problems are in NP for varieties of finite strict inverse semigroups and PSPACE-complete otherwise.

Cite as

Lukas Fleischer, Florian Stober, Alexander Thumm, and Armin Weiß. Membership and Conjugacy in Inverse Semigroups. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 156:1-156:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fleischer_et_al:LIPIcs.ICALP.2025.156,
  author =	{Fleischer, Lukas and Stober, Florian and Thumm, Alexander and Wei{\ss}, Armin},
  title =	{{Membership and Conjugacy in Inverse Semigroups}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{156:1--156: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.156},
  URN =		{urn:nbn:de:0030-drops-235330},
  doi =		{10.4230/LIPIcs.ICALP.2025.156},
  annote =	{Keywords: inverse semigroups, membership, conjugacy, finite automata}
}

Search Results

Documents authored by Stober, Florian

JGDoerrer/selection_generator

Abstract

Cite as

Exact Lower Bounds for the Number of Comparisons in Selection

Abstract

Cite as

Membership and Conjugacy in Inverse Semigroups

Abstract

Cite as

Thanks for your feedback!

Could not send message