Search Results

Documents authored by Sabellek, Leif

Document
DOI: 10.4230/LIPIcs.ICDT.2025.24
Learning Tree Pattern Transformations

Authors: Daniel Neider, Leif Sabellek, Johannes Schmidt, Fabian Vehlken, and Thomas Zeume

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
Explaining why and how a tree t structurally differs from another tree t^⋆ is a question that is encountered throughout computer science, including in understanding tree-structured data such as XML or JSON data. In this article, we explore how to learn explanations for structural differences between pairs of trees from sample data: suppose we are given a set {(t₁, t₁^⋆),… , (t_n, t_n^⋆)} of pairs of labelled, ordered trees; is there a small set of rules that explains the structural differences between all pairs (t_i, t_i^⋆)? This raises two research questions: (i) what is a good notion of "rule" in this context?; and (ii) how can sets of rules explaining a data set be learned algorithmically? We explore these questions from the perspective of database theory by (1) introducing a pattern-based specification language for tree transformations; (2) exploring the computational complexity of variants of the above algorithmic problem, e.g. showing NP-hardness for very restricted variants; and (3) discussing how to solve the problem for data from CS education research using SAT solvers.
Cite as

Daniel Neider, Leif Sabellek, Johannes Schmidt, Fabian Vehlken, and Thomas Zeume. Learning Tree Pattern Transformations. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{neider_et_al:LIPIcs.ICDT.2025.24,
  author =	{Neider, Daniel and Sabellek, Leif and Schmidt, Johannes and Vehlken, Fabian and Zeume, Thomas},
  title =	{{Learning Tree Pattern Transformations}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.24},
  URN =		{urn:nbn:de:0030-drops-229652},
  doi =		{10.4230/LIPIcs.ICDT.2025.24},
  annote =	{Keywords: Tree pattern transformations, learning from positive examples, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.CSL.2024.31
Remarks on Parikh-Recognizable Omega-languages

Authors: Mario Grobler, Leif Sabellek, and Sebastian Siebertz

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
Several variants of Parikh automata on infinite words were recently introduced by Guha et al. [FSTTCS, 2022]. We show that one of these variants coincides with blind counter machine as introduced by Fernau and Stiebe [Fundamenta Informaticae, 2008]. Fernau and Stiebe showed that every ω-language recognized by a blind counter machine is of the form ⋃_iU_iV_i^ω for Parikh recognizable languages U_i, V_i, but blind counter machines fall short of characterizing this class of ω-languages. They posed as an open problem to find a suitable automata-based characterization. We introduce several additional variants of Parikh automata on infinite words that yield automata characterizations of classes of ω-language of the form ⋃_iU_iV_i^ω for all combinations of languages U_i, V_i being regular or Parikh-recognizable. When both U_i and V_i are regular, this coincides with Büchi’s classical theorem. We study the effect of ε-transitions in all variants of Parikh automata and show that almost all of them admit ε-elimination. Finally we study the classical decision problems with applications to model checking.
Cite as

Mario Grobler, Leif Sabellek, and Sebastian Siebertz. Remarks on Parikh-Recognizable Omega-languages. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.CSL.2024.31,
  author =	{Grobler, Mario and Sabellek, Leif and Siebertz, Sebastian},
  title =	{{Remarks on Parikh-Recognizable Omega-languages}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{31:1--31:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello 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.CSL.2024.31},
  URN =		{urn:nbn:de:0030-drops-196743},
  doi =		{10.4230/LIPIcs.CSL.2024.31},
  annote =	{Keywords: Parikh automata, blind counter machines, infinite words, B\"{u}chi’s theorem}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2019.28
Granular Spatial Calculi of Relative Directions or Movements with Parallelism: Consistent Account (Short Paper)

Authors: Reinhard Moratz, Leif Sabellek, and Thomas Schneider

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)

Abstract
The OPRA* calculus family, originally suggested by Frank Dylla, adds parallelism to the OPRA calculus family which is very popular in Qualitative Spatio-temporal Reasoning (QSTR). Adding parallelism enables the direct representation of parallel moving objects, which is relevant in many applications like traffic monitoring. However, it turned out that it is hard to derive a sound geometric analysis. So far no sound spatial reasoning was supported. Our new generic analysis based on combining condensed semantics lower bounds with upper bounds from algebraic mappings of related calculi already leads to a close and sound approximization. This approximization can be easily augmented with a manual analysis of few geometrically underconstrained cases and then yields a complete analysis of possible configurations in this oriented point framework. This for the first time enables sound standard QSTR constraint reasoning for the OPRA* calculus family.
Cite as

Reinhard Moratz, Leif Sabellek, and Thomas Schneider. Granular Spatial Calculi of Relative Directions or Movements with Parallelism: Consistent Account (Short Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 28:1-28:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{moratz_et_al:LIPIcs.COSIT.2019.28,
  author =	{Moratz, Reinhard and Sabellek, Leif and Schneider, Thomas},
  title =	{{Granular Spatial Calculi of Relative Directions or Movements with Parallelism: Consistent Account}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{28:1--28:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.28},
  URN =		{urn:nbn:de:0030-drops-111206},
  doi =		{10.4230/LIPIcs.COSIT.2019.28},
  annote =	{Keywords: qualitative spatial-temporal reasoning, composition table, condensed semantics, homomorphic embeddings}
}
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact