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

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 (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 …
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 …
15 listopada 2017 14:15
Ranko Lazic (University of Warwick)
Succinct progress measures for solving parity games
The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm …
8 listopada 2017 14:15
Radosław Piórkowski (Uniwersytet Warszawski)
WQO dichotomy conjecture — proof of a special case, part 2
The conjecture claims that there exists a simple criterion for decidability for Petri nets with homogeneous data. We prove a special case of this conjecture for data being 2-edge-coloured graphs. I will outline the overall …
25 października 2017 14:15
Radosław Piórkowski (Uniwersytet Warszawski)
WQO dichotomy conjecture — proof of a special case
Decidability of many standard decision problems for Petri nets becomes an open problem once we extend the model with data. If we restrict only to homogeneous data domains, according to the WQO Dichotomy Conjecture there …
18 października 2017 14:15
Nathanael Fijalkow (University College London)
Timed comparisons of semi-Markov processes
A semi-Markov process is like a Markov process, but each transition takes some time to get fired, and this time is determined by a probabilistic distribution over the non-negative reals. In this talk I will …
11 października 2017 14:15
Bartek Klin (Uniwersytet Warszawski)
mu-calculus with atoms
True to the spirit of "\lambda x. (x with atoms)", I will present a modal mu-calculus with atoms. I will also explain what is wrong with it, and how it could perhaps be improved. This …
4 października 2017 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
First-order list functions (joint work with Laure Daviaud and Krishna S)
We define a class of functions, called first-order list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pairs of lists, etc. The definition is in the style of …