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

Jan. 4, 2012, 2:15 p.m.
Thomas Place (Uniwersytet Warszawski)
joint work with Mikołaj Bojańczyk (Regular languages of infinite trees that are boolean combinations of open sets)
This talk will be about boolean (not necessarily positive)combinations of open sets. I will present a decidable characterizationof the regular languages of infinite trees that are boolean combinationof open sets. In other words, I will …
Dec. 21, 2011, 2:15 p.m.
-
No seminar
Dec. 14, 2011, 2:15 p.m.
-
No seminar
Dec. 7, 2011, 2:15 p.m.
Martin Lang (RWTH Aachen)
Bounded reachability in resource pushdown systems
In the talk, we present a model for recursive programs with resourceconsumption. It combines the well-known theory of pushdown systems,which are capable of modeling recursive programs, and the recent theoryof regular cost functions, which can …
Nov. 30, 2011, 2:15 p.m.
Jerome Leroux (LaBRI, Bordeaux)
Vector Addition System Reachability Problem
The reachability problem for Vector Addition Systems (VASs) is a central problem of net theory. The general problem is known decidable by algorithms exclusively based on the classical Kosaraju-Lambert-Mayr-Sacerdote-Tenney decomposition (KLMTS decomposition). Recently from this …
Nov. 23, 2011, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
Separation property for wB and wS-regular languages
In this paper we show that wB and wS-regular languages satisfy the following separation-type theorem:Given two disjoint languages both recognised by wB (resp. wS)-automata, there exists an w-regular language separating them.In particular if a language …
Nov. 16, 2011, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
joint work with Anuj Dawar (Zero-one laws and planar graphs)
It is well known that first order logic admits a zero one law: a probability that a random structure of size $n$ tends to a limit of either 0 or 1 as $n$ tends to …
Nov. 9, 2011, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
joint work with Anuj Dawar (Bounded degree and planar spectra)
There are many problems about which we know a lot in the unrestrictedclasses, but are still not researched thoroughly in the restricted case.One of them was the problem of spectra of formulae. A set of …
Nov. 2, 2011, 2:15 p.m.
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 …
Oct. 26, 2011, 2:15 p.m.
Ł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 …
Oct. 19, 2011, 2:15 p.m.
-
No seminar
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 …