Organizatorzy

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

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

16 grudnia 2015 14:15
Eryk Kopczyński (Uniwersytet Warszawski)
Invisible pushdown languages
Context free languages allow one to express data with hierarchical structure, at the cost of losing some of the useful properties of languages recognized by finite automata on words. However, it is possible to restore …
9 grudnia 2015 14:15
Sławomir Lasota (Uniwersytet Warszawski)
Timed pushdown automata, equations over sets of integers, and branching vector addition systems with states in dimension 1
Mutual reductions between the three models will be discussed. Decidability of emptiness is an intriguing open problem.
2 grudnia 2015 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
A probabilistic logic for infinite trees
Consider the following quantifier for infinite trees: “the set of paths π which make φ(π) true has zero probability”.We consider weak MSO over infinite trees extended with this quantifier. I would like to report on …
25 listopada 2015 14:15
Martin Zimmermann (Saarland University)
Unbounded Lookahead in WMSO+U Games
Delay games are two-player games of infinite duration in which one player may delay her moves to obtain a lookahead on her opponent’s moves. We consider delay games with winning conditions expressed in weak monadic …
18 listopada 2015 14:15
Marcin Przybyłko (Uniwersytet Warszawski, University of New Caledonia)
A plantation game -- from practice to theory and back again
In this talk, I will present the results of collaboration with Institut Agronomique Néo-Calédonien in which we have been trying to createa simple framework that would be able to both, model evolution of a system …
4 listopada 2015 14:15
Andrea Cali (Birkbeck College, University of London)
Querying the Deep Web: old and new perspectives
The Deep Web is constituted by data that are accessible on theweb, typically through HTML forms, but are not indexable bysearch engines due to their static nature. Processing queries onDeep Web data poses significant challenges …
28 października 2015 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
On separation and unambiguity for register automata
Nondeterministic register automata introduced by Kaminski form one of the most natural models of recognition for data-labelled structures,in particular data words. Although the emptiness problem is decidablefor them, they lack some closure properties (e.g. complement). …
21 października 2015 14:15
Colin Riba (École Normale Supérieure de Lyon)
Fibrations of Tree Automata
We propose a notion of morphism between tree automata based on game semantics. These morphisms are winning strategies on a synchronous restriction of the linear implication between acceptance games of automata seen as simple games.Our …
14 października 2015 14:15
Filip Murlak (Uniwersytet Warszawski)
A decidability result for conjunctive queries over data trees (joint work with Wojciech Czerwinski, Claire David, and Pawel Parys)
I will show how to decide validity and containment for unions ofconjunctive queries in which each conjunctive query uses either dataequalities or data inequalities (but not both). This extendssimultaneously two decidability results by Björklund, Martens, …
7 października 2015 14:15
Jerzy Marcinkowski (Uniwersytet Wrocławski)
The Hunt for a Red Spider: Conjunctive Query Determinacy Problem is Undecidable
Imagine there is a set {Q_1,...Q_n} of database queries (conjunctivequeries), and, for any database instance D, we have access to theviews Q_1(D),...Q_n(D) defined by these queries.Then they give us another query, Q, and we would …
1 lipca 2015 14:15
-
There is no seminar this week
24 czerwca 2015 14:15
Nathanael Fijalkow (Uniwersytet Warszawski)
The LoCo conjecture
I will talk about the LoCo conjecture, which has been conjecture by Christof Löding and Thomas Colcombet in 2010. It talks about games with counters, and implies the decidability of the Rabin-Mostowski hierarchy.I will show …
17 czerwca 2015 14:15
Joost Winter (Uniwersytet Warszawski)
Distributive Laws: an Introduction
In this talk, I will introduce various types of distributive laws as can be found in category. In particular, I will introduce distributive laws between monads, as well as distributive laws between a monad and …
3 czerwca 2015 14:15
-
There is no seminar this week
27 maja 2015 14:15
Leszek Kołodziejczyk (Uniwersytet Warszawski)
How unprovable is Rabin's theorem?
Second-order arithmetic is an axiomatic theory in a language with two sorts of variables, one for representing natural numbers and the other for representing sets of natural numbers. The theory is roughly as strong as …