Organizers

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Information

Wednesdays, 2:15 p.m. , room: 5440

Research fields

List of talks

Oct. 12, 2011, 2:15 p.m.
Piotr Hofman (Uniwersytet Warszawski)
joint work with Sławek Lasota and Wojtek Czerwiński (Reachability problem for stateless multi-pushdown automata)
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 …
Oct. 5, 2011, 2:15 p.m.
Damian Niwiński (Uniwersytet Warszawski)
joint work with Andre Arnold and Henryk Michalewski (On separation question for tree languages)
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, …
June 15, 2011, 2:15 p.m.
Alessandro Facchini (Uniwersytet Warszawski)
joint work with Filip Murlak and Jacques Duparc (Definable Operations On Weakly Recognizable Sets of Trees)
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 …
June 8, 2011, 2:15 p.m.
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 …
June 1, 2011, 2:15 p.m.
-
No seminar
May 25, 2011, 2:15 p.m.
-
No seminar
May 18, 2011, 2:15 p.m.
-
No seminar
May 11, 2011, 2:15 p.m.
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 …
May 4, 2011, 2:15 p.m.
-
No seminar
April 27, 2011, 2:15 p.m.
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 …
April 20, 2011, 2:15 p.m.
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 …
April 13, 2011, 2:15 p.m.
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.
April 6, 2011, 2:15 p.m.
Michał Pilipczuk (Uniwersytet Warszawski)
Solving problems parameterized by tree-width in single exponential time: a logical approach
We introduce a variant of modal logic on graphs, dubbed EXISTENTIAL COUNTINGMODAL LOGIC (ECML), which captures a vast majority of problems knownto be tractable in single exponential time when parameterized by treewidth. Itappears that all …
March 30, 2011, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
Towards decidability of weak bisimilarity on BPP
Consider transition system generated by commutative context-free grammar,so called BPP. Strong bisimilarity is known to be PSPACE-complete on this classof infinite graphs, weak bisimilarity (with possible epsilon transitions) is important and longstanding open problem.I will …
March 23, 2011, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
No satisfiability measure for first-order logic on graphs
Consider MSO on graphs, with quantification over sets of edges andsets of nodes.Tree-width is a good measure of graphs for this logic because: a) for every k,satisﬁability is decidable over graphs of tree-width at most …