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
-
-
-
25 stycznia 2012 14:15
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 …
-
18 stycznia 2012 14:15
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 …
-
11 stycznia 2012 14:15
Thomas Place (Uniwersytet Warszawski)
Regular languages of infinite trees that are boolean combinations of open sets - continuation (joint work with Mikołaj Bojańczyk)
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 …
-
4 stycznia 2012 14:15
Thomas Place (Uniwersytet Warszawski)
Regular languages of infinite trees that are boolean combinations of open sets (joint work with Mikołaj Bojańczyk)
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 …
-
-
-
7 grudnia 2011 14:15
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 …
-
30 listopada 2011 14:15
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 …
-
23 listopada 2011 14:15
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 …
-
16 listopada 2011 14:15
Eryk Kopczyński (Uniwersytet Warszawski)
Zero-one laws and planar graphs (joint work with Anuj Dawar)
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 …
-
9 listopada 2011 14:15
Eryk Kopczyński (Uniwersytet Warszawski)
Bounded degree and planar spectra (joint work with Anuj Dawar)
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 …
-
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 …
