Search Results

Documents authored by Niwinski, Damian

Found 2 Possible Name Variants:

Niwinski, Damian

Document
DOI: 10.4230/LIPIcs.MFCS.2021.81
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
DOI: 10.4230/LIPIcs.CSL.2021.9
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
DOI: 10.4230/LIPIcs.ICALP.2020.136
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
DOI: 10.4230/LIPIcs.CSL.2013.1
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
DOI: 10.4230/LIPIcs.CSL.2012.1
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
DOI: 10.4230/LIPIcs.STACS.2012.396
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
DOI: 10.4230/LIPIcs.STACS.2009.1849
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}
}

Niwiński, Damian

Document
DOI: 10.4230/LIPIcs.MFCS.2021.81
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
DOI: 10.4230/LIPIcs.CSL.2021.9
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
DOI: 10.4230/LIPIcs.ICALP.2020.136
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
DOI: 10.4230/LIPIcs.CSL.2013.1
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
DOI: 10.4230/LIPIcs.CSL.2012.1
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
DOI: 10.4230/LIPIcs.STACS.2012.396
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
DOI: 10.4230/LIPIcs.STACS.2009.1849
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}
}
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