Nie jesteś zalogowany |
Cotygodniowe seminarium badawcze
Organizatorzy
- prof. dr hab. Mikołaj Bojańczyk
- prof. dr hab. Damian Niwiński
Informacje
środy, 14:15 , sala: 5440Dziedziny badań
Lista referatów
-
2 listopada 2011 14:15
Alexander Kartzow (Universitat Leipzig)
A Survey on Model Checking for Collapsible Pushdown Graphs
The model checking problem for some logic L and a class ofgraphs C is the problem to decide, on input a graph G from C and aformula phi from L, whether G satisfies phi.We first …
-
26 października 2011 14:15
Łukasz Kaiser (LIAFA, Paris)
Model Checking the Quantitative mu-Calculus on Infinite Transition Systems
We consider the model-checking problem for a quantitativeextension of the modal mu-calculus on two classes of infinitequantitative transition systems. The first class, initialized linearhybrid systems, is motivated by verification of systems whichexhibit continuous dynamics. We …
-
-
12 października 2011 14:15
Piotr Hofman (Uniwersytet Warszawski)
Reachability problem for stateless multi-pushdown automata (joint work with Sławek Lasota and Wojtek Czerwiński)
It is well known that multi-pushdown automata are Turing complete.However, one obtains an interesting class under assumption that theautomata have only one state. Surprisingly, the reachability problembecames decidable and the complexity isn't as high as …
-
5 października 2011 14:15
Damian Niwiński (Uniwersytet Warszawski)
On separation question for tree languages (joint work with Andre Arnold and Henryk Michalewski)
Once we know that a class C is different from co-C,we may ask a more subtle question: can any two disjointsets in C be ``approximated'' by their super-sets inco-C, still disjoint ?In the classical hierarchies, …
-
15 czerwca 2011 14:15
Alessandro Facchini (Uniwersytet Warszawski)
Definable Operations On Weakly Recognizable Sets of Trees (joint work with Filip Murlak and Jacques Duparc)
We introduce a class of alternating tree automata, called game automata, which is the largest class for which the substitution operation preserves Wadge equivalence. Moreover it contains all deterministic automata.We then show that for the …
-
8 czerwca 2011 14:15
Andre Arnold (Labri, Bordeaux)
Separation theorems in the Wagner hierarchy of rational omega-langauges
In the Borel hierarchy every pair of disjointPi_n sets is separable by a Delta_n set, andthere are pairs of disjoint Sigma_n sets whichare not separable.It is still a partially open question whether these separation results …
-
-
-
-
11 maja 2011 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Nominal Computation
I will present a programming language that manipulates nominal sets.In the programming language, an orbit finite set behaves like a finiteset. One can execute in finite time a loop over all elements of anorbit finite …
-
-
27 kwietnia 2011 14:15
Martin Zimmermann (RWTH Aachen)
Solving Muller Games via Safety Games
Using results on finite-time Muller Games (which are defined using scoring functions that measure how often a given loop in the arena has been visited) we showhow to determine the winner and a finite-state winning …
-
20 kwietnia 2011 14:15
Laurent Braud (Uniwersytet Warszawski)
Limits of interpretations and unfoldings
The original motivation was the characterisation of more structureswith decidable MSO theory. We consider the transformation approach :operations that preserve decidability include MSO-interpretations andunfoldings, which can be used to build the Caucal hierarchy. In anattempt …
-
13 kwietnia 2011 14:15
Paweł Parys (Uniwersytet Warszawski)
The excluded grid theorem
I will present a proof of the excluded grid theorem of Robertson and Seymour: a graph has no large grid minor if and only if it has small tree-width.
