14 Search Results for "Kr�tzsch, Markus"


Document
Tuple-Generating Dependencies Capture Complex Values

Authors: Maximilian Marx and Markus Krötzsch

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)


Abstract
We formalise a variant of Datalog that allows complex values constructed by nesting elements of the input database in sets and tuples. We study its complexity and give a translation into sets of tuple-generating dependencies (TGDs) for which the standard chase terminates on any input database. We identify a fragment for which reasoning is tractable. As membership is undecidable for this fragment, we develop decidable sufficient conditions.

Cite as

Maximilian Marx and Markus Krötzsch. Tuple-Generating Dependencies Capture Complex Values. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{marx_et_al:LIPIcs.ICDT.2022.13,
  author =	{Marx, Maximilian and Kr\"{o}tzsch, Markus},
  title =	{{Tuple-Generating Dependencies Capture Complex Values}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.13},
  URN =		{urn:nbn:de:0030-drops-158876},
  doi =		{10.4230/LIPIcs.ICDT.2022.13},
  annote =	{Keywords: terminating standard chase, existential rules, Datalog, complexity}
}
Document
Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras

Authors: Markus Bläser and Vladimir Lysikov

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
Determining the exponent of matrix multiplication ω is one of the central open problems in algebraic complexity theory. All approaches to design fast matrix multiplication algorithms follow the following general pattern: We start with one "efficient" tensor T of fixed size and then we use a way to get a large matrix multiplication out of a large tensor power of T. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over C: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. To obtain our result, we relate irreversibility to asymptotic slice rank and instability of tensors and prove that the instability of block tensors can often be decided by looking only on the sizes of nonzero blocks.

Cite as

Markus Bläser and Vladimir Lysikov. Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.MFCS.2020.17,
  author =	{Bl\"{a}ser, Markus and Lysikov, Vladimir},
  title =	{{Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.17},
  URN =		{urn:nbn:de:0030-drops-126869},
  doi =		{10.4230/LIPIcs.MFCS.2020.17},
  annote =	{Keywords: Tensors, Slice rank, Barriers, Matrix multiplication, GIT stability}
}
Document
Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups

Authors: Markus Lohrey and Georg Zetzsche

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
We prove that the power word problem for the solvable Baumslag-Solitar groups BS(1,q) = ⟨ a,t ∣ t a t^{-1} = a^q ⟩ can be solved in TC⁰. In the power word problem, the input consists of group elements g₁, …, g_d and binary encoded integers n₁, …, n_d and it is asked whether g₁^{n₁} ⋯ g_d^{n_d} = 1 holds. Moreover, we prove that the knapsack problem for BS(1,q) is NP-complete. In the knapsack problem, the input consists of group elements g₁, …, g_d,h and it is asked whether the equation g₁^{x₁} ⋯ g_d^{x_d} = h has a solution in ℕ^d.

Cite as

Markus Lohrey and Georg Zetzsche. Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{lohrey_et_al:LIPIcs.MFCS.2020.67,
  author =	{Lohrey, Markus and Zetzsche, Georg},
  title =	{{Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{67:1--67:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.67},
  URN =		{urn:nbn:de:0030-drops-127364},
  doi =		{10.4230/LIPIcs.MFCS.2020.67},
  annote =	{Keywords: computational group theory, matrix problems, Baumslag-Solitar groups}
}
Document
All Growth Rates of Abelian Exponents Are Attained by Infinite Binary Words

Authors: Jarkko Peltomäki and Markus A. Whiteland

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
We consider repetitions in infinite words by making a novel inquiry to the maximum eventual growth rate of the exponents of abelian powers occurring in an infinite word. Given an increasing, unbounded function f: ℕ → ℝ, we construct an infinite binary word whose abelian exponents have limit superior growth rate f. As a consequence, we obtain that every nonnegative real number is the critical abelian exponent of some infinite binary word.

Cite as

Jarkko Peltomäki and Markus A. Whiteland. All Growth Rates of Abelian Exponents Are Attained by Infinite Binary Words. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 79:1-79:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{peltomaki_et_al:LIPIcs.MFCS.2020.79,
  author =	{Peltom\"{a}ki, Jarkko and Whiteland, Markus A.},
  title =	{{All Growth Rates of Abelian Exponents Are Attained by Infinite Binary Words}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{79:1--79:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.79},
  URN =		{urn:nbn:de:0030-drops-127481},
  doi =		{10.4230/LIPIcs.MFCS.2020.79},
  annote =	{Keywords: abelian equivalence, abelian power, abelian critical exponent}
}
Document
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

Authors: Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets. A blocking set is a set of vertices such that no optimal vertex cover contains all vertices in the blocking set, and the study of minimal blocking sets played implicit and explicit roles in many existing results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class ?, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class ?, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes ?, including the class ?_{LP} of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or ?_{LP} graphs.

Cite as

Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{hols_et_al:LIPIcs.STACS.2020.36,
  author =	{Hols, Eva-Maria C. and Kratsch, Stefan and Pieterse, Astrid},
  title =	{{Elimination Distances, Blocking Sets, and Kernels for Vertex Cover}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.36},
  URN =		{urn:nbn:de:0030-drops-118974},
  doi =		{10.4230/LIPIcs.STACS.2020.36},
  annote =	{Keywords: Vertex Cover, kernelization, blocking sets, elimination distance, structural parameters}
}
Document
Invited Talk
The Power of the Terminating Chase (Invited Talk)

Authors: Markus Krötzsch, Maximilian Marx, and Sebastian Rudolph

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)


Abstract
The chase has become a staple of modern database theory with applications in data integration, query optimisation, data exchange, ontology-based query answering, and many other areas. Most application scenarios and implementations require the chase to terminate and produce a finite universal model, and a large arsenal of sufficient termination criteria is available to guarantee this (generally undecidable) condition. In this invited tutorial, we therefore ask about the expressive power of logical theories for which the chase terminates. Specifically, which database properties can be recognised by such theories, i.e., which Boolean queries can they realise? For the skolem (semi-oblivious) chase, and almost any known termination criterion, this expressivity is just that of plain Datalog. Surprisingly, this limitation of most prior research does not apply to the chase in general. Indeed, we show that standard - chase terminating theories can realise queries with data complexities ranging from PTime to non-elementary that are out of reach for the terminating skolem chase. A "Datalog-first" standard chase that prioritises applications of rules without existential quantifiers makes modelling simpler - and we conjecture: computationally more efficient. This is one of the many open questions raised by our insights, and we conclude with an outlook on the research opportunities in this area.

Cite as

Markus Krötzsch, Maximilian Marx, and Sebastian Rudolph. The Power of the Terminating Chase (Invited Talk). In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{krotzsch_et_al:LIPIcs.ICDT.2019.3,
  author =	{Kr\"{o}tzsch, Markus and Marx, Maximilian and Rudolph, Sebastian},
  title =	{{The Power of the Terminating Chase}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.3},
  URN =		{urn:nbn:de:0030-drops-103057},
  doi =		{10.4230/LIPIcs.ICDT.2019.3},
  annote =	{Keywords: Existential rules, Tuple-generating dependencies, all-instances chase termination, expressive power, data complexity}
}
Document
Enumeration Complexity of Conjunctive Queries with Functional Dependencies

Authors: Nofar Carmeli and Markus Kröll

Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)


Abstract
We study the complexity of enumerating the answers of Conjunctive Queries (CQs) in the presence of Functional Dependencies (FDs). Our focus is on the ability to list output tuples with a constant delay in between, following a linear-time preprocessing. A known dichotomy classifies the acyclic self-join-free CQs into those that admit such enumeration, and those that do not. However, this classification no longer holds in the common case where the database exhibits dependencies among attributes. That is, some queries that are classified as hard are in fact tractable if dependencies are accounted for. We establish a generalization of the dichotomy to accommodate FDs; hence, our classification determines which combination of a CQ and a set of FDs admits constant-delay enumeration with a linear-time preprocessing. In addition, we generalize a hardness result for cyclic CQs to accommodate a common type of FDs. Further conclusions of our development include a dichotomy for enumeration with linear delay, and a dichotomy for CQs with disequalities. Finally, we show that all our results apply to the known class of "cardinality dependencies" that generalize FDs (e.g., by stating an upper bound on the number of genres per movies, or friends per person).

Cite as

Nofar Carmeli and Markus Kröll. Enumeration Complexity of Conjunctive Queries with Functional Dependencies. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{carmeli_et_al:LIPIcs.ICDT.2018.11,
  author =	{Carmeli, Nofar and Kr\"{o}ll, Markus},
  title =	{{Enumeration Complexity of Conjunctive Queries with Functional Dependencies}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Kimelfeld, Benny and Amsterdamer, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.11},
  URN =		{urn:nbn:de:0030-drops-85988},
  doi =		{10.4230/LIPIcs.ICDT.2018.11},
  annote =	{Keywords: Enumeration, Complexity, CQs}
}
Document
Preserving Constraints with the Stable Chase

Authors: David Carral, Markus Krötzsch, Maximilian Marx, Ana Ozaki, and Sebastian Rudolph

Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)


Abstract
Conjunctive query answering over databases with constraints – also known as (tuple-generating) dependencies – is considered a central database task. To this end, several versions of a construction called chase have been described. Given a set Sigma of dependencies, it is interesting to ask which constraints not contained in Sigma that are initially satisfied in a given database instance are preserved when computing a chase over Sigma. Such constraints are an example for the more general class of incidental constraints, which when added to Sigma as new dependencies do not affect certain answers and might even speed up query answering. After formally introducing incidental constraints, we show that deciding incidentality is undecidable for tuple-generating dependencies, even in cases for which query entailment is decidable. For dependency sets with a finite universal model, the core chase can be used to decide incidentality. For the infinite case, we propose the stable chase, which generalises the core chase, and study its relation to incidental constraints.

Cite as

David Carral, Markus Krötzsch, Maximilian Marx, Ana Ozaki, and Sebastian Rudolph. Preserving Constraints with the Stable Chase. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{carral_et_al:LIPIcs.ICDT.2018.12,
  author =	{Carral, David and Kr\"{o}tzsch, Markus and Marx, Maximilian and Ozaki, Ana and Rudolph, Sebastian},
  title =	{{Preserving Constraints with the Stable Chase}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Kimelfeld, Benny and Amsterdamer, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.12},
  URN =		{urn:nbn:de:0030-drops-86015},
  doi =		{10.4230/LIPIcs.ICDT.2018.12},
  annote =	{Keywords: Incidental constraints, Tuple-generating dependencies, Infinite core chase, Universal Model, BCQ entailment}
}
Document
On the Complexity of Universality for Partially Ordered NFAs

Authors: Markus Krötzsch, Tomás Masopust, and Michaël Thomazo

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, i.e., for which cycles occur only in the form of self-loops on a single state. A poNFA is universal if it accepts all words over its input alphabet. Deciding universality is \PSpace-complete for poNFAs, and we show that this remains true even when restricting to a fixed alphabet. This is nontrivial since standard encodings of alphabet symbols in, e.g., binary can turn self-loops into longer cycles. A lower coNP-complete complexity bound can be obtained if we require that all self-loops in the poNFA are deterministic, in the sense that the symbol read in the loop cannot occur in any other transition from that state. We find that such restricted poNFAs (rpoNFAs) characterise the class of R-trivial languages, and we establish the complexity of deciding if the language of an NFA is R-trivial. Nevertheless, the limitation to fixed alphabets turns out to be essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSPACE-complete. Our results also prove the complexity of the inclusion and equivalence problems, since universality provides the lower bound, while the upper bound is mostly known or proved in the paper.

Cite as

Markus Krötzsch, Tomás Masopust, and Michaël Thomazo. On the Complexity of Universality for Partially Ordered NFAs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{krotzsch_et_al:LIPIcs.MFCS.2016.61,
  author =	{Kr\"{o}tzsch, Markus and Masopust, Tom\'{a}s and Thomazo, Micha\"{e}l},
  title =	{{On the Complexity of Universality for Partially Ordered NFAs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.61},
  URN =		{urn:nbn:de:0030-drops-64738},
  doi =		{10.4230/LIPIcs.MFCS.2016.61},
  annote =	{Keywords: automata, nondeterminism, partial order, universality}
}
Document
On the Complexity of Enumerating the Answers to Well-designed Pattern Trees

Authors: Markus Kröll, Reinhard Pichler, and Sebastian Skritek

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)


Abstract
Well-designed pattern trees (wdPTs) have been introduced as an extension of conjunctive queries to allow for partial matching - analogously to the OPTIONAL operator of the semantic web query language SPARQL. Several computational problems of wdPTs have been studied in recent years, such as the evaluation problem in various settings, the counting problem, as well as static analysis tasks including the containment and equivalence problems. Also restrictions needed to achieve tractability of these tasks have been proposed. In contrast, the problem of enumerating the answers to a wdPT has been largely ignored so far. In this work, we embark on a systematic study of the complexity of the enumeration problem of wdPTs. As our main result, we identify several tractable and intractable cases of this problem both from a classical complexity point of view and from a parameterized complexity point of view.

Cite as

Markus Kröll, Reinhard Pichler, and Sebastian Skritek. On the Complexity of Enumerating the Answers to Well-designed Pattern Trees. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{kroll_et_al:LIPIcs.ICDT.2016.22,
  author =	{Kr\"{o}ll, Markus and Pichler, Reinhard and Skritek, Sebastian},
  title =	{{On the Complexity of Enumerating the Answers to Well-designed Pattern Trees}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.22},
  URN =		{urn:nbn:de:0030-drops-57912},
  doi =		{10.4230/LIPIcs.ICDT.2016.22},
  annote =	{Keywords: SPARQL, Pattern Trees, CQs, Enumeration, Complexity}
}
Document
Approximate OWL Instance Retrieval with SCREECH

Authors: Pascal Hitzler, Markus Krötzsch, Sebastian Rudolph, and Tuvshintur Tserendorj

Published in: Dagstuhl Seminar Proceedings, Volume 8091, Logic and Probability for Scene Interpretation (2008)


Abstract
With the increasing interest in expressive ontologies for the Semantic Web, it is critical to develop scalable and efficient ontology reasoning techniques that can properly cope with very high data volumes. For certain application domains, approximate reasoning solutions, which trade soundness or completeness for increased reasoning speed, will help to deal with the high computational complexities which state of the art ontology reasoning tools have to face. In this paper, we present a comprehensive overview of the SCREECH approach to approximate instance retrieval with OWL ontologies, which is based on the KAON2 algorithms, facilitating a compilation of OWL DL TBoxes into Datalog, which is tractable in terms of data complexity. We present three different instantiations of the Screech approach, and report on experiments which show that the gain in efficiency outweighs the number of introduced mistakes in the reasoning process.

Cite as

Pascal Hitzler, Markus Krötzsch, Sebastian Rudolph, and Tuvshintur Tserendorj. Approximate OWL Instance Retrieval with SCREECH. In Logic and Probability for Scene Interpretation. Dagstuhl Seminar Proceedings, Volume 8091, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hitzler_et_al:DagSemProc.08091.3,
  author =	{Hitzler, Pascal and Kr\"{o}tzsch, Markus and Rudolph, Sebastian and Tserendorj, Tuvshintur},
  title =	{{Approximate OWL Instance Retrieval with SCREECH}},
  booktitle =	{Logic and Probability for Scene Interpretation},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8091},
  editor =	{Anthony G. Cohn and David C. Hogg and Ralf M\"{o}ller and Bernd Neumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08091.3},
  URN =		{urn:nbn:de:0030-drops-16157},
  doi =		{10.4230/DagSemProc.08091.3},
  annote =	{Keywords: Description logics, automated reasoning, approximate reasoning, Horn logic}
}
Document
C-XSC and Closely Related Software Packages

Authors: Werner Hofschuster, Walter Krämer, and Markus Neher

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
C-XSC and Closely Related Software Packages

Cite as

Werner Hofschuster, Walter Krämer, and Markus Neher. C-XSC and Closely Related Software Packages. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hofschuster_et_al:DagSemProc.08021.7,
  author =	{Hofschuster, Werner and Kr\"{a}mer, Walter and Neher, Markus},
  title =	{{C-XSC and Closely Related Software Packages}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.7},
  URN =		{urn:nbn:de:0030-drops-14425},
  doi =		{10.4230/DagSemProc.08021.7},
  annote =	{Keywords: Mathematical software, reliable computing, C-XSC, CoStLy, ACETAF}
}
Document
Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments

Authors: Markus Grimmer

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
There is a broad range of packages and libraries for verified numerical computation. C-XSC is a library combining one of the most extensive sets of functions and operations on the one hand with a wide range of applications and special features on the other hand. As such it is an important task both to make use of its existing capabilities in applications and to develop further extensions giving access to additional areas and environments. In this talk, we present some examples of extensions for C-XSC that have been developed lately. Among these are extensions that give access to further hardware and software environments as well as applications making use of these possibilities. Software libraries for interval computation always imply great computation effort: One way to reduce computation times is the development of parallel methods to make use of parallel hardware. For this, it is important that the features and data types of the used library can be easily used in parallel programs. An MPI package for C-XSC data types allows to easily use C-XSC in parallel programs without bothering about the internal structure of data types. Another extension of C-XSC, the C-XSC Taylor arithmetic, is also covered by the MPI package. Parallel verified linear system solvers based on the package are available as well, and further development has been and is being done to integrate more efficient methods for interval linear system solution. One application making use of the mentioned extensions is a parallel verified Fredholm integral equation solver. Some results are given to demonstrate the reduction of computation time and, at the same time, the accuracy gain that can be obtained using the increased computation power. Naturally, hardware interval support would offer still more possibilities towards optimal performance of verified numerical software. Another possibility to extend the range of C-XSC is to make results available for further computations in other software environments as, for example, computer algebra packages. An example of this is presented for the Maple interval package intpakX. This kind of interfaces also allows the user to get access to further platforms like operating systems, compilers or even hardware. References: [1] ALiCEnext: http://www.alicenext.uni-wuppertal.de. [2] Blomquist, F.; Hofschuster, W.; Kraemer, W.: Real and Complex Taylor Arithmetic in C-XSC. Preprint BUW-WRSWT 2005/4, University of Wuppertal, 2005. [3] Grimmer, M.; Kraemer, W.: An MPI Extension for Verified Numerical Computations in Parallel Environments. In: Int. Conf. on Scientific Computing (CSC’07, Worldcomp’07) Las Vegas, June 25-28, 2007, Proceedings pp. 111-117, Arabnia et al. (eds.), 2007. [4] Grimmer, M.: An MPI Extension for the Use of C-XSC in Parallel Environments. Preprint BUW-WRSWT 2005/3, University of Wuppertal, 2005. [5] Grimmer, M.: Selbstverifizierende mathematische Softwarewerkzeuge im High Performance Computing. Dissertation, Logos Verlag, Berlin, 2007. [6] Grimmer, M.: Interval Arithmetic in Maple with intpakX. In: PAMM - Proceedings in Applied Mathematics and Mechanics, Vol. 2, Nr. 1, p. 442-443, Wiley-InterScience, 2003. [7] Hofschuster, W.; Kraemer, W.: C-XSC 2.0: A C++ Library for Extended Scientific Computing. Numerical Software with Result Verification, Lecture Notes in Computer Science, Volume 2991/2004, Springer-Verlag, Heidelberg, pp. 15 - 35, 2004. [8] Klein, W.: Enclosure Methods for Linear and Nonlinear Systems of Fredholm Integral Equations of the Second Kind. In: Adams, Kulisch: Scientific Computing with Result Verification, Academic Press, 1993.

Cite as

Markus Grimmer. Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{grimmer:DagSemProc.08021.10,
  author =	{Grimmer, Markus},
  title =	{{Extending the Range of C-XSC: Some Tools and Applications for the use in Parallel and other Environments}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.10},
  URN =		{urn:nbn:de:0030-drops-14416},
  doi =		{10.4230/DagSemProc.08021.10},
  annote =	{Keywords: C-XSC, Integral Equations, Interval Arithmetic, Maple, MPI, Parallel Environment, Taylor Arithmetic, Verified Linear System Solver.}
}
Document
The CoStLy C++ Class Library

Authors: Markus Neher

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
CoStLy (ul{Co}mplex ul{St}andard Functions ul{L}ibrarul{y}) has been developed as a C++ class library for the validated computation of function values and of ranges of complex standard functions. If performed in exact arithmetic, the inclusion functions for principal branches compute optimal range bounds. For the sake of accuracy, a major effort has been made in the implementation of the algorithms in floating point arithmetic to eliminate all intermediate expressions subject to numerical overflow, underflow, or cancellation. The CoStLy library has been extensively tested for arguments with absolute values ranging from 1.0E-300 to 1.0E+300. For most arguments, the computed bounds for function values are highly accurate. In many test cases, the observed precision of the result was about 50 correct bits (out of the 53 bits available in IEEE 754 floating point arithmetic) for point arguments.

Cite as

Markus Neher. The CoStLy C++ Class Library. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{neher:DagSemProc.08021.19,
  author =	{Neher, Markus},
  title =	{{The CoStLy C++ Class Library}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.19},
  URN =		{urn:nbn:de:0030-drops-14495},
  doi =		{10.4230/DagSemProc.08021.19},
  annote =	{Keywords: Complex interval arithmetic, inclusion functions}
}
  • Refine by Author
  • 5 Krötzsch, Markus
  • 3 Marx, Maximilian
  • 3 Rudolph, Sebastian
  • 2 Kröll, Markus
  • 2 Neher, Markus
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Complexity theory and logic
  • 2 Theory of computation → Logic and databases
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 2 C-XSC
  • 2 CQs
  • 2 Complexity
  • 2 Enumeration
  • 2 Tuple-generating dependencies
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 4 2008
  • 4 2020
  • 2 2016
  • 2 2018
  • 1 2019
  • Show More...

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