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

Oct. 24, 2012, 2:15 p.m.
Martin Zimmermann (Uniwersytet Warszawski)
joint work with Wladimir Fridman and Christof Löding (Degrees of Lookahead in Context-free Infinite Games)
We consider delay games, infinite games in which one player may postpone her moves for some time to obtain a lookahead on her opponent's moves. For regular winning conditions, Hosch and Landweber and later Holtmann, …
Oct. 17, 2012, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
Choice on thin trees and unambiguity
During the talk I will almost provide a decidable characterisation of strongly unambiguous languages - regular languages of infinite trees L such that both L and its complement can be recognised by an unambiguous automaton. …
Oct. 11, 2012, 2:30 p.m.
Andrew Pitts (University of Cambridge)
Notions of Finiteness for Nominal Sets
In the generalised version of nominal sets developed by the group in Warsaw, the property of a structure having only finitely many orbits plays a central role. I will discuss the relationship between "orbit-finiteness" and …
Oct. 10, 2012, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
in nominal sets (P!=NP)
After a brief recap on nominal sets, and following a standard definition of deterministic and nondeterministic Turing machines, I will show a nominal language that is in NP, but is not deterministically recognizable by a …
Oct. 3, 2012, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Automating automata exams
Online education is hot. One weakness is grading students' solutions to problems. So far, automatic systems can do superficial grading of genuine problems (e.g. multiple choice questions about theory, or testing algorithms), or genuine grading …
July 18, 2012, 2:15 p.m.
Marcin Przybyłko (Uniwersytet Warszawski)
Between tree patterns and conjunctive queries: computational complexity of boolean combinations of patterns.
In static analysis of patterns, negation causes drastic increase of complexity. When consider patterns that allow both data comparison and negation, undecidability can be reached with simple queries. Even without data, potential complexity is unacceptably …
June 28, 2012, 2:15 p.m.
Wojciech Kazana (INRIA and ENS Cachan)
joint work with Luc Segoufin (First-order logic over classes of graphs with bounded expansion)
In 2010 it has been shown by Dvorak, Kral and Thomas that the model-checking problem for first-order logic over classes of graphs with bounded expansion can be solved in linear time. In this talk I …
June 20, 2012, 2:15 p.m.
Nathanaël Fijalkow (Uniwersytet Warszawski)
joint work with Martin Zimmermann (Cost-Parity Games)
The starting point of this work is the following observation: although similar in flavor, parity games and finitary parity games are very different from an algorithmic perspective. Both are two-player games on graphs whose vertices …
June 13, 2012, 2:15 p.m.
Szczepan Hummel (Uniwersytet Warszawski)
Unambiguous Tree Languages Are Topologically Harder Than Deterministic Ones
Topological complexity becomes more and more popular set complexity measure in automata theory. One of its remarkable uses is the separation of the classes of languages.I will address the question of the topological complexity of …
June 13, 2012, 1:15 p.m.
Violeta Manevska (St. Clement of Ohrid University of Bitola, Macedonia)
Generalization of the Theory of Finite Semigroup Automata
Observing the automata, we can see that they, during their work, make a transition from one state to another, on which a word from an alphabet corresponds, and in the end they finish in some …
June 6, 2012, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
joint work with Mikołaj Bojańczyk, Bartek Klin, Sławek Lasota (Imperative programming with FM-sets)
I will describe a rather natural programming language for working with orbit-finite Fraenkel-Mostowski sets (aka "nominal" sets).
May 30, 2012, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Vince Barany, Diego Figueira, Paweł Parys (Which data words are simple from an XPath perspective?)
XPath satisfiability is undecidable. However, when doing the undecidability proof, one produces formulas that are only satisfied by very artificial data words. We propose a measure of data words, emulating tree-width for graphs, such that …
May 23, 2012, 2:15 p.m.
Tony Tan (University of Edinburgh)
An Automata Model for Trees with Ordered Data Values
Data trees are trees in which each node, besides carrying a label from a finite alphabet,also carries a data value from an infinite domain.They have been used as an abstraction model for reasoning tasks on …
May 16, 2012, 2:15 p.m.
Artur Jeż (Uniwersytet Wrocławski)
Recompression-based PSPACE algorithm for word equations.
In this talk I will present an application of a simple technique of local recompression, to word equations. The technique is based on iterative replacement of pairs of letters appearing in the equation by a …
May 9, 2012, 2:15 p.m.
Nathanael Fijalkow (joint work with Hugo Gimbert and Youssouf Oualhadj) (Uniwersytet Warszawski)
Deciding the value 1 problem for probabilistic leaktight automata
In this talk, I will present some recent work on the value 1 problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1?This problem …