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

Feb. 4, 2015, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
joint work with Lorenzo Clemente (First-order definable pushdown automata)
We reinterpret the classical definition of pushdown automata in the setting of first-order definable sets (a subclass of sets with atoms). In view of potential applicability of this model in verification of recursive programs that …
Jan. 28, 2015, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
joint work with Wojciech Czerwiński, Wim Martens and Marcin Przybyłko (892 Theorems about Tree Pattern Containment)
We study the following problem of tree pattern containment: given two tree patterns, is it the case that the second pattern can be embedded into every tree into which the first pattern can be embedded. …
Jan. 21, 2015, 2:15 p.m.
Wim Martens (Universität Bayreuth)
SCULPT: A Schema Language for Tabular Data on the Web
The World Wide Web Consortium has just started to think about a recommendation for tabular data and metadata on the Web. Inspired by these efforts, we develop a concept for a schema language for tabular …
Jan. 14, 2015, 2:15 p.m.
Matthias Niewerth (Universität Bayreuth)
joint work with Thomas Schwentick (Reasoning about XML Constraints based on XML-to-relational mappings)
I will introduce a framework for XML integrity constraints. AnXML-to-relational constraint consists of a mapping m, that maps trees to relations and a relational integrity constraint. We will have a look onthe complexity of the …
Jan. 7, 2015, 2:15 p.m.
Igor Walukiewicz (CNRS and Bordeaux University)
joint work with Sylvain Salvati (A semantic model for verification of higher-order programs)
We consider simply typed lambda-calculus with fixpoints as anon-interpreted functional programming language: the result of theexecution of a program is its normal form that can be seen as a,potentially infinite, tree of calls to built-in …
Dec. 17, 2014, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
note the change of room (Monads rulez)
The algebraic approach to regular languages is to use monoids instead of automata. The algebraic approach has been extended to other settings, such as infinite words, countable total orders, and various kinds of trees. I …
Dec. 10, 2014, 2:15 p.m.
Adam Witkowski (Uniwersytet Warszawski)
Datalog over trees strikes back
I will present the proof of decidability of containment of monadic, connected, linear Datalog programs over trees with infinite alphabet.
Dec. 3, 2014, 2:15 p.m.
Marcin Przybyłko (Uniwersytet Warszawski)
Winning a Tree Game
Tree games extend standard turn based games by introducing so-called branching positions. When a player reaches such position, game automatically splits into several independent and concurrently executed sub-games. Unfortunately, this behavior may deprive players of …
Nov. 26, 2014, 2:15 p.m.
Nathanaël Fijalkow (Uniwersytet Warszawski)
Hopefully) the last talk about the value 1 problem for probabilistic automat ()
Since I started my PhD, I already spoke twice at this seminar about the value 1 problem for probabilistic automata. This talk shall be the last on this topic, as it hopefully answers the initial …
Nov. 19, 2014, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
joint work with Claire David and Nadime Francis (Consistency of injective tree patterns)
I will talk about satisfiability problems for tree patterns under different semantics. I will focus on the following problem: decide if a given tree pattern can be matched injectively in some tree from a fixed …
Nov. 12, 2014, 2:15 p.m.
Joost Winter (Uniwersytet Warszawski)
The coalgebraic approach to weighted automata: an introduction
In this talk, I will give an overview of how weighted automata can be seen as coalgebras and bialgebras. The coalgebraic approach to weighted automata was developed by Rutten, Bonsangue, Bartels, Silva, Bonchi, and others, …
Nov. 5, 2014, 2:15 p.m.
Ranko Lazic (University of Warwick)
Multi-dimensional energy games and related problems
I shall present some recent work on multi-dimensional energy games, which happen to have strong connections to several questions involving finite-system simulations, zero-reachability games and alternating termination of vector addition systems.The work is joint with …
Oct. 29, 2014, 2:15 p.m.
Henryk Michalewski (Uniwersytet Warszawski)
joint work with Matteo Mio (Category and Measure in the Monadic Second Order Theory of Trees)
The decidability of the "Satisfiability" problem is a majoropen problem in the area of logics of probabilistic programs such as,e.g., PCTL*.We introduce an extension of "MSO with Null quantifier": MSO+N. Thesystem MSO+N is sufficiently expressive …
Oct. 22, 2014, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
First-Order Logic on CPDA Graphs
It is known that configuration graphs of higher-order pushdown automata (without the collapse operation) coincide with graphs in the Caucal hierarchy. In particular these graphs have decidable MSO theory. The next step is to consider …
Oct. 15, 2014, 2:15 p.m.
Lorenzo Clemente (Uniwersytet Warszawski)
Beyond worst-case analysis for mean-payoff games
Mean-payoff games are classical quantitative games where the objective is to optimise the long-term average payoff.In this purely adversarial setting, one is interested in whether Player 0 has a strategy that guarantees a certain mean-payoff …