Igor Walukiewicz: publications

Wreath Products of Forest Algebras, with Applications to Tree Logics
with Mikolaj Bojanczyk and Howard Straubing. Proceedings of LICS'09 PDF

Weak Alternating Timed Automata
with Pawel Parys. Proceedings of ICALP'09, LNCS, pp. 273--284 PDF (Long version PDF at HAL )

A look at the control of asynchronous automata
with Anca Muscholl and Marc Zeitoun, in Perspectives in Concurrency Theory, K. Lodaya, M. Mukund, R. Ramanujam (Ed.) (2008) 356--371 PDF

Nondeterministic controllers of nondeterministic processes
with Andre Arnold, in J. Flum, E. Graedel, T. Wilke eds. "Logic and Automata", Texts in Logic and Games, Amsterdam University Press, 2007 PDF

Forest Algebras
with Mikolaj Bojanczyk, in J. Flum, E. Graedel, T. Wilke eds. "Logic and Automata", Texts in Logic and Games, Amsterdam University Press, 2007 PDF

Minimizing variants of visibly pushdown automata, Proceedings of MFCS'07, LNCS 4708, pp. 135-146,
with Pat Chervet, PDF

The Complexity of Games on Higher Order Pushdown Automata
with Thierry Cachat. A short note. PDF at HAL

A lower bound on web services composition
with Anca Muscholl, Logical Methods in Computer Science (FOSSACS, Special Issue) CORR (conference version FOSSACS 2007, PDF )

Positional determinacy of games with infinitely many priorities
with Erich Grädel, Logical Methods in Computer Science Vol. 2 2006, pp. 1-22 PDF, arXiv

Idealized Algol with ground recursion, and PDA equivalence
with Andrzej Murawski and Luke Ong, Proceedings of ICALP'05, LNCS 3580, pp 917-929 PostScript, PDF

Unsafe grammars and panic automata
with Teodor Knapik, Damian Niwinski and Pawel Urzyczyn, Proceedings of ICALP'05, LNCS 3580, pp 1450-1461 PostScript, PDF. Long version: PostScript, PDF

Third-Order Idealized Algol with Iteration is Decidable
with Andrzej Murawski, Theor. Comput. Sci. 390(2-3): 214-229 (2008) (Conference version, FOSSACS'05, LNCS 3441, pp. 202-218 PostScript, PDF)

Alternating Timed Automata
with Slawomir Lasota, ACM Trans. Comput. Log. 9(2), (2008) PDF (conference version, FOSSACS'05 LNCS 3441, PDF)

An NP-complete fragment of LTL
with Anca Muschol, Proceedings of DLT'04, PostScript, PDF

Characterizing EF and EX tree logics
with Mikolaj Bojanczyk, TCS 358 (2-3) pp. 255-272 (2006) PostScript, PDF)

Deciding Nondeterministic Hierarchy of Deterministic Tree Automata
with Damian Niwinski, ENTCS 123 pp. 195-208, PostScript, PDF

A landscape with games in the background
Invited talk at LICS'04, Proceedings of LICS'04, pp. 356-366, PostScript, PDF

Distributed Games
with Swarup Mohalik, Proceedings of FSTTCS'03, LNCS 2914, pp. 338-351, PostScript, PDF (Full version PostScript, PDF)

Pushdown games with unboundedness and regular conditions
with Alexis Bouquet, Olivier Serre, Proceedings of FSTTCS'03, LNCS 2914, pp. 88-99, PostScript, PDF (Full version PostScript, PDF)

Games for synthesis of controlers with partial observation,
with Andre Arnold and Aymeric Vincent. Theoretical Computer Science vol. 303(1) (2003) pp. 7-34, PostScript, PDF

A gap property of deterministic tree languages,
with Damian Niwinski. Theoretical Computer Science vol. 303(1) (2003) pp. 215-231 PostScript, PDF

Complexity of weak acceptance conditions in tree automata,
with Jakub Neumann and Andrzej Szepietowski. IPL vol. 84 (2002) pp. 181-187, PostScript, PDF

Deciding low levels of tree-automata hierarchy
Proceedings of WoLLIC'02, ENTCS vol 67, PostScript, PDF

Permissive strategies: from parity games to safety games,
with Julien Bernet and David Janin. Theoretical Informatics and Applications (RAIRO) 36(2002) pp. 251-275, PostScript, PDF

Model checking CTL properties of pushdown systems,
FSTTCS'00, LNCS 1974, pp. 127-138, PostScript, PDF

Local logics for traces,
Journal of Automata, Languages and Combinatorics 7(2002) pp. 259-290, PostScript, PDF

Guarded fixed point logic,
with Erich Grädel, LICS 99, PostScript, PDF

Difficult configurations -- On the complexity of LTrL,
ICALP '98, LNCS 1443 PostScript, (Full version to appear in Formal Methods in System Design PostScript, PDF)

The Horn Mu--calculus,
with Witold Charatonik, David McAllester Damian Niwinski, Andreas Podelski, LICS '98, PostScript, PDF

Relating hierachies of word and tree automata,
with Damian Niwinski, STACS'98, LNCS 1373, PostScript

How much memory is needed to win infinite games,
with Stefan Dziembowski and Marcin Jurdzinski, IEEE LICS'97, PostScript, PDF

An expressively complete linear time temporal logic,
with P. S. Thiagarajan, IEEE LICS'97, PostScript. Full version in Information and Computation 179(2002) pp. 230--249, PostScript , PDF

On the expressive completeness of the propositional mu-calculus with respect to the monadic second order logic,
with David Janin, CONCUR'96, LNCS 1119, pp. 263-277 PostScript

Pushdown processes: games and model checking,
CAV'96, LNCS 1102 pp. 62-75 PostScript. Full version in Information and Computation 164(2001) pp. 234-263, PostScript, PDF

Monadic second order logic on tree-like structures,
STACS'96, LNCS 1046, pp. 401-414 PostScript. Full version Theoretical Computer Science 275 (2002), no. 1-2, pp 311-346. PostScript, PFD.

Monadic Second-Order Logic, Graph Coverings and Unfoldings of Transition Systems
with Bruno Courcelle, CSL'95, Full version in Annals of Pure and Applied Logic, 92 (1998) pp. 35-62, PostScript.

Automata for the mu-calculus and related results,
with David Janin, MFCS'95, LNCS 969, pp. 552-562 PostScript, PDF

Completeness of Kozen's axiomatisation of the propositional Mu-calculus,
LICS'95, pp. 14-24. Full version in Information and Computation 157 (2000), pp.142--182 (PostScript , PDF of a full of version)

A Complete Deductive System for the mu-Calculus,
IEEE LICS'93 proceedings, pp. 136--147, also BRICS Report Series RS-95-6 (University of Aarhus) PostScript (full version)

A Complete Deductive System for the mu-Calculus,
PhD-thesis, Warsaw University, 1994, PostScript, PDF

Games for the mu-calculus,
with Damian Niwinski, TCS 163, 1997, pp. 99--116 PostScript

Gentzen Type Axiomatization for Propositional Algorithmic Logic,
MFCS'90 B.Rovan (ed.) LNCS 452, pp. 499-508. Full version in TCS 118 (1993) 67-79

Igor Walukiewicz
Last modified: Wed Jan 12 09:08:43 CET 2005