3 Search Results for "K�tzing, Timo"

Document
DOI: 10.4230/LIPIcs.ICDT.2023.10
Diversity of Answers to Conjunctive Queries

Authors: Timo Camillo Merkl, Reinhard Pichler, and Sebastian Skritek

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
Enumeration problems aim at outputting, without repetition, the set of solutions to a given problem instance. However, outputting the entire solution set may be prohibitively expensive if it is too big. In this case, outputting a small, sufficiently diverse subset of the solutions would be preferable. This leads to the Diverse-version of the original enumeration problem, where the goal is to achieve a certain level d of diversity by selecting k solutions. In this paper, we look at the Diverse-version of the query answering problem for Conjunctive Queries and extensions thereof. That is, we study the problem if it is possible to achieve a certain level d of diversity by selecting k answers to the given query and, in the positive case, to actually compute such k answers.
Cite as

Timo Camillo Merkl, Reinhard Pichler, and Sebastian Skritek. Diversity of Answers to Conjunctive Queries. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{merkl_et_al:LIPIcs.ICDT.2023.10,
  author =	{Merkl, Timo Camillo and Pichler, Reinhard and Skritek, Sebastian},
  title =	{{Diversity of Answers to Conjunctive Queries}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.10},
  URN =		{urn:nbn:de:0030-drops-177529},
  doi =		{10.4230/LIPIcs.ICDT.2023.10},
  annote =	{Keywords: Query Answering, Diversity of Solutions, Complexity, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.47
Towards an Atlas of Computational Learning Theory

Authors: Timo Kötzing and Martin Schirneck

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
A major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about trade-offs between learning restrictions and, more generally, learning settings; furthermore, they inform about what restrictions can be observed without losing learning power. With this paper we propose that one main focus of future research in Computational Learning should be on a structured approach to determine the relations of different learning criteria. In particular, we propose that, for small sets of learning criteria, all pairwise relations should be determined; these relations can then be easily depicted as a map, a diagram detailing the relations. Once we have maps for many relevant sets of learning criteria, the collection of these maps is an Atlas of Computational Learning Theory, informing at a glance about the landscape of computational learning just as a geographical atlas informs about the earth. In this paper we work toward this goal by providing three example maps, one pertaining to partially set-driven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure.
Cite as

Timo Kötzing and Martin Schirneck. Towards an Atlas of Computational Learning Theory. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kotzing_et_al:LIPIcs.STACS.2016.47,
  author =	{K\"{o}tzing, Timo and Schirneck, Martin},
  title =	{{Towards an Atlas of Computational Learning Theory}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.47},
  URN =		{urn:nbn:de:0030-drops-57483},
  doi =		{10.4230/LIPIcs.STACS.2016.47},
  annote =	{Keywords: computational learning, language learning, partially set-driven learning, strongly monotone learning}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.494
A Solution to Wiehagen's Thesis

Authors: Timo Kötzing

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
Wiehagen's Thesis in Inductive Inference (1991) essentially states that, for each learning criterion, learning can be done in a normalized, enumerative way. The thesis was not a formal statement and thus did not allow for a formal proof, but support was given by examples of a number of different learning criteria that can be learned enumeratively. Building on recent formalizations of learning criteria, we are now able to formalize Wiehagen's Thesis. We prove the thesis for a wide range of learning criteria, including many popular criteria from the literature. We also show the limitations of the thesis by giving four learning criteria for which the thesis does not hold (and, in two cases, was probably not meant to hold). Beyond the original formulation of the thesis, we also prove stronger versions which allow for many corollaries relating to strongly decisive and conservative learning.
Cite as

Timo Kötzing. A Solution to Wiehagen's Thesis. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 494-505, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kotzing:LIPIcs.STACS.2014.494,
  author =	{K\"{o}tzing, Timo},
  title =	{{A Solution to Wiehagen's Thesis}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{494--505},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.494},
  URN =		{urn:nbn:de:0030-drops-44823},
  doi =		{10.4230/LIPIcs.STACS.2014.494},
  annote =	{Keywords: Algorithmic Learning Theory, Wiehagen's Thesis, Enumeration Learning}
}
  • Refine by Author
  • 2 Kötzing, Timo
  • 1 Merkl, Timo Camillo
  • 1 Pichler, Reinhard
  • 1 Schirneck, Martin
  • 1 Skritek, Sebastian

  • Refine by Classification
  • 1 Information systems → Data management systems

  • Refine by Keyword
  • 1 Algorithmic Learning Theory
  • 1 Algorithms
  • 1 Complexity
  • 1 Diversity of Solutions
  • 1 Enumeration Learning
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2014
  • 1 2016
  • 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact