Organizers

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

Information

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

Research fields

List of talks

May 18, 2016, 2:15 p.m.
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 …
May 11, 2016, 2:15 p.m.
-
There is no seminar this week
May 4, 2016, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Lorenzo Clemente, Sławomir Lasota and Charles Paperman (Regular Separability of Parikh Automata Languages)
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 …
April 27, 2016, 2:15 p.m.
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 …
April 20, 2016, 2:15 p.m.
Marcin Przybyłko (Uniwersytet Warszawski, University of New Caledonia)
joint work with Michał Skrzypczak (Branching games with regular winning sets)
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 …
April 13, 2016, 2:15 p.m.
Adam Witkowski (Uniwersytet Warszawski)
joint work with Wim Martens (SCULPT: describing the tabular data)
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 …
April 6, 2016, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Wim Martens, Lorijn van Rooijen, Marc Zeitoun and Georg Zetzsche (Separability of context-free languages by piecewise testable languages)
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 …
March 30, 2016, 2:15 p.m.
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 …
March 23, 2016, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
joint work with L. Clemente, S. Salvati, I. Walukiewicz (The Diagonal Problem for Higher-Order Recursion Schemes is Decidable)
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 …
March 16, 2016, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Michał Pilipczuk (On the Courcelle Conjecture)
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 (Homomorphism problems for first-order definable structures)
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 (Homomorphism problems for first-order definable structures)
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 (Expressiveness of Min/Max Automata)
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 …