Organizers

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

Information

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

Research fields

List of talks

March 21, 2018, 2:15 p.m.
Marcin Jurdziński (University of Warwick)
joint work with Laure Daviaud and Ranko Lazić
In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payoff). The game is zero-sum and …
March 14, 2018, 2:15 p.m.
Bartosz Piotrowski (Uniwersytet Warszawski)
Automated Reasoning in Large Theories and Premise Selection with Machine Learning
In the talk I will briefly overview current state-of-the-art in the fields of Formal Mathematics and Automated Theorem Proving and how Machine Learning techniques can be fruitfully applied in these domains. One of crucial problems …
March 7, 2018, 2:15 p.m.
-
No seminar
Feb. 28, 2018, 2:15 p.m.
Pierre Pradic (ENS de Lyon)
Joint work with Colin Riba
Church synthesis problem asks whether or not one can synthesize a 1-Lipschitz (or synchronous) function according to a specification of the type ∀ X ∃ Y φ(X,Y) expressed in the language of MSO over ω. …
Feb. 21, 2018, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Transducers with polynomial size increase (part 2)
For functional string-to-string transductions, one of the most popular models is deterministic two-way automata with output. This model admits many different equivalent characterisations (mso transductions, streaming string transducers), and strictly generalises other transducer models such …
Feb. 14, 2018, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Transducers with polynomial size increase
For functional string-to-string transductions, one of the most popular models is deterministic two-way automata with output. This model admits many different equivalent characterisations (mso transductions, streaming string transducers), and strictly generalises other transducer models such …
Feb. 7, 2018, 2:15 p.m.
Tobias Heindel (Universität Leipzig)
Recognizing Languages with Finite Monoidal Categories
A classic result of language theory [Eilenberg, Proposition 12.3] characterizes recognizable word languages as those whose characteristic functions are representative functions [Griffing] -- the latter playing a seminal role in the theory of Hopf algebras …
Jan. 24, 2018, 2:15 p.m.
-
No seminar
Jan. 17, 2018, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Bounded treedepth, bounded expansion, and their interpretations
Classes of bounded expansion are quite general classes of sparse graphs, for which many algorithmic problems which are hard in general become tractable. In particular, the model checking problem for first order logic is fixed …
Jan. 10, 2018, 2:15 p.m.
Lorenzo Clemente (Uniwersytet Warszawski)
Computing the binary reachability relation of Timed Pushdown Automata
The reachability problem asks, for a fixed initial and final configuration, whether there is a run of the system going from the former to the latter. The binary reachability problem generalises the reachability problem: The …
Dec. 20, 2017, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
index) bounds for unambiguous languages
The talk is about the class of regular languages of infinite trees that can be recognised by unambiguous automata. Although the class is very natural, its properties are usually non-trivial with many basic questions unanswered …
Dec. 13, 2017, 2:15 p.m.
Adrien Boiret (Uniwersytet Warszawski)
Equivalence of Deterministic Top-Down Tree Transducers is ExpTime-Complete
The class of Deterministic Top-Down Tree Transducers (DTOP) has been studied for a long time, but while its equivalence problem was known to be ExpTime-Hard, the best known algorithms were coNExpTime (search of counter-example) or …
Dec. 6, 2017, 2:15 p.m.
Juliusz Straszyński (Uniwersytet Warszawski)
PSPACE-complexity of reachability and coverability problems for acyclic Grammar VASes
I will show a reduction of reachablity problem for Grammar VASes to a Subset Sum Game, which is PSPACE-complete.
Nov. 29, 2017, 2:15 p.m.
Petr Novotny (IST Austria)
Checking and Classifying Fast Termination in VASS
Vector Addition Systems with States (VASS) consists of a finite state machine equipped with d positive integer-valued counters, where in each transition every counter is incremented, decremented, or left unchanged. In this talk, I will …
Nov. 22, 2017, 2:15 p.m.
Tomasz Gogacz (Uniwersytet Warszawski)
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
I will present a nice result in Knowledge Representation. It is a proof of decidability of query entailment for a certain extension of modal logic. The procedure consists of two semi-recursive procedures. The first is …