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

2 listopada 2016 14:15
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 …
19 października 2016 14:15
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 …
12 października 2016 14:15
Laure Laviaud (Uniwersytet Warszawski)
About max-plus and min-plus automata: (un)decidabilit)
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 …
5 października 2016 14:15
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 …
15 czerwca 2016 14:15
Szymon Toruńczyk (Uniwersytet Warszawski)
Entropy Bounds for Conjunctive Queries (joint work with Tomasz Gogacz)
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 …
8 czerwca 2016 14:15
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 …
1 czerwca 2016 14:15
Filip Murlak (Uniwersytet Warszawski)
Schema validation via streaming circuits (joint work with Charles Paperman and Michal Pilipczuk)
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 …
25 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 …
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 …