Publications

The following publications are related to the topics of GAMES and have either been presented at one of the annual meetings or came out of an exchange or short visit sponsored by the programme.

To appear

  • V. Bárány, Ł. Kaiser, and A. Rabinovich. Expressing Cardinality Quantifiers in Monadic Second-Order Logic over Chains. J. Symb. Logic. To appear.             
    BibTeX

2011

  • L. Brim, J. Chaloupka, L. Doyen, R. Gentilini, and J. Raskin. Faster algorithms for mean-payoff games. Formal Methods in System Design, vol. 38(2), pp. 97-118, 2011.             
    BibTeX
  • W. Czerwinski, S. B. Fröschle, and S. Lasota. Partially-commutative context-free processes: Expressibility and tractability. Inf. Comput., vol. 209(5), pp. 782-798, 2011.             
    BibTeX
  • K. Apt and E. Grädel (Eds.). Lectures in Game Theory for Computer Scientists. Cambridge University Press, 2011.             
    BibTeX
  • P. Parys. Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata. In STACS, pp. 603-614, 2011.             
    BibTeX
  • L. Segoufin and S. Torunczyk. Automata based verification over linearly ordered data domains. In STACS, pp. 81-92, 2011.             
    BibTeX

2010

  • P. A. Abdulla, Y. Chen, L. Clemente, L. Holík, C. Hong, R. Mayr, and T. Vojnar. Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing. In CAV, pp. 132-147, 2010.             
    BibTeX
  • P. A. Abdulla, Y. Chen, L. Holík, R. Mayr, and T. Vojnar. When Simulation Meets Antichains. In TACAS, pp. 158-174, 2010.             
    BibTeX
  • B. Aminof, O. Kupferman, and A. Murano. Improved Model Checking of Hierarchical Systems. In VMCAI, pp. 61-77, 2010.             
    BibTeX
  • M. Benedikt, C. Ley, and G. Puppis. Automata vs. Logics on Data Words. In CSL, pp. 110-124, 2010.             
    BibTeX
  • S. Berardi, T. Coquand, and S. Hayashi. Games with 1-backtracking. Ann. Pure Appl. Logic, vol. 161(10), pp. 1254-1269, 2010.             
    BibTeX
  • D. Berwanger and L. Kaiser. Information Tracking in Games on Graphs. Journal of Logic, Language and Information, vol. 19(4), pp. 395-412, 2010.             
    BibTeX
  • A. Bianco, M. Faella, F. Mogavero, and A. Murano. Exploring the Boundary of Half Positionality. In CLIMA XI, pp. 171-185, 2010.             
    BibTeX
  • M. Bojanczyk, D. Niwinski, A. Rabinovich, A. Radziwonczyk-Syta, and M. Skrzypczak. On the Borel Complexity of MSO Definable Sets of Branches. Fundam. Inform., vol. 98(4), pp. 337-349, 2010.             
    BibTeX
  • D. Bresolin, D. D. Monica, V. Goranko, A. Montanari, and G. Sciavicco. Metric Propositional Neighborhood Logics: Expressiveness, Decidability, and Undecidability. In ECAI, pp. 695-700, 2010.             
    BibTeX
  • D. Bresolin, D. D. Monica, V. Goranko, A. Montanari, and G. Sciavicco. Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings. Electr. Notes Theor. Comput. Sci., vol. 262, pp. 65-81, 2010.             
    BibTeX
  • T. Brázdil, V. Brozek, and K. Etessami. One-Counter Stochastic Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) (K. Lodaya and M. Mahajan, Eds.), vol. 8 of, pp. 108–119, 2010.             
    BibTeX
  • T. Brázdil, V. Brozek, K. Etessami, A. Kucera, and D. Wojtczak. One-Counter Markov Decision Processes. In SODA, pp. 863-874, 2010.             
    BibTeX
  • V. Bárány, Ł. Kaiser, and A. Rabinovich. Expressing Cardinality Quantifiers in Monadic Second-Order Logic over Trees. Fundamenta Informaticae, vol. 100, pp. 1–18, 2010.             
    BibTeX
  • A. Bès and A. Rabinovich. Decidable Expansions of Labelled Linear Orderings. In Fields of Logic and Computation, pp. 95-107, 2010.             
    BibTeX
  • K. Chatterjee and L. Doyen. Energy Parity Games. In ICALP (2), pp. 599-610, 2010.             
    BibTeX
  • L. Clemente and R. Mayr. Multipebble Simulations for Alternating Automata - (Extended Abstract). In CONCUR, pp. 297-312, 2010.             
    BibTeX
  • T. Colcombet and C. Löding. Regular Cost Functions over Finite Trees. In LICS, pp. 70-79, 2010.             
    BibTeX
  • J. Cristau, C. David, and F. Horn. How do we remember the past in randomised strategies? In GANDALF, pp. 30-39, 2010.             
    BibTeX
  • G. D'Agostino and G. Lenzi. On the $\mu$-calculus over transitive and finite transitive frames. Theor. Comput. Sci., vol. 411(50), pp. 4273-4290, 2010.             
    BibTeX
  • F. Donnarumma. A Model for Programmability and Virtuality in Dynamical Neural Networks. , 2010.             
    BibTeX
  • J. Fearnley and M. Z. 0002. Playing Muller Games in a Hurry. In GANDALF, pp. 146-161, 2010.             
    BibTeX
  • J. Fearnley, M. Jurdzinski, and R. Savani. Linear Complementarity Algorithms for Infinite Games. In SOFSEM, pp. 382-393, 2010.             
    BibTeX
  • D. Figueira, P. Hofman, and S. Lasota. Relating timed and register automata. In EXPRESS'10, pp. 61-75, 2010.             
    BibTeX
  • N. Fijalkow and F. Horn. The surprizing complexity of reachability games. CoRR, vol. abs/1010.2420, 2010.             
    BibTeX
  • T. Ganzow and Ł. Kaiser. New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures. In Proceedings of the 19th Annual Conference of the European Association for Computer Science Logic, CSL 2010 (A. Dawar and H. Veith, Eds.), vol. 6247 of Lecture Notes in Computer Science, pp. 366–380. Springer, 2010.             
    BibTeX
  • H. Gimbert and Y. Oualhadj. Probabilistic Automata on Finite Words: Decidable and Undecidable Problems. In ICALP (2), pp. 527-538, 2010.             
    BibTeX
  • S. Göller and M. Lohrey. Branching-time Model Checking of One-counter Processes. In STACS, pp. 405-416, 2010.             
    BibTeX
  • M. Hague and C. L. Ong. Analysing Mu-Calculus Properties of Pushdown Systems. In SPIN, pp. 187-192, 2010.             
    BibTeX
  • S. Hummel, M. Skrzypczak, and S. Torunczyk. On the Topological Complexity of MSO+U and Related Automata Models. In MFCS, pp. 429-440, 2010.             
    BibTeX
  • M. Huth, N. Piterman, and D. Wagner. p-Automata: New Foundations for Discrete-Time Probabilistic Verification. In QEST, pp. 161-170, 2010.             
    BibTeX
  • M. Jenkins, J. Ouaknine, A. Rabinovich, and J. Worrell. Alternating Timed Automata over Bounded Time. In LICS, pp. 60-69, 2010.             
    BibTeX
  • B. Kordy, S. Mauw, M. Melissen, and P. Schweitzer. Attack-Defense Trees and Two-Player Binary Zero-Sum Extensive Form Games Are Equivalent. In GameSec, pp. 245-256, 2010.             
    BibTeX
  • C. Loeding (Ed.). International Summer School on Modeling and Verifying Parallel Processes Movep 2010. 2010.             
    BibTeX
  • J. Marcinkowski, J. Michaliszyn, and E. Kieronski. B and D Are Enough to Make the Halpern-Shoham Logic Undecidable. In ICALP (2), pp. 357-368, 2010.             
    BibTeX
  • F. Mogavero, A. Murano, and M. Y. Vardi. Relentful Strategic Reasoning in Alternating-Time Temporal Logic. In LPAR (Dakar), pp. 371-386, 2010.             
    BibTeX
  • F. Mogavero, A. Murano, and M. Y. Vardi. Reasoning About Strategies. In FSTTCS, pp. 133-144, 2010.             
    BibTeX
  • A. Montanari, I. Pratt-Hartmann, and P. Sala. Decidability of the Logic of the Reflexive Sub-interval Relation over Finite Linear Orders. In Proceedings of the 17th International Symposium on Temporal Representation and Reasoning (TIME), Paris, France, September 2010, pp. 27-34, 2010.             
    BibTeX
  • A. Montanari, G. Puppis, and P. Sala. Maximal Decidable Fragments of Halpern and Shoham's Modal Logic of Intervals. In ICALP (2), pp. 345-356, 2010.             
    BibTeX
  • A. Montanari, G. Puppis, P. Sala, and G. Sciavicco. Decidability of the Interval Temporal Logic ABB over the Natural Numbers. In STACS, pp. 597-608, 2010.             
    BibTeX
  • A. Rabinovich. The full binary tree cannot be interpreted in a chain. J. Symb. Log., vol. 75(4), pp. 1489-1498, 2010.             
    BibTeX

2009

  • P. A. Abdulla, Y. Chen, L. Holík, and T. Vojnar. Mediating for Reduction (on Minimizing Alternating Büchi Automata). In FSTTCS, pp. 1-12, 2009.             
    BibTeX
  • P. A. Abdulla, G. Delzanno, N. B. Henda, and A. Rezine. Monotonic Abstraction: on Efficient Verification of Parameterized Systems. Int. J. Found. Comput. Sci., vol. 20(5), pp. 779-801, 2009.             
    BibTeX
  • A. Bianco, M. Faella, F. Mogavero, and A. Murano. Balanced Paths in Colored Graphs. In MFCS, pp. 149-161, 2009.             
    BibTeX
  • M. Bojanczyk and T. Idziaszek. Algebra for Infinite Forests with an Application to the Temporal Logic EF. In CONCUR, pp. 131-145, 2009.             
    BibTeX
  • M. Bojanczyk and S. Torunczyk. Deterministic Automata and Extensions of Weak MSO. In FSTTCS, pp. 73-84, 2009.             
    BibTeX
  • D. Bresolin, D. D. Monica, V. Goranko, A. Montanari, and G. Sciavicco. Undecidability of Interval Temporal Logics with the Overlap Modality. In TIME, pp. 88-95, 2009.             
    BibTeX
  • C. H. Broadbent and C. L. Ong. On Global Model Checking Trees Generated by Higher-Order Recursion Schemes. In FOSSACS, pp. 107-121, 2009.             
    BibTeX
  • T. Brázdil, V. Brozek, A. Kucera, and J. Obdrzálek. Qualitative Reachability in Stochastic BPA Games. In STACS, pp. 207-218, 2009.             
    BibTeX
  • J. Cabessa, J. Duparc, A. Facchini, and F. Murlak. The Wadge Hierarchy of Max-Regular Languages. In FSTTCS, pp. 121-132, 2009.             
    BibTeX
  • W. Czerwinski, S. B. Fröschle, and S. Lasota. Partially-Commutative Context-Free Processes. In CONCUR, pp. 259-273, 2009.             
    BibTeX
  • M. Faella. Admissible Strategies in Infinite Games over Graphs. In MFCS, pp. 307-318, 2009.             
    BibTeX
  • A. Ferrante, M. Napoli, and M. Parente. Model Checking for Graded CTL. Fundam. Inform., vol. 96(3), pp. 323-339, 2009.             
    BibTeX
  • A. Ferrante, M. Napoli, and M. Parente. Graded-CTL: Satisfiability and Symbolic Model Checking. In ICFEM, pp. 306-325, 2009.             
    BibTeX
  • E. Filiot, N. Jin, and J. Raskin. An Antichain Algorithm for LTL Realizability. In CAV, pp. 263-277, 2009.             
    BibTeX
  • N. Gierasimczuk, L. Kurzen, and F. R. Velázquez-Quesada. Learning and Teaching as a Game: A Sabotage Approach. In LORI, pp. 119-132, 2009.             
    BibTeX
  • E. Grädel, Ł. Kaiser, and R. Rabinovich. Directed Graphs of Entanglement Two. In Proceedings of the 17th International Symposium on Fundamentals of Computation Theory, FCT '09, vol. 5699 of LNCS, pp. 169–181. Springer, 2009.             
    BibTeX
  • F. Honsell and M. Lenisa. Conway Games, Coalgebraically. In CALCO, pp. 300-316, 2009.             
    BibTeX
  • S. Hummel, H. Michalewski, and D. Niwinski. On the Borel Inseparability of Game Tree Languages. In STACS, pp. 565-575, 2009.             
    BibTeX
  • M. Huth, N. Piterman, and H. Wang. A workbench for preprocessor design and evaluation: toward benchmarks for parity games. ECEASST, vol. 23, 2009.             
    BibTeX
  • M. Jurdzinski, M. Z. Kwiatkowska, G. Norman, and A. Trivedi. Concavely-Priced Probabilistic Timed Automata. In CONCUR, pp. 415-430, 2009.             
    BibTeX
  • M. Jurdzinski, R. Lazic, and M. Rutkowski. Average-Price-per-Reward Games on Hybrid Automata with Strong Resets. In VMCAI, pp. 167-181, 2009.             
    BibTeX
  • L. Kaiser. Synthesis for Structure Rewriting Systems. In MFCS, pp. 415-426, 2009.             
    BibTeX
  • V. Kountouriotis, C. Nomikos, and P. Rondogiannis. A Game-Theoretic Characterization of Boolean Grammars. In Developments in Language Theory, pp. 334-347, 2009.             
    BibTeX
  • J. Leroux. The General Vector Addition System Reachability Problem by Presburger Inductive Invariants. In LICS, pp. 4-13, 2009.             
    BibTeX
  • E. D. Maria, A. Montanari, and N. Vitacolonna. Games on Strings with a Limited Order Relation. In LFCS, pp. 164-179, 2009.             
    BibTeX
  • A. Montanari, G. Puppis, and P. Sala. A Decidable Spatial Logic with Cone-Shaped Cardinal Directions. In CSL, pp. 394-408, 2009.             
    BibTeX
  • S. Paul and S. E. Simon. Nash Equilibrium in Generalised Muller Games. In FSTTCS, pp. 335-346, 2009.             
    BibTeX
  • A. Rabinovich. Synthesis of Finite-state and Definable Winning Strategies. In FSTTCS, pp. 359-370, 2009.             
    BibTeX
  • M. Ummels and D. Wojtczak. Decision Problems for Nash Equilibria in Stochastic Games. In CSL, pp. 515-529, 2009.             
    BibTeX
  • A. Witzel, K. R. Apt, and J. A. Zvesper. Strategy Elimination in Games with Interaction Structures. In LORI, pp. 302-315, 2009.             
    BibTeX

2008

  • J. van Benthem, S. Ghosh, and F. Liu. Modelling simultaneous games in dynamic logic. Synthese, vol. 165(2), pp. 247-268, 2008.             
    BibTeX
  • D. Berwanger. Infinite Coordination Games. In LOFT, pp. 1-19, 2008.             
    BibTeX
  • D. Berwanger and L. Doyen. On the Power of Imperfect Information. In FSTTCS, pp. 73-82, 2008.             
    BibTeX
  • M. Bojanczyk and P. Parys. XPath evaluation in linear time. In PODS, pp. 241-250, 2008.             
    BibTeX
  • P. Bouyer, T. Brihaye, M. Jurdzinski, R. Lazic, and M. Rutkowski. Average-Price and Reachability-Price Games on Hybrid Automata with Strong Resets. In FORMATS, pp. 63-77, 2008.             
    BibTeX
  • T. Brázdil, V. Forejt, J. Kretínsky, and A. Kucera. The Satisfiability Problem for Probabilistic CTL. In LICS, pp. 391-402, 2008.             
    BibTeX
  • T. Colcombet and C. Löding. The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata. In ICALP (2), pp. 398-409, 2008.             
    BibTeX
  • P. Darondeau, B. Genest, P. S. Thiagarajan, and S. Yang. Quasi-Static Scheduling of Communicating Tasks. In CONCUR, pp. 310-324, 2008.             
    BibTeX
  • A. Dawar and E. Grädel. The Descriptive Complexity of Parity Games. In Proceedings of the 17th Annual Conference on Computer Science Logic, CSL 2008, vol. 5213 of LNCS, pp. 354–368. Springer, 2008.             
    BibTeX
  • K. Etessami, D. Wojtczak, and M. Yannakakis. Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems. In QEST, pp. 243-253, 2008.             
    BibTeX
  • C. Galanaki, P. Rondogiannis, and W. W. Wadge. An infinite-game semantics for well-founded negation in logic programming. Ann. Pure Appl. Logic, vol. 151(2-3), pp. 70-88, 2008.             
    BibTeX
  • P. D. Gianantonio, F. Honsell, and M. Lenisa. A type assignment system for game semantics. Theor. Comput. Sci., vol. 398(1-3), pp. 150-169, 2008.             
    BibTeX
  • H. Gimbert and F. Horn. Solving Simple Stochastic Games. In CiE, pp. 206-209, 2008.             
    BibTeX
  • F. Horn. Explicit Muller Games are PTIME. In FSTTCS, pp. 235-243, 2008.             
    BibTeX
  • M. Jurdzinski and A. Trivedi. Average-Time Games. In FSTTCS, pp. 340-351, 2008.             
    BibTeX
  • A. Murano, M. Napoli, and M. Parente. Program Complexity in Hierarchical Module Checking. In LPAR, pp. 318-332, 2008.             
    BibTeX
  • F. Murlak. Weak index versus Borel rank. In STACS, pp. 573-584, 2008.             
    BibTeX
  • A. W. To and L. Libkin. Recurrent Reachability Analysis in Regular Model Checking. In LPAR, pp. 198-213, 2008.             
    BibTeX
  • M. Ummels. The Complexity of Nash Equilibria in Infinite Multiplayer Games. In FoSSaCS, pp. 20-34, 2008.             
    BibTeX