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

Feb. 29, 2012, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
Descriptive properties of regular languages of thin trees
Feb. 22, 2012, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Thomas Place (Model theory with nominal sets)
Using nominal sets, we define a uniform approach to logics over data words, data trees, data graphs and so on. The key technical result is that, in the equality symmetry, formulas that quantify over data …
Feb. 15, 2012, 2:15 p.m.
Martin Zimmermann (Uniwersytet Warszawski)
Solving Infinite Games with Bounds
In this talk I will present results reported in my PhD thesis.Parameterized linear temporal logic (PLTL) is an extension of Linear Temporal Logic (LTL) by temporal operators equipped with variables for time bounds. One can …
Feb. 8, 2012, 2:15 p.m.
-
No seminar
Feb. 1, 2012, 2:15 p.m.
-
No seminar
Jan. 25, 2012, 2:15 p.m.
Tomasz Idziaszek (Uniwersytet Warszawski)
An algebra for languages of infinite thin trees - continuation
Still there is no satisfactory algebraic framework which deals with languages of infinite trees. For example, a framework which we used with Mikołaj to effectively characterize EF logic is an algebra with infinite number of …
Jan. 18, 2012, 2:15 p.m.
Tomasz Idziaszek (Uniwersytet Warszawski)
An algebra for languages of infinite thin trees
Still there is no satisfactory algebraic framework which deals with languages of infinite trees. For example, a framework which we used with Mikołaj to effectively characterize EF logic is an algebra with infinite number of …
Jan. 11, 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 - continuation)
This is the continuation of last week talk. Last week I presented a decidable characterization of the class of trees languages definable by boolean combinations of open sets. This week I will present part of …
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 …