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

8 października 2014 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Clones and tree languages (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 …
1 października 2014 14:15
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 …
25 czerwca 2014 14:15
Filip Mazowiecki (Uniwersytet Warszawski)
Decidability of Weak Logics with Deterministic Transitive Closure (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 …
18 czerwca 2014 14:15
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 …
4 czerwca 2014 14:15
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 …
28 maja 2014 14:15
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 …
21 maja 2014 14:15
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 …
14 maja 2014 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Deciding branching bisimilarity on BPA in NEXPTIME (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 …
7 maja 2014 14:15
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 …
30 kwietnia 2014 14:15
-
No seminar this week
23 kwietnia 2014 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Star height via games
I will show a simplified proof of decidability for the star height problem. The simplified proof follows the same lines as the proof of Daniel Kirsten: first the star height problem is reduced to the …
16 kwietnia 2014 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
Kolmogorov's R-sets and regular tree languages
R-sets, introduced in 1928 by Andrey Kolmogorov, were designed as a wide class of well-behaved sets that can be described in a constructible way. One of the crucial properties of this class is universal measurability …
9 kwietnia 2014 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
Determinisation of History Deterministic Automata
A non-deterministic automaton is history deterministic if it is possible to resolve its choices in a way that depends only on the already read input. Such automata appear naturally in synthesis problems and qualitative models.One …
2 kwietnia 2014 14:15
Szymon Toruńczyk (Uniwersytet Warszawski)
Turing Machine with Atoms and Descriptive Complexity
We relate Turing Machines with Atoms to a certain logic over finite structures. As an application to Descriptive Complexity Theory, within a substantial class of relational structures including Cai-Fürer-Immerman graphs, we precisely characterize those subclasses …
26 marca 2014 14:15
Luc Dartois (LIAFA, Paris)
Adding Modular predicates
When considering classes of regular languages, it is a primordial question to be able to determine if a given language belongs to it. Over fragments of logic, this question has been largely studied since McNaughton-Papert …