Organizers

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

Information

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

Research fields

List of talks

March 16, 2016, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Michał Pilipczuk
We prove a conjecture of Courcelle, which states that a graph property is definable in mso with modular counting predicates on graphs of constant treewidth if, and only if it is recognizable in the following …
March 9, 2016, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
Expressivity of probabilistic modal logic, the easy way
Probabilistic modal logic is a very basic modal logic (propositional logic plus a diamond-like modality) interpreted on probabilistic transition systems. It is expressive, i.e., its logical equivalence coincides with bisimilarity, and the proof of this …
March 2, 2016, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
joint work with B.Klin, S. Lasota, J. Ochremiak
We prove decidability of the existence of a homomorphism between two given infinite structures with finite signatures which are definable, or interpret, in the natural numbers with equality. The result uses Pestov's theorem from topological …
Jan. 27, 2016, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
joint work with S. Lasota, J. Ochremiak and S. Toruńczyk
Consider infinite relational structures where both the universe and the relations are definable by first-order formulas over natural numbers with equality. An example of such a structure is the countable clique graph, or a graph …
Jan. 20, 2016, 2:15 p.m.
Amal Dev Manuel (Uniwersytet Warszawski)
joint work with Thomas Colcombet, Denis Kuperberg, and Szymon Toruńczyk
In this work we show how to decide if a given regular cost function isrecognised by a Min (Max) automaton. This is achieved bycharacterising the classes of cost functions of the these automataalgebraically. Also a …
Jan. 13, 2016, 2:15 p.m.
Marcin Wrochna (Uniwersytet Warszawski)
On space efficiency of algorithms working on structural decompositions of graphs
Motivated by failed attempts at making dynamic algorithms on tree-width use less space (without using more time), we look at this from a complexity-theoretic point of view. I will mention relations to Savitch's theorem and …
Dec. 16, 2015, 2:15 p.m.
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 …
Dec. 9, 2015, 2:15 p.m.
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.
Dec. 2, 2015, 2:15 p.m.
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 …
Nov. 25, 2015, 2:15 p.m.
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 …
Nov. 18, 2015, 2:15 p.m.
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 …
Nov. 4, 2015, 2:15 p.m.
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 …
Oct. 28, 2015, 2:15 p.m.
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). …
Oct. 21, 2015, 2:15 p.m.
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 …
Oct. 14, 2015, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
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, …