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

Jan. 18, 2017, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Algorithms on infinite structures
I will talk about how one can evaluate programs over infinite structures, and about some attempts of measuring the computational complexity of such programs. Here are some relevant keywords: sets with atoms, LOIS, while-programs with …
Jan. 11, 2017, 2:15 p.m.
Joost Winter (Uniwersytet Warszawski)
or: power series in a single variable (Decidability of equivalence of algebraic streams)
In this talk, I will show the decidability of equivalence of algebraic streams (or, equivalentnly, power series in a single variable) over commutative rings that are, in some sense "computable". This result is a partial …
Dec. 14, 2016, 2:15 p.m.
Joost Winter (Uniwersytet Warszawski)
Valence automata as weighted automata
In this talk we will discuss a way in which it is possible to regard valence automata as weighted automata over suitably chosen semirings, together with a "threshold language" interpretation. This way, it is possible …
Dec. 7, 2016, 2:15 p.m.
Sebastian Siebertz (Uniwersytet Warszawski)
On neighbourhood complexity and kernels for distance-r dominating sets on nowhere dense classes of graphs
The r-neighbourhood complexity of a vertex set A from a graph G is the number of subsets of A which are induced as r-neighbourhoods of vertices of G. We prove that every sufficiently large set …
Nov. 30, 2016, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
WQO Dichotomy Conjecture
I will neither state nor prove any interesting theorem. Instead, I'll formulate an interesting (I hope) conjecture about applicability of well quasi orders (WQO) in decision problems for infinite state systems with data (like Petri …
Nov. 16, 2016, 2:15 p.m.
Petr Jancar (Technical University of Ostrava)
Deciding bisimulation equivalence and semantic finiteness of first-order grammars
The plan is to briefly recall the ideas of the decidability proof for bisimulation equivalence of first-order grammars; the proof (presented at ICALP'14) is an alternative for Senizergues's proof for equational graphs with finite out-degree …
Nov. 9, 2016, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Lorenzo Clemente, Sławomir Lasota and Charles Paperman (Separability of Reachability Sets of Vector Addition Systems)
Given two families of sets F and G, the separability problem of sets from a class G by sets from a class F asks whether for two given sets U, V in G there exists …
Nov. 2, 2016, 2:15 p.m.
Vincent Penelle (Uniwersytet Warszawski)
Rewriting Higher-order Stack Trees
In this talk, I will present the model of stack tree rewriting systems, as a common extension of higher-order pushdown automata and ground tree rewriting system. I will define the model of stack trees, the …
Oct. 19, 2016, 2:15 p.m.
A V Sreejith (Uniwersytet Warszawski)
Monadic second order logic over countable linear orderings
We will look at words over countable linear orderings (for example, omega words, words over rationals etc). We will then look at languages over such words definable by MSO[<]. Is satisfiability of MSO decidable? Is …
Oct. 12, 2016, 2:15 p.m.
Laure Laviaud (Uniwersytet Warszawski)
un)decidabilit (About max-plus and min-plus automata:)
In this talk, I will present min-plus and max-plus automata, which are a kind of weighted automata computing functions from the set of words to the integers. I will give some classical results about decision …
Oct. 5, 2016, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
A non-regular language of infinite trees that is recognised by a finitary algebra
I will present an example, resulting from joint work with Bartek Klin. One natural approach to algebras for infinite trees is to use an algebra which has infinitely many sorts {0,1,2,..}, where sort n represents …
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 …