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

18 maja 2016 14:15
Joost Winter (Uniwersytet Warszawski)
Decidability results for weighted-language equivalence via bisimulation up-to
In this talk, I will present work earlier presented at FoSSaCS 2015, showing how the bisimulation-up to technique, the decidablity of weighted language equivalence for Noetherian semirings (originally proven by Ésik and Maletti) can be …
11 maja 2016 14:15
-
There is no seminar this week
4 maja 2016 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Regular Separability of Parikh Automata Languages (joint work with Lorenzo Clemente, Sławomir Lasota and Charles Paperman)
This is a part of a plan to understand when two languages are separable by some regular language and actually a work in progress. I will show that regular separability is decidable for two languages …
27 kwietnia 2016 14:15
Damien Pous (ENS Lyon)
Kleene algebra, from automata algorithms to proof assistants
Kleene algebra are the algebraic counterpart to finite automata on finite words. First I will describe two recent algorithms for finite automata: one exploiting bisimulations up to congruence to tame non-determinism, and one exploiting binary …
20 kwietnia 2016 14:15
Marcin Przybyłko (Uniwersytet Warszawski, University of New Caledonia)
Branching games with regular winning sets (joint work with Michał Skrzypczak)
A branching game is a game that produces trees instead of paths. This is achieved by introducing new type of positions -- branching positions -- that split the game into two independent sub-games. M.Mio defined …
13 kwietnia 2016 14:15
Adam Witkowski (Uniwersytet Warszawski)
SCULPT: describing the tabular data (joint work with Wim Martens)
SCULPT is a schema language for tabular data (like CSV files) proposed by Wim Martens, Frank Neven and Stan Vansummeren. I will talk about a variant of satisfiability problem which is tractable for a robust …
6 kwietnia 2016 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Separability of context-free languages by piecewise testable languages (joint work with Wim Martens, Lorijn van Rooijen, Marc Zeitoun and Georg Zetzsche)
I will show that separability of context-free languages by piecewise testable languages is decidable (which is surprising as deciding whether a context-free language is piecewise testable is undecidable). Then I will generalize this result and …
30 marca 2016 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
A gap property for Buchi languages of infinite trees
In this talk I will speak about classes of languages of infinite treesdefinable in monadic second-order (MSO) logic. My main interest willbe in two such classes: languages that are definable in the weakvariant of MSO …
23 marca 2016 14:15
Paweł Parys (Uniwersytet Warszawski)
The Diagonal Problem for Higher-Order Recursion Schemes is Decidable (joint work with L. Clemente, S. Salvati, I. Walukiewicz)
A non-deterministic recursion scheme recognizes a language of finite trees. This very expressive model can simulate, among others, higher-order pushdown automata with collapse. We show the decidability of the diagonal problem for schemes: given a …
16 marca 2016 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
On the Courcelle Conjecture (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 …
9 marca 2016 14:15
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 …
2 marca 2016 14:15
Szymon Toruńczyk (Uniwersytet Warszawski)
Homomorphism problems for first-order definable structures (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 …
27 stycznia 2016 14:15
Bartek Klin (Uniwersytet Warszawski)
Homomorphism problems for first-order definable structures (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 …
20 stycznia 2016 14:15
Amal Dev Manuel (Uniwersytet Warszawski)
Expressiveness of Min/Max Automata (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 …
13 stycznia 2016 14:15
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 …