D. Niwinski: papers

Damian Niwiński

Some papers

The Probabilistic Rabin Tree Theorem (co-authors P.Parys and M.Skrzypczak), an extended version of the paper at LICS 2023.
On Guidable Index of Tree Automata (co-author M.Skrzypczak), MFCS 2021.
A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation (co-authors A.Arnold and P.Parys), CSL 2021.
Computing Measures of Weak-MSO Definable Sets of Trees (co-authors M.Przybyłko and M.Skrzypczak), ICALP 2020.
Contribution of Warsaw Logicians to Computational Logic, Axioms, 2016.
A simple indeterminate infinite game (co-author E.Kopczynski), draft, final version in the Festschrift of Victor Selivanov, 2012.
On topological completeness of regular tree languages (co-author H.Michalewski), draft, final version in the Festschrift of Dexter Kozen, 2012.
On the separation question for tree languages (co-authors A. Arnold and H.Michalewski), STACS 2012, extended draft, final version in TOCS 2013.
On the Borel complexity of MSO definable sets of branches (co-authors M.Bojanczyk, A.Rabinovich, A.Radziwonczyk-Syta,M.Skrzypczak), final version in Fundamenta Informaticae 98(4), pp. 337-349, 2010.
On the Borel inseparability of game tree languages (co-authors S.Hummel and H.Michalewski), STACS 2009.
Continuous separation of game languages (co-author A.Arnold), draft, final version in Fundamenta Informaticae Vol. 81 Issue 1-3, pp. 19-28, 2008.
On the topological complexity of tree languages (co-authors A.Arnold, J.Duparc, and F.Murlak), in: Logic and automata: History and Perspectives, (J. Flum, E. Graedel, T. Wilke, eds.), Amsterdam University Press, 2007, pp. 9-28, 2007.
Computing flat vectorial Boolean fixed points, unpublished manuscript, 2006.
Unsafe grammars and panic automata (co-authors T.Knapik, P.Urzyczyn, I.Walukiewicz), draft,
(a shorten version presented to ICALP 2005).
On the positional determinacy of edge--labeled games (co-author T.Colcombet), draft, 2004, final version in TCS 352 (1--3) (2006).
Deciding Nondeterministic Hierarchy of Deterministic Tree Automata (co-author I.Walukiewicz), draft, presented to WOLLIC 2004.
A gap property of deterministic tree languages (co-author I.Walukiewicz), draft, final version in TCS 303 (2003).
Mu-calculus via games (extended abstract), draft, final version presented to CSL 2002.
Higher-order pushdown trees are easy, (co-authors T.Knapik and P.Urzyczyn), draft, final version presented to FOSSACS 2002.
Deciding monadic theories of hyperalgebraic trees (co-authors T.Knapik and P.Urzyczyn), draft, final version presented to TLCA 2001.
Relating hierarchies of word and tree automata (co-author I. Walukiewicz), draft, final version presented to STACS 1998.
On Distributive Fixpoint Expressions (1998, co-author H.Seidl), draft, final version in RAIRO ITA 33(4/5): 427-446 (1999).
Fixed point characterization of infinite behavior of finite state systems [abstract], [draft], final version published in TCS 189 (1997).
Wazne przyklady w teorii zlozonosci (in Polish) [ps]
Algorytmy i zlozonosc obliczeniowa (in Polish) [ps]

The book: Rudiments of mu-calculus (co-author: Andre Arnold), Elsevier 2001.