3 Search Results for "Przybylko, Marcin"


Document
Answer Counting Under Guarded TGDs

Authors: Cristina Feier, Carsten Lutz, and Marcin Przybyłko

Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)


Abstract
We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language, respectively. Our main result is a classification according to whether answer counting is fixed-parameter tractable (FPT), W[1]-equivalent, #W[1]-equivalent, #W[2]-hard, or #A[2]-equivalent, lifting a recent classification for UCQs without ontologies and constraints due to Dell et al. [Holger Dell et al., 2019]. The classification pertains to various structural measures, namely treewidth, contract treewidth, starsize, and linked matching number. Our results rest on the assumption that the arity of relation symbols is bounded by a constant and, in the case of ontology-mediated querying, that all symbols from the ontology and query can occur in the data (so-called full data schema). We also study the meta-problems for the mentioned structural measures, that is, to decide whether a given ontology-mediated query or constraint-query specification is equivalent to one for which the structural measure is bounded.

Cite as

Cristina Feier, Carsten Lutz, and Marcin Przybyłko. Answer Counting Under Guarded TGDs. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{feier_et_al:LIPIcs.ICDT.2021.11,
  author =	{Feier, Cristina and Lutz, Carsten and Przyby{\l}ko, Marcin},
  title =	{{Answer Counting Under Guarded TGDs}},
  booktitle =	{24th International Conference on Database Theory (ICDT 2021)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-179-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{186},
  editor =	{Yi, Ke and Wei, Zhewei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.11},
  URN =		{urn:nbn:de:0030-drops-137195},
  doi =		{10.4230/LIPIcs.ICDT.2021.11},
  annote =	{Keywords: Ontology-Mediated Querying, Querying under Constraints, Answer Counting, Parameterized Complexity}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
Computing Measures of Weak-MSO Definable Sets of Trees

Authors: Damian Niwiński, Marcin Przybyłko, and Michał Skrzypczak

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
This work addresses the problem of computing measures of recognisable sets of infinite trees. An algorithm is provided to compute the probability measure of a tree language recognisable by a weak alternating automaton, or equivalently definable in weak monadic second-order logic. The measure is the uniform coin-flipping measure or more generally it is generated by a branching stochastic process. The class of tree languages in consideration, although smaller than all regular tree languages, comprises in particular the languages definable in the alternation-free μ-calculus or in temporal logic CTL. Thus, the new algorithm may enhance the toolbox of probabilistic model checking.

Cite as

Damian Niwiński, Marcin Przybyłko, and Michał Skrzypczak. Computing Measures of Weak-MSO Definable Sets of Trees. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 136:1-136:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{niwinski_et_al:LIPIcs.ICALP.2020.136,
  author =	{Niwi\'{n}ski, Damian and Przyby{\l}ko, Marcin and Skrzypczak, Micha{\l}},
  title =	{{Computing Measures of Weak-MSO Definable Sets of Trees}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{136:1--136:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.136},
  URN =		{urn:nbn:de:0030-drops-125430},
  doi =		{10.4230/LIPIcs.ICALP.2020.136},
  annote =	{Keywords: infinite trees, weak alternating automata, coin-flipping measure}
}
Document
On the Complexity of Branching Games with Regular Conditions

Authors: Marcin Przybylko and Michal Skrzypczak

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


Abstract
Infinite duration games with regular conditions are one of the crucial tools in the areas of verification and synthesis. In this paper we consider a branching variant of such games - the game contains branching vertices that split the play into two independent sub-games. Thus, a play has the form of~an~infinite tree. The winner of the play is determined by a winning condition specified as a set of infinite trees. Games of this kind were used by Mio to provide a game semantics for the probabilistic mu-calculus. He used winning conditions defined in terms of parity games on trees. In this work we consider a more general class of winning conditions, namely those definable by finite automata on infinite trees. Our games can be seen as a branching-time variant of the stochastic games on graphs. We address the question of determinacy of a branching game and the problem of computing the optimal game value for each of the players. We consider both the stochastic and non-stochastic variants of the games. The questions under consideration are parametrised by the family of strategies we allow: either mixed, behavioural, or pure. We prove that in general, branching games are not determined under mixed strategies. This holds even for topologically simple winning conditions (differences of two open sets) and non-stochastic arenas. Nevertheless, we show that the games become determined under mixed strategies if we restrict the winning conditions to open sets of trees. We prove that the problem of comparing the game value to a rational threshold is undecidable for branching games with regular conditions in all non-trivial stochastic cases. In the non-stochastic cases we provide exact bounds on the complexity of the problem. The only case left open is the 0-player stochastic case, i.e. the problem of computing the measure of a given regular language of infinite trees.

Cite as

Marcin Przybylko and Michal Skrzypczak. On the Complexity of Branching Games with Regular Conditions. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{przybylko_et_al:LIPIcs.MFCS.2016.78,
  author =	{Przybylko, Marcin and Skrzypczak, Michal},
  title =	{{On the Complexity of Branching Games with Regular Conditions}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{78:1--78: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.78},
  URN =		{urn:nbn:de:0030-drops-64865},
  doi =		{10.4230/LIPIcs.MFCS.2016.78},
  annote =	{Keywords: stochastic games, meta-parity games, infinite trees, regular languages, parity automata}
}
  • Refine by Author
  • 2 Przybyłko, Marcin
  • 1 Feier, Cristina
  • 1 Lutz, Carsten
  • 1 Niwiński, Damian
  • 1 Przybylko, Marcin
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Markov processes
  • 1 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Database theory

  • Refine by Keyword
  • 2 infinite trees
  • 1 Answer Counting
  • 1 Ontology-Mediated Querying
  • 1 Parameterized Complexity
  • 1 Querying under Constraints
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2016
  • 1 2020
  • 1 2021

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