Igor Walukiewicz: publications

Asynchronous Games over Tree Architectures
with B. Genest, H. Gimbert, and A. Muscholl, ICALP, 2013. PDF

Lazy abstractions for timed automata
with F. Herbreteau, B. Srivathsan, CAV, 2013. arxiv

Using models to model-check recursive schemes
with S. Salvati, TLCA 2013. PDF

Better abstractions for timed automata
with F. Herbreteau, B. Srivathsan, LICS, 2012. PDF

An alternate proof of Statman's finite completeness theorem
with B. Srivathsan, Information Processing Letters, Volume 112, Issues 14-15 pp.612-616, 2012 DOI , PDF

Using non-convex approximations for efficient analysis of timed automata
with F. Herbreteau and D. Kini and B. Srivathsan, FSTTCS'11, LIPIcs 13, pages 162-173, Proceedings

Krivine machines and higher-order schemes
with Sylvain Salvati, ICALP'11, LNCS 6756, pages 162-173, PDF

Choice Functions and Well-Orderings over the Infinite Binary Tree
with Arnaud Carayol, Christof Löding, Damian Niwinski. Central European Journal of Mathematics 8(4), 2010, pp 662-682 PDF

Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata
with Blaise Genest, Hugo Gimbert, Anca Muscholl. Proceedings of ICALP'10, LNCS 6199, pages 52-63 PDF

Efficient Emptiness Check for Timed Buchi Automata
with Frederic Herbreteau and B. Srivathsan. Formal Methods in System Design: Volume 40, Issue 2 (2012), Page 122-146 DOI , PDF
Also in Proceedings of CAV'10, LNCS 6174, pages 148-161 PDF

Wreath Products of Forest Algebras, with Applications to Tree Logics
with Mikolaj Bojanczyk and Howard Straubing. Logical Methods in Computer Science, 8(3), 2012 paper 19
Also in proceedings of LICS'09 PDF

Weak Alternating Timed Automata
with Pawel Parys. Logical Methods in Computer Science 8(3), 2012 paper 18
Also in proceedings of ICALP'09, LNCS 5556, pp. 273--284 PDF

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 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