@inproceedings{BG-lpar01,
address = {Havana, Cuba},
month = dec,
year = 2001,
volume = 2250,
series = {Lecture Notes in Artificial Intelligence},
publisher = {Springer},
editor = {Nieuwenhuis, Robert and Voronkov, Andrei},
acronym = {{LPAR}'01},
booktitle = {{P}roceedings of the 8th {I}nternational
{C}onference on {L}ogic for {P}rogramming,
{A}rtificial {I}ntelligence, and {R}easoning
({LPAR}'01)},
author = {Berwanger, Dietmar and Gr{\"a}del, Erich},
title = {Games and Model Checking for Guarded Logics},
pages = {70-84},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BG-lpar01.ps},
ps = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BG-lpar01.ps}
}
@incollection{BB-lncs2500-19,
missingmonth = mar,
missingnmonth = 3,
year = 2002,
volume = 2500,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Gr{\"a}del, Erich and Thomas, Wolfgang and Wilke, Thomas},
acronym = {{A}utomata, {L}ogics, and {I}nfinite {G}ame},
booktitle = {{A}utomata, {L}ogics, and {I}nfinite {G}ame: {A}~{G}uide to
{C}urrent {R}esearch},
author = {Berwanger, Dietmar and Blumensath, Achim},
title = {Automata for Guarded Fixed Point Logics},
pages = {343-355},
chapter = {19},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BB-lncs2500-19.ps},
ps = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BB-lncs2500-19.ps}
}
@incollection{BB-lncs2500-16,
missingmonth = mar,
missingnmonth = 3,
year = 2002,
volume = 2500,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Gr{\"a}del, Erich and Thomas, Wolfgang and Wilke, Thomas},
acronym = {{A}utomata, {L}ogics, and {I}nfinite {G}ame},
booktitle = {{A}utomata, {L}ogics, and {I}nfinite {G}ame: {A}~{G}uide to
{C}urrent {R}esearch},
author = {Berwanger, Dietmar and Blumensath, Achim},
title = {The Monadic Theory of Tree-like Structures},
pages = {285-301},
chapter = {16},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BB-lncs2500-16.ps},
ps = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BB-lncs2500-16.ps}
}
@inproceedings{BGL-csl02,
address = {Edinburgh, Scotland, UK},
month = sep,
year = 2002,
volume = 2471,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Bradfield, Julian C.},
acronym = {{CSL}'02},
booktitle = {{P}roceedings of the 16th {I}nternational
{W}orkshop on {C}omputer {S}cience {L}ogic
({CSL}'02)},
author = {Berwanger, Dietmar and Gr{\"a}del, Erich and
Lenzi, Giacomo},
title = {On the variable hierarchy of the modal {{\(\mu\)}}-calculus},
pages = {352-366},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BGL-csl02.ps},
ps = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BGL-csl02.ps}
}
@article{Berwanger-SL03,
publisher = {Kluwer Academic Publishers},
journal = {Studia Logica},
author = {Berwanger, Dietmar},
title = {Game Logic is Strong Enough for Parity Games},
year = {2003},
month = nov,
volume = {75},
number = {2},
pages = {205-219},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/Berwanger-SL03.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/Berwanger-SL03.pdf},
doi = {10.1023/A:1027358927272}
}
@inproceedings{BGK-lpar03,
address = {Almaty, Kazakhstan},
month = sep,
year = 2003,
volume = 2850,
series = {Lecture Notes in Artificial Intelligence},
publisher = {Springer},
editor = {Vardi, Moshe Y. and Voronkov, Andrei},
acronym = {{LPAR}'03},
booktitle = {{P}roceedings of the 10th {I}nternational
{C}onference on {L}ogic for {P}rogramming,
{A}rtificial {I}ntelligence, and {R}easoning
({LPAR}'03)},
author = {Berwanger, Dietmar and Gr{\"a}del, Erich and
Kreutzer, Stephan},
title = {Once Upon a Time in the West. Determinacy, Complexity
and Definability of Path Games.},
pages = {226-240},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BGK-lpar03.ps},
ps = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BGK-lpar03.ps}
}
@inproceedings{BG-lpar04,
address = {Montevideo, Uruguay},
month = mar,
year = 2005,
volume = 3452,
series = {Lecture Notes in Artificial Intelligence},
publisher = {Springer},
editor = {Baader, Franz and Voronkov, Andrei},
acronym = {{LPAR}'04},
booktitle = {{P}roceedings of the 11th {I}nternational
{C}onference on {L}ogic for {P}rogramming,
{A}rtificial {I}ntelligence, and {R}easoning
({LPAR}'04)},
author = {Berwanger, Dietmar and Gr{\"a}del, Erich},
title = {Entanglement~-- {A} Measure for the Complexity of
Directed Graphs with Applications to Logic and Games},
pages = {209-223},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BG-lpar04.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BG-lpar04.pdf}
}
@article{BG-tocsys04,
publisher = {Springer},
journal = {Theory of Computing Systems},
author = {Berwanger, Dietmar and Gr{\"a}del, Erich},
title = {Fixed-Point Logics and Solitaire Games},
year = {2004},
month = dec,
volume = {37},
number = 6,
pages = {675-694},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BG-tocsys04.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BG-tocsys04.pdf},
doi = {10.1007/s00224-004-1147-5}
}
@phdthesis{Berwanger-Thesis,
author = {Berwanger, Dietmar},
title = {Games and Logical Expressiveness},
school = {Department of Computer Science, RWTH Aachen, Germany},
year = {2005},
type = {{Ph.}{D.} {T}hesis},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/phd-berwanger.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/phd-berwanger.pdf}
}
@inproceedings{BL-stacs05,
address = {Stuttgart, Germany},
month = feb,
year = 2005,
volume = 3404,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Diekert, Volker and Durand, Bruno},
acronym = {{STACS}'05},
booktitle = {{P}roceedings of the 22nd {A}nnual
{S}ymposium on {T}heoretical {A}spects of
{C}omputer {S}cience
({STACS}'05)},
author = {Berwanger, Dietmar and Lenzi, Giacomo},
title = {The variable hierarchy of the {{\(\mu\)}}-calculus is
strict},
pages = {97-109},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BL-stacs05.ps},
ps = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BL-stacs05.ps}
}
@inproceedings{BDHK-stacs06,
address = {Marseilles, France},
month = feb,
year = 2006,
volume = 3884,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Durand, Bruno and Thomas, Wolfgang},
acronym = {{STACS}'06},
booktitle = {{P}roceedings of the 23rd {A}nnual
{S}ymposium on {T}heoretical {A}spects of
{C}omputer {S}cience
({STACS}'06)},
author = {Berwanger, Dietmar and Dawar, Anuj and Hunter, Paul and
Kreutzer, Stephan},
title = {{DAG}-width and parity games},
pages = {524-536},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BDHK-stacs06.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BDHK-stacs06.pdf},
doi = {10.1007/11672142_43}
}
@inproceedings{BJ-icgt06,
address = {Natal, Rio Grande do Norte, Brazil},
month = sep,
year = 2006,
volume = 4178,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Corradini, Andrea and Ehrig, Hartmut and Montanari, Ugo and Ribeiro, Leila and
Rozenberg, Grzegorz},
acronym = {{ICGT}'06},
booktitle = {{P}roceedings of the 3rd {I}nternational {C}onference on {G}raph
{T}ransformations ({ICGT}'06)},
author = {Berwanger, Dietmar and Janin, David},
title = {Automata on Directed Graphs: Vertex versus Edge
Marking},
pages = {46-60},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BJ-icgt06.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BJ-icgt06.pdf},
doi = {10.1007/11841883_5}
}
@article{BGL-tocsys07,
publisher = {Springer},
journal = {Theory of Computing Systems},
author = {Berwanger, Dietmar and Gr{\"a}del, Erich and
Lenzi, Giacomo},
title = {The variable hierarchy of the {{\(\mu\)}}-calculus is
strict},
volume = {40},
number = {4},
year = 2007,
month = jun,
pages = {437-466},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BGL-tocsys07.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BGL-tocsys07.pdf},
doi = {10.1007/s00224-006-1317-8}
}
@inproceedings{Ber-stacs07,
address = {Aachen, Germany},
month = feb,
year = 2007,
volume = 4393,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Thomas, Wolfgang and Weil, Pascal},
acronym = {{STACS}'07},
booktitle = {{P}roceedings of the 24th {A}nnual
{S}ymposium on {T}heoretical {A}spects of
{C}omputer {S}cience
({STACS}'07)},
author = {Berwanger, Dietmar},
title = {Admissibility in infinite games},
pages = {188-199},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/Ber-stacs07.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/Ber-stacs07.pdf},
doi = {10.1007/978-3-540-70918-3_17}
}
@inproceedings{BCDHR-concur08,
address = {Toronto, Canada},
month = aug,
year = 2008,
volume = 5201,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {van Breugel, Franck and Chechik, Marsha},
acronym = {{CONCUR}'08},
booktitle = {{P}roceedings of the 19th
{I}nternational {C}onference on
{C}oncurrency {T}heory
({CONCUR}'08)},
author = {Berwanger, Dietmar and Chatterjee, Krishnendu and
Doyen, Laurent and Henzinger, {\relax Th}omas A. and Raje, Sangram},
title = {Strategy Construction for Parity Games with Imperfect
Information},
pages = {325-339},
doi = {10.1007/978-3-540-85361-9_27},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BCDHR-concur08.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BCDHR-concur08.pdf}
}
@inproceedings{BD-fsttcs08,
address = {Bangalore, India},
month = dec,
year = 2008,
volume = 2,
series = {Leibniz International Proceedings in Informatics},
publisher = {Leibniz-Zentrum f{\"u}r Informatik},
editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V.},
acronym = {{FSTTCS}'08},
booktitle = {{P}roceedings of the 28th {C}onference on
{F}oundations of {S}oftware {T}echnology and
{T}heoretical {C}omputer {S}cience
({FSTTCS}'08)},
author = {Berwanger, Dietmar and Doyen, Laurent},
title = {On the Power of Imperfect Information},
nopages = {},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BD-fsttcs08.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BD-fsttcs08.pdf},
abstract = {We present a polynomial-time reduction from parity games with
imperfect information to safety games with imperfect information. Similar
reductions for games with perfect information typically increase the game
size exponentially. Our construction avoids such a blow-up by using
imperfect information to realise succinct counters which cover a range
exponentially larger than their size. In particular, the reduction shows
that the problem of solving imperfect-information games with safety
conditions is EXPTIME-complete.}
}
@inproceedings{BP-icla09,
address = {Chennai, India},
month = jan,
year = 2009,
volume = 5378,
series = {Lecture Notes in Artificial Intelligence},
publisher = {Springer},
editor = {Ramanujam, R. and Sarukkai, Sundar},
acronym = {{ICLA}'09},
booktitle = {{P}roceedings of the 3rd {I}ndian {C}onference on {L}ogic and
{A}pplications ({ICLA}'09)},
author = {Berwanger, Dietmar and Pinchinat, Sophie},
title = {Game Quantification Patterns},
pages = {116-130},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BP-icla09.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BP-icla09.pdf},
doi = {10.1007/978-3-540-92701-3_8},
abstract = {We analyse two basic approaches of extending classical logics
with quantifiers interpreted via games: Propositional Game Logic of Parikh
and Alternating-Time Temporal Logic of Alur, Henzinger, and Kupferman.
Although the two approaches are historically remote and they incorporate
operationally orthogonal paradigms, we trace the formalisms back to common
foundations and argue that they share remarkable similarities in terms of
expressive power.}
}
@inproceedings{BCDDH-tacas09,
address = {York, UK},
month = mar,
year = 2009,
volume = {5505},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Kowalewski, Stefan and Philippou, Anna},
acronym = {{TACAS}'09},
booktitle = {{P}roceedings of the 15th {I}nternational
{C}onference on {T}ools and {A}lgorithms for
{C}onstruction and {A}nalysis of {S}ystems
({TACAS}'09)},
author = {Berwanger, Dietmar and Chatterjee, Krishnendu and
De{~}Wulf, Martin and Doyen, Laurent and
Henzinger, {\relax Th}omas~A.},
title = {Alpaga: A~Tool for Solving Parity Games with Imperfect
Information},
pages = {58-61},
url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BCDDH-tacas09.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/BCDDH-tacas09.pdf},
doi = {10.1007/978-3-642-00768-2_7},
abstract = {Alpaga is a solver for two-player parity games with imperfect
information. Given the description of a game, it~determines
whether the first player can ensure to win and, if~so,
it~constructs a winning strategy. The~tool provides a
symbolic implementation of a recent algorithm based on
antichains.}
}
@incollection{Berwanger09,
year = 2010,
volume = 6006,
series = {Lecture Notes in Artificial Intelligence},
publisher = {Springer},
editor = {Bonnano, Giacomo and L{\"o}we, Benedikt and van der
Hoek, Wiebe},
booktitle = {Logic and the Foundations of Game and Decision Theory (LOFT8)},
author = {Berwanger, Dietmar},
title = {Infinite Coordination Games},
pages = {1-19},
futurechapter = {},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/Ber-loft8.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/Ber-loft8.pdf},
doi = {10.1007/978-3-642-15164-4_1},
abstract = {We investigate the prescriptive power of sequential iterated
admissibility in coordination games of the Gale-Stewart style, \textit{i.e.},
perfect-information games of infinite duration with only two payoffs. We
show that, on this kind of games, the procedure of eliminating weakly
dominated strategies is independent of the elimination order and that,
under maximal simultaneous elimination, the procedure converges after at
most omega many stages.}
}
@article{BK-jlli10,
publisher = {Kluwer Academic Publishers},
journal = {Journal of Logic, Language and Information},
author = {Berwanger, Dietmar and Kaiser, {\L}ukasz},
title = {Information Tracking in Games on Graphs},
volume = 19,
number = 4,
pages = {395-412},
year = 2010,
month = oct,
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BK-jlli10.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BK-jlli10.pdf},
doi = {10.1007/s10849-009-9115-8},
abstract = {When seeking to coordinate in a game with imperfect information,
it is often relevant for a player to know what other players know. Keeping
track of the information acquired in a play of infinite duration may,
however, lead to infinite hierarchies of higher-order knowledge. We
present a construction that makes explicit which higher-order knowledge is
relevant in a game and allows us to describe a class of games that admit
coordinated winning strategies with finite memory.}
}
@article{BCDDH-icomp10,
publisher = {Elsevier Science Publishers},
journal = {Information and Computation},
author = {Berwanger, Dietmar and Chatterjee, Krishnendu and Doyen, Laurent
and De{~}Wulf, Martin and Henzinger, {\relax Th}omas A.},
title = {Strategy Construction for Parity Games with Imperfect
Information},
volume = 208,
number = 10,
pages = {1206-1220},
year = 2010,
month = oct,
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BCDDH-icomp10.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BCDDH-icomp10.pdf},
ps = {BCDDH-icomp10.ps},
doi = {10.1016/j.ic.2009.09.006},
abstract = {We consider two-player parity games with imperfect information
in which strategies rely on observations that provide imperfect
information about the history of a play. To solve such games,
\textit{i.e.}, to determine the winning regions of players and
corresponding winning strategies, one can use the subset construction to
build an equivalent perfect-information game. Recently, an algorithm that
avoids the inefficient subset construction has been proposed. The
algorithm performs a fixed-point computation in a lattice of antichains,
thus maintaining a succinct representation of state sets. However, this
representation does not allow to recover winning strategies.\par
In this paper, we build on the antichain approach to develop an algorithm
for constructing the winning strategies in parity games of imperfect
information. One major obstacle in adapting the classical procedure is
that the complementation of attractor sets would break the invariant of
downward-closedness on which the antichain representation relies. We
overcome this difficulty by decomposing problem instances recursively into
games with a combination of reachability, safety, and simpler parity
conditions. We also report on an experimental implementation of our
algorithm; to our knowledge, this is the first implementation of a
procedure for solving imperfect-information parity games on graphs.}
}
@techreport{lsv-11-20,
author = {Berwanger, Dietmar and Kaiser, {\L}ukasz and Le{\ss}enich, Simon},
title = {Imperfect Recall and Counter Games},
institution = {Laboratoire Sp{\'e}cification et V{\'e}rification,
ENS Cachan, France},
year = {2011},
month = oct,
type = {Research Report},
number = {LSV-11-20},
url = {http://www.lsv.ens-cachan.fr/Publis/RAPPORTS_LSV/PDF/rr-lsv-2011-20.pdf},
pdf = {http://www.lsv.ens-cachan.fr/Publis/RAPPORTS_LSV/PDF/rr-lsv-2011-20.pdf},
note = {21~pages},
abstract = {We study a class of omega-regular games with imperfect
information and imperfect recall, and present a
solution method which relies on the
MSO-compatibility of graph unfoldings. Furthermore,
we show a reduction from a large class of counter
parity games to such games with imperfect recall.
By combining the two results, we obtain the first
elementary algorithm for solving counter parity
games, which provides substantially improved
complexity bounds for several problems in
computational logic.}
}
@inproceedings{BLP-fsttcs11,
address = {Mumbai, India},
month = dec,
year = 2011,
volume = 13,
series = {Leibniz International Proceedings in Informatics},
publisher = {Leibniz-Zentrum f{\"u}r Informatik},
editor = {Chakraborty, Supratik and Kumar, Amit},
acronym = {{FSTTCS}'11},
booktitle = {{P}roceedings of the 31st {C}onference on
{F}oundations of {S}oftware {T}echnology and
{T}heoretical {C}omputer {S}cience
({FSTTCS}'11)},
author = {Berwanger, Dietmar and Kaiser, {\L}ukasz and Puchala, Bernd},
title = {Perfect-Information Construction for Coordination in Games},
pages = {387-398},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BLP-fsttcs11.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BLP-fsttcs11.pdf},
doi = {10.4230/LIPIcs.FSTTCS.2011.387},
abstract = {We present a general construction for eliminating imperfect
information from games with several players who coordinate against nature,
and to transform them into two-player games with perfect information while
preserving winning strategy profiles. The construction yields an infinite
game tree with epistemic models associated to nodes. To obtain a more
succinct representation, we define an abstraction based on homomorphic
equivalence, which we prove to be sound for games with observable winning
conditions. The abstraction generates finite game graphs in several
relevant cases, and leads to a new semi-decision procedure for
multi-player games with imperfect information.}
}
@article{BGKR-tcs12,
publisher = {Elsevier Science Publishers},
journal = {Theoretical Computer Science},
author = {Berwanger, Dietmar and Gr{\"a}del, Erich and Kaiser, {\L}ukasz and
Rabinovich, Roman},
title = {Entanglement and the complexity of directed graphs},
volume = 463,
year = 2012,
month = dec,
pages = {2-25},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BGKR-tcs12.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BGKR-tcs12.pdf},
doi = {10.1016/j.tcs.2012.07.010},
abstract = {Entanglement is a parameter for the complexity of
finite directed graphs that measures to which extent the cycles of
the graph are intertwined. It is defined by way of a game
similar in spirit to the cops and robber games used to
describe tree width, directed tree width, and hypertree width.
Nevertheless, on many classes of graphs, there are
significant differences between entanglement
and the various incarnations of tree width.\par
Entanglement is intimately related with the computational and
descriptive complexity of the modal \(\mu\)-calculus.
The number of fixed-point variables needed to
describe a finite graph up to bisimulation is captured by its
entanglement. This plays a crucial role in the proof
that the variable hierarchy of the \(\mu\)-calculus is strict.\par
We study complexity issues for entanglement and compare it to
other structural parameters of directed graphs.
One of our main results is that parity games of
bounded entanglement can be solved in polynomial time.
Specifically, we establish that the
complexity of solving a parity game can be parametrised in terms of
the minimal entanglement of subgames induced by a winning strategy.\par
Furthermore, we discuss the case of graphs of entanglement two.
While graphs of entanglement zero and one are very simple,
graphs of entanglement two allow arbitrary nesting of
cycles, and they form a sufficiently rich class for
modelling relevant classes of structured systems.
We provide characterisations
of this class, and propose decomposition notions similar
to the ones for tree width, DAG-width, and Kelly-width.}
}
@inproceedings{BKL-mfcs12,
address = {Bratislava, Slovakia},
month = aug,
year = 2012,
volume = 7464,
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Rovan, Branislav and Sassone, Vladimiro and Widmayer, Peter},
acronym = {{MFCS}'12},
booktitle = {{P}roceedings of the 37th
{I}nternational {S}ymposium on
{M}athematical {F}oundations of
{C}omputer {S}cience
({MFCS}'12)},
author = {Berwanger, Dietmar and Kaiser, {\L}ukasz and Le{\ss}enich, Simon},
title = {Solving Counter Parity Games},
pages = {160-171},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BKL-mfcs12.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BKL-mfcs12.pdf},
doi = {10.1007/978-3-642-32589-2_17},
abstract = {We study a class of parity games equipped with counters
that evolve according to arbitrary non-negative
affine functions. These games capture several cost
models for dynamic systems from the literature. We
present an elementary algorithm for computing the
exact value of a counter parity game, which both
generalizes previous results and improves their
complexity. To this end, we introduce a class of
\(\omega\)-regular games with imperfect information
and imperfect recall, solve them using
automata-based techniques, and prove a
correspondence between finite-memory strategies in
such games and strategies in counter parity games.}
}
@article{BDHKO-jctB12,
publisher = {Elsevier Science Publishers},
journal = {Journal of Combinatorial Theory, Series~B},
author = {Berwanger, Dietmar and Dawar, Anuj and Hunter, Paul and Kreutzer, Staphan
and Obdrz{\'a}lek, Jan},
title = {The {DAG}-width of directed graphs},
volume = 102,
number = 4,
year = 2012,
month = jul,
pages = {900-923},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BDHKO-jctB12.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BDHKO-jctB12.pdf},
doi = {10.1016/j.jctb.2012.04.004},
abstract = {Tree-width is a well-known metric on undirected graphs
that measures how tree-like a graph is and gives a
notion of graph decomposition that proves useful in
algorithm design. Tree-width can be characterised
by a graph searching game where a number of cops
attempt to capture a robber. We consider the
natural adaptation of this game to directed graphs
and show that monotone strategies in the game yield
a measure, called DAG-width, that can be seen to
describe how close a directed graph is to a directed
acyclic graph (DAG). We also provide an associated
decomposition and show how it is useful for
developing algorithms on directed graphs. In
particular, we show that the problem of determining
the winner of a parity game is solvable in
polynomial time on graphs of bounded DAG-width. We
also consider the relationship between DAG-width and
other connectivity measures such as directed
tree-width and path-width. A consequence we obtain
is that certain NP-complete problems such as
Hamiltonicity and disjoint paths are polynomial-time
computable on graphs of bounded DAG-width.}
}
@article{bs-ipl12,
publisher = {Elsevier Science Publishers},
journal = {Information Processing Letters},
author = {Berwanger, Dietmar and Serre, Olivier},
title = {Parity games on undirected graphs},
volume = 112,
number = 23,
year = 2012,
month = dec,
pages = {928-932},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/bs-ipl12.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/bs-ipl12.pdf},
doi = {10.1016/j.ipl.2012.08.021},
abstract = {We examine the complexity of solving parity games in the special
case when the underlying game graph is undirected. For strictly
alternating games, that is, when the game graph is bipartite between the
players, we observe that the solution can be computed in linear time. In
contrast, when the assumption of strict alternation is dropped, we show
that the problem is as hard in the undirected case as it is in the
general, directed, case.}
}
@inproceedings{BM-sr14,
address = {Grenoble, France},
month = apr,
year = 2014,
volume = 146,
series = {Electronic Proceedings in Theoretical Computer Science},
editor = {Mogavero, Fabio and Murano, Aniello},
acronym = {{SR}'14},
booktitle = {{P}roceedings of the 2nd {I}nternational {W}orkshop on {S}trategic
{R}easoning ({SR}'14)},
author = {Berwanger, Dietmar and Mathew, Anup Basil},
title = {Games with Recurring Certainty},
pages = {91-96},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BM-sr14.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BM-sr14.pdf},
doi = {10.4204/EPTCS.146.12},
abstract = {Infinite games where several players seek to coordinate under
imperfect information are known to be intractable, unless the information
flow is severely restricted. Examples of undecidable cases typically
feature a situation where players become uncertain about the current state
of the game, and this uncertainty lasts forever.\par
Here we consider games where the players attain certainty about the
current state over and over again along any play. For finite-state games,
we note that this kind of \emph{recurring} certainty implies a stronger condition
of \emph{periodic} certainty, that is, the events of state certainty ultimately
occur at uniform, regular intervals. We show that it is decidable whether
a given game presents recurring certainty, and that, if so, the problem of
synthesising coordination strategies under \(\omega\)-regular winning conditions is
solvable.}
}
@article{BS13-TSI-games,
publisher = {Herm{\`e}s},
journal = {Technique et Science Informatiques},
author = {Berwanger, Dietmar and Serre, Olivier},
editor = {Berwanger, Dietmar and Serre, Olivier},
title = {Th{\'e}orie des jeux en informatique},
booktitle = {Th{\'e}orie des jeux en informatique},
volume = 32,
number = {9-10},
year = 2013,
month = dec,
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BS13-TSI-games.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BS13-TSI-games.pdf}
}
@misc{cassting-D13,
author = {Markey, Nicolas and Doyen, Laurent and Berwanger, Dietmar},
title = {Models for large-scale systems},
howpublished = {Cassting deliverable~D1.3 (FP7-ICT-601148)},
month = sep,
year = {2015},
note = {17~pages},
type = {Contract Report},
url = {http://www.cassting-project.eu/wp-content/uploads/deliv-13.pdf},
pdf = {http://www.cassting-project.eu/wp-content/uploads/deliv-13.pdf}
}
@inproceedings{BV-fsttcs15,
address = {Bangalore, India},
month = dec,
year = 2015,
volume = {45},
series = {Leibniz International Proceedings in Informatics},
publisher = {Leibniz-Zentrum f{\"u}r Informatik},
editor = {Harsha, Prahladh and Ramalingam, G.},
acronym = {{FSTTCS}'15},
booktitle = {{P}roceedings of the 35th {C}onference on
{F}oundations of {S}oftware {T}echnology and
{T}heoretical {C}omputer {S}cience
({FSTTCS}'15)},
author = {Berwanger, Dietmar and Van{ }den{ }Bogaard, Marie},
title = {Games with Delays. A~{F}rankenstein Approach},
pages = {307-319},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BV-fsttcs15.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BV-fsttcs15.pdf},
doi = {10.4230/LIPIcs.FSTTCS.2015.307},
abstract = {We investigate infinite games on finite graphs where the
information flow is perturbed by non-deterministic signalling delays. It
is known that such perturbations make synthesis problems virtually
unsolvable, in the general case. On the classical model where signals are
attached to states, tractable cases are rare and difficult to identify. In
this paper, we propose a model where signals are detached from control
states, and we identify a subclass on which equilibrium outcomes can be
preserved, even if signals are delivered with a delay that is finitely
bounded. To offset the perturbation, our solution procedure combines
responses from a collection of virtual plays following an equilibrium
strategy in the instant-signalling game to synthesise, in a
Dr.~Frankenstein manner, an equivalent equilibrium strategy for the
delayed-signalling game.}
}
@inproceedings{BV-dlt15,
address = {Liverpool, UK},
month = jul,
year = 2015,
volume = {9168},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Potapov, Igor},
acronym = {{DLT}'15},
booktitle = {{P}roceedings of the 19th {I}nternational
{C}onference on {D}evelopments in {L}anguage {T}heory
({DLT}'15)},
author = {Berwanger, Dietmar and Van{ }den{ }Bogaard, Marie},
title = {Consensus Game Acceptors},
pages = {108-119},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BV-dlt15.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BV-dlt15.pdf},
doi = {10.1007/978-3-319-21500-6_8},
abstract = {We study a game for recognising formal languages, in which two
players with imperfect information need to coordinate on a common
decision, given private input strings correlated by a finite graph. The
players have a joint objective to avoid an inadmissible decision, in spite
of the uncertainty induced by the input.\par
We show that the acceptor model based on consensus games characterises
context-sensitive languages, and conversely, that winning strategies in
such games can be described by context-sensitive languages. We also
discuss consensus game acceptors with a restricted observation pattern
that describe nondeterministic linear-time languages.}
}
@inproceedings{BMV-atva15,
address = {Shanghai, China},
month = oct,
year = {2015},
volume = {9364},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
editor = {Finkbeiner, Bernd and Pu, Geguang and Zhang, Lijun},
acronym = {{ATVA}'15},
booktitle = {{P}roceedings of the 13th {I}nternational
{S}ymposium on {A}utomated {T}echnology
for {V}erification and {A}nalysis
({ATVA}'15)},
author = {Berwanger, Dietmar and Mathew, Anup Basil and
Van{ }den{ }Bogaard, Marie},
title = {Hierarchical Information Patterns and Distributed Strategy Synthesis},
pages = {378-393},
url = {http://www.lsv.fr/Publis/PAPERS/PDF/BMV-atva15.pdf},
pdf = {http://www.lsv.fr/Publis/PAPERS/PDF/BMV-atva15.pdf},
doi = {10.1007/978-3-319-24953-7_28},
abstract = {Infinite games with imperfect information tend to be
undecidable unless the information flow is severely restricted. One
fundamental decidable case occurs when there is a total ordering among
players, such that each player has access to all the information that the
following ones receive.\par
In this paper we consider variations of this hierarchy principle for
synchronous games with perfect recall, and identify new decidable classes
for which the distributed synthesis problem is solvable with finite-state
strategies. In particular, we show that decidability is maintained when
the information hierarchy may change along the play, or when transient
phases without hierarchical information are allowed.}
}
@comment{{B-arxiv16,
author = Bollig, Benedikt,
affiliation = aff-LSVmexico,
title = One-Counter Automata with Counter Visibility,
institution = Computing Research Repository,
number = 1602.05940,
month = feb,
nmonth = 2,
year = 2016,
type = RR,
axeLSV = mexico,
NOcontrat = "",
url = http://arxiv.org/abs/1602.05940,
PDF = "http://www.lsv.fr/Publis/PAPERS/PDF/B-arxiv16.pdf",
lsvdate-new = 20160222,
lsvdate-upd = 20160222,
lsvdate-pub = 20160222,
lsv-category = "rapl",
wwwpublic = "public and ccsb",
note = 18~pages,
abstract = "In a one-counter automaton (OCA), one can read a letter
from some finite alphabet, increment and decrement the counter by
one, or test it for zero. It is well-known that universality and
language inclusion for OCAs are undecidable. We consider here OCAs
with counter visibility: Whenever the automaton produces a letter,
it outputs the current counter value along with~it. Hence, its
language is now a set of words over an infinite alphabet. We show
that universality and inclusion for that model are in PSPACE, thus
no harder than the corresponding problems for finite automata, which
can actually be considered as a special case. In fact, we show that
OCAs with counter visibility are effectively determinizable and
closed under all boolean operations. As~a~strict generalization, we
subsequently extend our model by registers. The general nonemptiness
problem being undecidable, we impose a bound on the number of
register comparisons and show that the corresponding nonemptiness
problem is NP-complete.",
}}
@article{BVdB-ijfcs18,
publisher = {World Scientific},
journal = {International Journal of Foundations of Computer Science},
author = {Berwanger, Dietmar and {van den Bogaard}, Marie},
title = {Consensus Game Acceptors and Iterated Transductions},
volume = {29},
number = {02},
pages = {165-185},
year = {2018},
month = feb,
doi = {10.1142/S0129054118400026},
url = {https://www.worldscientific.com/doi/abs/10.1142/S0129054118400026},
abstract = {We study a game for recognising formal languages, in which two players with imperfect information should coordinate on a common decision, given private input words correlated by a finite graph. The players have a common objective to avoid an inadmissible decision, in spite of the uncertainty induced by the input.
We show that the acceptor model based on consensus games characterises context-sensitive languages. Further, we describe the expressiveness of these games in terms of iterated synchronous transductions and identify a subclass that characterises context-free languages.},
pdf = {http://www.lsv.fr/~dwb/consensus.pdf}
}
@article{BM-icomp17,
publisher = {Elsevier Science Publishers},
journal = {Information and Computation},
author = {Berwanger, Dietmar and Mathew, Anup Basil},
title = {Infinite games with finite knowledge gaps},
volume = {254},
pages = {217-237},
year = {2017},
month = jun,
url = {https://doi.org/10.1016/j.ic.2016.10.009},
doi = {10.1016/j.ic.2016.10.009},
abstract = {Infinite games where several players seek to coordinate under imperfect information are deemed to be undecidable, unless the information is hierarchically ordered among the players. We identify a class of games for which joint winning strategies can be constructed effectively without restricting the direction of information flow. Instead, our condition requires that the players attain common knowledge about the actual state of the game over and over again along every play. We show that it is decidable whether a given game satisfies the condition, and prove tight complexity bounds for the strategy synthesis problem under ω-regular winning conditions given by deterministic parity automata.},
pdf = {http://lsv.fr/~dwb/rec.pdf}
}
@article{BMVdB-acta17,
publisher = {Springer},
journal = {Acta Informatica},
author = {Berwanger, Dietmar and Mathew, Anup Basil and {van den Bogaard}, Marie},
title = {Hierarchical information and the synthesis of distributed strategies},
year = {2017},
month = jun,
url = {https://doi.org/10.1007/s00236-017-0306-5},
doi = {10.1007/s00236-017-0306-5},
abstract = {Infinite games with imperfect information are known to be undecidable unless the information flow is severely restricted. One fundamental decidable case occurs when there is a total ordering among players, such that each player has access to all the information that the following ones receive. In this paper we consider variations of this hierarchy principle for synchronous games with perfect recall, and identify new decidable classes for which the distributed synthesis problem is solvable with finite-state strategies. In particular, we show that decidability is maintained when the information hierarchy may change along the play, or when transient phases without hierarchical information are allowed. Finally, we interpret our result in terms of distributed system architectures.},
pdf = {http://lsv.fr/~dwb/hi.pdf}
}
@inproceedings{BR-sr17,
address = {Liverpool, UK},
month = jul,
editor = {{van der Hoek}, Wiebe and Maubert, Bastien and Murano, Aniello and Rubin, Sasha},
acronym = {{SR}'17},
booktitle = {{P}roceedings of the 5th International Workshop on Strategic Reasoning ({SR}'17)},
author = {Dietmar Berwanger and R. Ramanujam},
title = {{Deviator Detection under Imperfect Monitoring}},
year = {2017},
url = {https://arxiv.org/abs/1712.09686},
pdf = {https://arxiv.org/pdf/1712.09686.pdf},
abstract = {Grim-trigger strategies are a fundamental mechanism for sustaining equilibria in iterated games: the players cooperate along an agreed path, and as soon as one player deviates, the others form a coalition to play him down to his minmax level. A precondition to triggering such a strategy is that the identity of the deviating player becomes common knowledge among the other players. This can be difficult or impossible to attain in games where the information structure allows only imperfect monitoring of the played actions or of the global state.
We study the problem of synthesising finite-state strategies for detecting the deviator from an agreed strategy profile in games played on finite graphs with different information structures. We show that the problem is undecidable in the general case where the global state cannot be monitored. On the other hand, we prove that under perfect monitoring of the global state and imperfect monitoring of actions, the problem becomes decidable, and we present an effective synthesis procedure that covers infinitely repeated games with private monitoring.}
}
@inproceedings{BD-stacs2020,
address = {Montpellier, France},
month = mar,
series = {Leibniz International Proceedings in Informatics},
publisher = {Leibniz-Zentrum f{\"u}r Informatik},
editor = {Bl{\"a}ser, Markus and Paul, Christophe},
acronym = {{STACS}'20},
booktitle = {{P}roceedings of the 37th {A}nnual
{S}ymposium on {T}heoretical {A}spects of
{C}omputer {S}cience
({STACS}'20)},
author = {Berwanger, Dietmar and Doyen, Laurent},
title = {Observation and Distinction. Representing Information in Infinite Games},
pages = {48:1--48:17},
doi = {10.4230/LIPIcs.STACS.2020.48},
year = 2020
}
This file was generated by bibtex2html 1.98.