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

June 15, 2016, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
joint work with Tomasz Gogacz (Entropy Bounds for Conjunctive Queries)
We study the problem of finding the worst-case size of theresult Q(D) of a fixed conjunctive query Q applied to adatabase D satisfying given functional dependencies. Weprovide a characterization of this bound in terms ofentropy …
June 8, 2016, 2:15 p.m.
Leszek Kołodziejczyk (Uniwersytet Warszawski)
The logical strength of Büchi's decidability theorem
I will talk about the strength of axioms needed to prove Büchi's decidability theorem and related results concerning automata on infinite words. The talk will be based on joint work with Henryk Michalewski, Michał Skrzypczak …
June 1, 2016, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
joint work with Charles Paperman and Michal Pilipczuk (Schema validation via streaming circuits)
I will talk about recognizing regular tree languages in a model wherethe input is streamed to the recognizer as a sequence of tags(possibly representing a tree in the usual XML encoding). It is knownthat a …
May 25, 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 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 …