This shows you the differences between two versions of the page.

Both sides previous revision Previous revision | |||

home [2013/09/13 12:49] Antonin Kucera [About the Laboratory] |
home [2013/10/23 10:17] (current) Antonin Kucera [About the Laboratory] |
||
---|---|---|---|

Line 4: | Line 4: | ||

* //Game theory in formal verification.// The interaction between a system and its environment can be seen as a game of two players (controller and environment) with antagonistic objectives. We are particularly interested in games with infinite arenas, continuous-time games, and multi-objective games. We try to understand optimal strategies in these games and invent efficient algorithms for their synthesis. | * //Game theory in formal verification.// The interaction between a system and its environment can be seen as a game of two players (controller and environment) with antagonistic objectives. We are particularly interested in games with infinite arenas, continuous-time games, and multi-objective games. We try to understand optimal strategies in these games and invent efficient algorithms for their synthesis. | ||

* //Foundations of performance analysis.// Performance analysis measures how efficiently a given system uses its resources. We concentrate on developing mathematical models and algorithms for analyzing and predicting performance of real-time systems. | * //Foundations of performance analysis.// Performance analysis measures how efficiently a given system uses its resources. We concentrate on developing mathematical models and algorithms for analyzing and predicting performance of real-time systems. | ||

- | * //Parameterized complexity and algorithms.// The theory of parameterized complexity truly revolutionarized the area of algorithm design in recent years, as it provides a way to attack many NP-hard problems with algorithms that are efficient wrt. certain additional restrictions (the parameters). We focus on design of parameterized combinatorial algorithms, on algorithmic metatheorems for logics, and complexity lower bounds. | + | * //Parameterized complexity and algorithms.// The theory of parameterized complexity provides a way to attack many NP-hard problems with algorithms that are efficient wrt. certain additional restrictions (the parameters). We focus on parameterized combinatorial algorithms, algorithmic metatheorems for logics, and complexity lower bounds. |

- | * //Structural and topological graph theory.// Graphs and their mathematical theory underline much of our algorithmic and (parameterized) complexity research. We are particularly interested in the structural graph theory, studying various kinds of graph decompositions and related width and depth parameters, and in topological graph theory, where our main emphasis is on the graph crossing number and on planar covers and emulators. | + | * //Structural and topological graph theory.// In the structural graph theory, we concentrate on various kinds of graph decompositions and related width and depth parameters. In topological graph theory, our main emphasis is on the graph crossing number and on planar covers and emulators. |

* //Program analysis.// The goal of program analysis is to automatically gain some useful information (like the existence of errors or security holes) about a given program. Our research is focused on improving the functionality of basic program analysis techniques, designing new techniques, and evaluating the efficiency and applicability of these techniques. | * //Program analysis.// The goal of program analysis is to automatically gain some useful information (like the existence of errors or security holes) about a given program. Our research is focused on improving the functionality of basic program analysis techniques, designing new techniques, and evaluating the efficiency and applicability of these techniques. | ||