9 Search Results for "Niwiński, Damian"


Document
Parity Games of Bounded Tree-Depth

Authors: Konrad Staniszewski

Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)


Abstract
The exact complexity of solving parity games is a major open problem. Several authors have searched for efficient algorithms over specific classes of graphs. In particular, Obdržálek showed that for graphs of bounded tree-width or clique-width, the problem is in P, which was later improved by Ganardi, who showed that it is even in LOGCFL (with an additional assumption for clique-width case). Here we extend this line of research by showing that for graphs of bounded tree-depth the problem of solving parity games is in logspace uniform AC⁰. We achieve this by first considering a parameter that we obtain from a modification of clique-width, which we call shallow clique-width. We subsequently provide a suitable reduction.

Cite as

Konrad Staniszewski. Parity Games of Bounded Tree-Depth. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{staniszewski:LIPIcs.CSL.2023.33,
  author =	{Staniszewski, Konrad},
  title =	{{Parity Games of Bounded Tree-Depth}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.33},
  URN =		{urn:nbn:de:0030-drops-174942},
  doi =		{10.4230/LIPIcs.CSL.2023.33},
  annote =	{Keywords: Parity Games, Circuits, Tree-Depth, Clique-Width}
}
Document
On Guidable Index of Tree Automata

Authors: Damian Niwiński and Michał Skrzypczak

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
We study guidable parity automata over infinite trees introduced by Colcombet and Löding, which form an expressively complete subclass of all non-deterministic tree automata. We show that, for any non-deterministic automaton, an equivalent guidable automaton with the smallest possible index can be effectively found. Moreover, if an input automaton is of a special kind, i.e. it is deterministic or game automaton then a guidable automaton with an optimal index can be deterministic (respectively game) automaton as well. Recall that the problem whether an equivalent non-deterministic automaton with the smallest possible index can be effectively found is open, and a positive answer is known only in the case when an input automaton is a deterministic, or more generally, a game automaton.

Cite as

Damian Niwiński and Michał Skrzypczak. On Guidable Index of Tree Automata. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 81:1-81:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{niwinski_et_al:LIPIcs.MFCS.2021.81,
  author =	{Niwi\'{n}ski, Damian and Skrzypczak, Micha{\l}},
  title =	{{On Guidable Index of Tree Automata}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{81:1--81:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.81},
  URN =		{urn:nbn:de:0030-drops-145214},
  doi =		{10.4230/LIPIcs.MFCS.2021.81},
  annote =	{Keywords: guidable automata, index problem, \omega-regular games}
}
Document
A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation

Authors: André Arnold, Damian Niwiński, and Paweł Parys

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)


Abstract
We consider nested fixed-point expressions like μ z. ν y. μ x. f(x,y,z) evaluated over a finite lattice, and ask how many queries to a function f are needed to find the value. The previous upper bounds for a monotone function f of arity d over the lattice {0,1}ⁿ were of the order n^{𝒪(d)}, whereas a lower bound of Ω(n²/(lg n)) is known in case when at least one alternation between the least (μ) and the greatest (ν) fixed point occurs in the expression. Following a recent development for parity games, we show here that a quasi-polynomial number of queries is sufficient, namely n^{lg(d/lg n)+𝒪(1)}. The algorithm is an abstract version of several algorithms proposed recently by a number of authors, which involve (implicitly or explicitly) the structure of a universal tree. We then show a quasi-polynomial lower bound for the number of queries used by the algorithms in consideration.

Cite as

André Arnold, Damian Niwiński, and Paweł Parys. A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{arnold_et_al:LIPIcs.CSL.2021.9,
  author =	{Arnold, Andr\'{e} and Niwi\'{n}ski, Damian and Parys, Pawe{\l}},
  title =	{{A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.9},
  URN =		{urn:nbn:de:0030-drops-134430},
  doi =		{10.4230/LIPIcs.CSL.2021.9},
  annote =	{Keywords: Mu-calculus, Parity games, Quasi-polynomial time, Black-box algorithm}
}
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.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
The Ackermann Award 2013

Authors: Anuj Dawar, Thomas A. Henzinger, and Damian Niwiński

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)


Abstract
Report on the Ackermann Award 2013.

Cite as

Anuj Dawar, Thomas A. Henzinger, and Damian Niwiński. The Ackermann Award 2013. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2013.1,
  author =	{Dawar, Anuj and Henzinger, Thomas A. and Niwi\'{n}ski, Damian},
  title =	{{The Ackermann Award 2013}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{1--4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.1},
  URN =		{urn:nbn:de:0030-drops-41837},
  doi =		{10.4230/LIPIcs.CSL.2013.1},
  annote =	{Keywords: Ackermann award}
}
Document
The Ackermann Award 2012

Authors: Thierry Coquand, Anuj Dawar, and Damian Niwinski

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)


Abstract
Report on the Ackermann Award 2012.

Cite as

Thierry Coquand, Anuj Dawar, and Damian Niwinski. The Ackermann Award 2012. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{coquand_et_al:LIPIcs.CSL.2012.1,
  author =	{Coquand, Thierry and Dawar, Anuj and Niwinski, Damian},
  title =	{{The Ackermann Award 2012}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{1--5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.1},
  URN =		{urn:nbn:de:0030-drops-36575},
  doi =		{10.4230/LIPIcs.CSL.2012.1},
  annote =	{Keywords: Ackermann Award 2012}
}
Document
On the separation question for tree languages

Authors: André Arnold, Henryk Michalewski, and Damian Niwinski

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)


Abstract
We show that the separation property fails for the classes Sigma_n of the Rabin-Mostowski index hierarchy of alternating automata on infinite trees. This extends our previous result (obtained with Szczepan Hummel) on the failure of the separation property for the class Sigma_2 (i.e., for co-Buchi sets). It remains open whether the separation property does hold for the classes Pi_n of the index hierarchy. To prove our result, we first consider the Rabin-Mostowski index hierarchy of deterministic automata on infinite words, for which we give a complete answer (generalizing previous results of Selivanov): the separation property holds for Pi_n and fails for Sigma_n-classes. The construction invented for words turns out to be useful for trees via a suitable game.

Cite as

André Arnold, Henryk Michalewski, and Damian Niwinski. On the separation question for tree languages. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 396-407, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{arnold_et_al:LIPIcs.STACS.2012.396,
  author =	{Arnold, Andr\'{e} and Michalewski, Henryk and Niwinski, Damian},
  title =	{{On the separation question for tree languages}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{396--407},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.396},
  URN =		{urn:nbn:de:0030-drops-34156},
  doi =		{10.4230/LIPIcs.STACS.2012.396},
  annote =	{Keywords: Alternating automata on infinite trees, Index hierarchy, Separation property}
}
Document
On the Borel Inseparability of Game Tree Languages

Authors: Szczepan Hummel, Henryk Michalewski, and Damian Niwinski

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)


Abstract
The game tree languages can be viewed as an automata-theoretic counterpart of parity games on graphs. They witness the strictness of the index hierarchy of alternating tree automata, as well as the fixed-point hierarchy over binary trees. We consider a game tree language of the first non-trivial level, where Eve can force that 0 repeats from some moment on, and its dual, where Adam can force that 1 repeats from some moment on. Both these sets (which amount to one up to an obvious renaming) are complete in the class of co-analytic sets. We show that they cannot be separated by any Borel set, hence {\em a fortiori\/} by any weakly definable set of trees. This settles a case left open by L. Santocanale and A. Arnold, who have thoroughly investigated the separation property within the $\mu $-calculus and the automata index hierarchies. They showed that separability fails in general for non-deterministic automata of type $\Sigma^{\mu }_{n} $, starting from level $n=3$, while our result settles the missing case $n=2$.

Cite as

Szczepan Hummel, Henryk Michalewski, and Damian Niwinski. On the Borel Inseparability of Game Tree Languages. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 565-576, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{hummel_et_al:LIPIcs.STACS.2009.1849,
  author =	{Hummel, Szczepan and Michalewski, Henryk and Niwinski, Damian},
  title =	{{On the Borel Inseparability of Game Tree Languages}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{565--576},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1849},
  URN =		{urn:nbn:de:0030-drops-18493},
  doi =		{10.4230/LIPIcs.STACS.2009.1849},
  annote =	{Keywords: Tree automata, Separation property, Borel sets, Parity games}
}
Document
Topological Complexity of omega-Powers: Extended Abstract

Authors: Olivier Finkel and Dominique Lecomte

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
The operation of taking the omega-power $V^omega$ of a language $V$ is a fundamental operation over finitary languages leading to omega-languages. Since the set $X^omega$ of infinite words over a finite alphabet $X$ can be equipped with the usual Cantor topology, the question of the topological complexity of omega-powers of finitary languages naturally arises and has been posed by Damian Niwinski (1990), Pierre Simonnet (1992), and Ludwig Staiger (1997). We investigate the topological complexity of omega-powers. We prove the following very surprising results which show that omega-powers exhibit a great opological complexity: for each non-null countable ordinal $xi$, there exist some $Sigma^0_xi$-complete omega-powers, and some $Pi^0_xi$-complete omega-powers. On the other hand, the Wadge hierarchy is a great refinement of the Borel hierarchy, determined by Bill Wadge. We show that, for each ordinal $xi$ greater than or equal to 3, there are uncountably many Wadge degrees of omega-powers of Borel rank $xi +1$. Using tools of effective descriptive set theory, we prove some effective versions of the above results.

Cite as

Olivier Finkel and Dominique Lecomte. Topological Complexity of omega-Powers: Extended Abstract. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{finkel_et_al:DagSemProc.08271.7,
  author =	{Finkel, Olivier and Lecomte, Dominique},
  title =	{{Topological Complexity of omega-Powers: Extended Abstract}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.7},
  URN =		{urn:nbn:de:0030-drops-16505},
  doi =		{10.4230/DagSemProc.08271.7},
  annote =	{Keywords: Infinite words, omega-languages, omega-powers, Cantor topology, topological complexity, Borel sets, Borel ranks, complete sets, Wadge hierarchy, Wadge}
}
  • Refine by Author
  • 4 Niwiński, Damian
  • 3 Niwinski, Damian
  • 2 Arnold, André
  • 2 Dawar, Anuj
  • 2 Michalewski, Henryk
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Automata over infinite objects
  • 1 Mathematics of computing → Markov processes
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Logic and verification

  • Refine by Keyword
  • 2 Borel sets
  • 2 Parity games
  • 2 Separation property
  • 1 Ackermann Award 2012
  • 1 Ackermann award
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 2 2012
  • 2 2021
  • 1 2008
  • 1 2009
  • 1 2013
  • 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