Person

Laurent Doyen

This person is no longer with EPFL

Related publications (12)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Strategy construction for parity games with imperfect information

Laurent Doyen

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, i.e., to determine the winning regions of players and corresponding ...

2010

Expressiveness And Closure Properties For Quantitative Languages

Laurent Doyen

Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the ma ...

2010

Quantitative generalizations of classical languages, which assign to each word a real number instead of a Boolean value, have applications in modeling resource-constrained computation. We use weighted automata (finite automata with transition weights) to d ...

2010

Alpaga: A Tool for Solving Parity Games with Imperfect Information

Laurent Doyen

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

2009

Probabilistic Weighted Automata

Laurent Doyen

Nondeterministic weighted automata are finite automata with numerical weights on transitions. They define quantitative languages

L

that assign to each word

w

a real number

L(w)

. The value of an infinite word

w

is computed as the maximal value of al ...

2009

Antichains For The Automata-Based Approach To Model-Checking

Laurent Doyen

We propose and evaluate antichain algorithms to solve the universality and language inclusion problems for nondeterministic Buchi automata, and the emptiness problem for alternating Buchi automata. To obtain those algorithms, we establish the existence of ...

2009

We consider imperfect-information parity games in which strategies rely on observations that provide imperfect information about the history of a play. To solve such games, i.e. to determine the winning regions of players and corresponding winning strategi ...

2008

On the Power of Imperfect Information

Laurent Doyen

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

2008

Quantitative Languages

Laurent Doyen

Quantitative generalizations of classical languages, which assign to each word a real number instead of a boolean value, have applications in modeling resource-constrained computation. We use quantitative automata (finite automata with transition weights) ...

2008

Probabilistic Weighted Automata

Laurent Doyen

Nondeterministic weighted automata are finite automata with numerical weights on transitions. They define quantitative languages

L

that assign to each word

w

a real number

L(w)

. The value of an infinite word

w

is computed as the maximal value of al ...

2009