Organizatorzy

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

Informacje

środy, 14:15 , sala: 5050

Dziedziny badań

Lista referatów

21 marca 2018 14:15
Marcin Jurdziński (University of Warwick)
A pseudo-quasi-polynomial algorithm for solving mean-payoff parity games
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 …
14 marca 2018 14:15
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 …
7 marca 2018 14:15
-
No seminar
28 lutego 2018 14:15
Pierre Pradic (ENS de Lyon)
A Curry-Howard Approach to Church's Synthesis via Linear Logic
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 ω. …
21 lutego 2018 14:15
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 …
14 lutego 2018 14:15
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 …
7 lutego 2018 14:15
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 …
24 stycznia 2018 14:15
-
No seminar
17 stycznia 2018 14:15
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 …
10 stycznia 2018 14:15
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 …
20 grudnia 2017 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
No
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 …
13 grudnia 2017 14:15
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 …
6 grudnia 2017 14:15
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.
29 listopada 2017 14:15
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 …
22 listopada 2017 14:15
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 …