2 Search Results for "Zetzsche, Stefan"

Document
DOI: 10.4230/LIPIcs.CALCO.2023.11
Generators and Bases for Monadic Closures

Authors: Stefan Zetzsche, Alexandra Silva, and Matteo Sammartino

Published in: LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)

Abstract
It is well-known that every regular language admits a unique minimal deterministic acceptor. Establishing an analogous result for non-deterministic acceptors is significantly more difficult, but nonetheless of great practical importance. To tackle this issue, a number of sub-classes of non-deterministic automata have been identified, all admitting canonical minimal representatives. In previous work, we have shown that such representatives can be recovered categorically in two steps. First, one constructs the minimal bialgebra accepting a given regular language, by closing the minimal coalgebra with additional algebraic structure over a monad. Second, one identifies canonical generators for the algebraic part of the bialgebra, to derive an equivalent coalgebra with side effects in a monad. In this paper, we further develop the general theory underlying these two steps. On the one hand, we show that deriving a minimal bialgebra from a minimal coalgebra can be realized by applying a monad on an appropriate category of subobjects. On the other hand, we explore the abstract theory of generators and bases for algebras over a monad.
Cite as

Stefan Zetzsche, Alexandra Silva, and Matteo Sammartino. Generators and Bases for Monadic Closures. In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 11:1-11:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zetzsche_et_al:LIPIcs.CALCO.2023.11,
  author =	{Zetzsche, Stefan and Silva, Alexandra and Sammartino, Matteo},
  title =	{{Generators and Bases for Monadic Closures}},
  booktitle =	{10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-287-7},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{270},
  editor =	{Baldan, Paolo and de Paiva, Valeria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.11},
  URN =		{urn:nbn:de:0030-drops-188084},
  doi =		{10.4230/LIPIcs.CALCO.2023.11},
  annote =	{Keywords: Monads, Category Theory, Generators, Automata, Coalgebras, Bialgebras}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.71
Membership Problems in Finite Groups

Authors: Markus Lohrey, Andreas Rosowski, and Georg Zetzsche

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed n ≥ 3, where n is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks [Eugene M. Luks, 1991], which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar.
Cite as

Markus Lohrey, Andreas Rosowski, and Georg Zetzsche. Membership Problems in Finite Groups. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 71:1-71:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lohrey_et_al:LIPIcs.MFCS.2022.71,
  author =	{Lohrey, Markus and Rosowski, Andreas and Zetzsche, Georg},
  title =	{{Membership Problems in Finite Groups}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{71:1--71:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.71},
  URN =		{urn:nbn:de:0030-drops-168694},
  doi =		{10.4230/LIPIcs.MFCS.2022.71},
  annote =	{Keywords: algorithms for finite groups, intersection non-emptiness problems, knapsack problems in groups}
}
  • Refine by Author
  • 1 Lohrey, Markus
  • 1 Rosowski, Andreas
  • 1 Sammartino, Matteo
  • 1 Silva, Alexandra
  • 1 Zetzsche, Georg
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Abstract machines
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Automata
  • 1 Bialgebras
  • 1 Category Theory
  • 1 Coalgebras
  • 1 Generators
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact