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

Nov. 19, 2014, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
joint work with Claire David and Nadime Francis
I will talk about satisfiability problems for tree patterns under different semantics. I will focus on the following problem: decide if a given tree pattern can be matched injectively in some tree from a fixed …
Nov. 12, 2014, 2:15 p.m.
Joost Winter (Uniwersytet Warszawski)
The coalgebraic approach to weighted automata: an introduction
In this talk, I will give an overview of how weighted automata can be seen as coalgebras and bialgebras. The coalgebraic approach to weighted automata was developed by Rutten, Bonsangue, Bartels, Silva, Bonchi, and others, …
Nov. 5, 2014, 2:15 p.m.
Ranko Lazic (University of Warwick)
Multi-dimensional energy games and related problems
I shall present some recent work on multi-dimensional energy games, which happen to have strong connections to several questions involving finite-system simulations, zero-reachability games and alternating termination of vector addition systems.The work is joint with …
Oct. 29, 2014, 2:15 p.m.
Henryk Michalewski (Uniwersytet Warszawski)
joint work with Matteo Mio
The decidability of the "Satisfiability" problem is a majoropen problem in the area of logics of probabilistic programs such as,e.g., PCTL*.We introduce an extension of "MSO with Null quantifier": MSO+N. Thesystem MSO+N is sufficiently expressive …
Oct. 22, 2014, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
First-Order Logic on CPDA Graphs
It is known that configuration graphs of higher-order pushdown automata (without the collapse operation) coincide with graphs in the Caucal hierarchy. In particular these graphs have decidable MSO theory. The next step is to consider …
Oct. 15, 2014, 2:15 p.m.
Lorenzo Clemente (Uniwersytet Warszawski)
Beyond worst-case analysis for mean-payoff games
Mean-payoff games are classical quantitative games where the objective is to optimise the long-term average payoff.In this purely adversarial setting, one is interested in whether Player 0 has a strategy that guarantees a certain mean-payoff …
Oct. 8, 2014, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Henryk Michalewski
I will talk about work in progress, which tries to connect• the project to classify fragments of MSO on finite trees, e.g. decide which regular languages of finite trees are definable in first-order logic• results …
Oct. 1, 2014, 2:15 p.m.
Nathanael Fijalkow (Uniwersytet Warszawski)
Playing Safe
The general question we consider is to characterize the memory size of winning strategies in two-player games.In this talk, I will show that for the special case of safety conditions (aka topologically closed conditions), the …
June 25, 2014, 2:15 p.m.
Filip Mazowiecki (Uniwersytet Warszawski)
joint work with Witold Charatonik and Emanuel Kieroński
The deterministic transitive closure operator, added to languages containing even only two variables, allows to express many natural properties of a binary relation, including being a linear order, a tree, a forest or a partial …
June 18, 2014, 2:15 p.m.
Jan Rutten (CWI and Radboud Universiteit Nijmegen)
The dual equivalence of equations and coequations for automata
Because of the isomorphism:(X x A) -> X = X -> (A -> X)the transition structure t: X -> (A -> X)of a deterministic automaton with state set Xand with inputs from an alphabet A …
June 4, 2014, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
Distributive laws of monads over comonads can't be formatted
We use bialgebraic methods to prove that bialgebraic methods are useless. Specifically, we show that distributive laws of monads over comonads, which are a common abstract generalizationof some concrete formats of well-structured operational definitions, do …
May 28, 2014, 2:15 p.m.
Szczepan Hummel (Uniwersytet Warszawski)
Unambiguity-preserving operations on tree languages that lift topological complexity
The talk reports my results concerning lower bound for the topological complexity of the class of languages of infinite trees recognized by unambiguous automata.At the beginning I will show operation sigma that has the following …
May 21, 2014, 2:15 p.m.
Tomasz Gogacz (Uniwersytet Wrocławski)
All instances termination of chase is undecidable
We show that all instances termination of chase is undecidable.More precisely, there is no algorithm deciding, for a given set Tconsisting of Tuple Generating Dependencies (a.k.a. Datalog+/- program), whether the T-chase on D will terminate …
May 14, 2014, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Petr Jancar
Branching bisimilarity is a variant of the weak bisimilarity. Recently there was a big progress in deciding bisimilarity on context-free systems: decidability was shown. I will present the main ideas of this result and explain …
May 7, 2014, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
How Many Numbers Can a Lambda-term Contain?
It is well known, that simply-typed lambda-terms can be used to represent numbers, as well as some other data types, in particular tuples of numbers. We prove, however, that in a lambda-term of a fixed …