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

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
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
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 …
April 25, 2012, 2:15 p.m.
Igor Walukiewicz (LaBRI, Bordeaux)
Verification on higher-order recursive schemes
We propose a new approach to analysing higher-order recursive schemes. Higher-order recursive schemes were introduced by Damm in the 80-ties as a respelling of simply-typed lambda calculus with fixpoints (lambda-Y). In this century the interest …
April 18, 2012, 2:15 p.m.
Anca Muscholl (LaBRI, Bordeaux)
joint work with B. Genest, H. Gimbert and I. Walukiewicz
The control problem starts with a plant and asks to restrict its controllable actions in such a way that a given specification is met. The synthesis problem can be seen as a special case of …
April 4, 2012, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Collapsible Pushdown Systems
I will briefly describe two results (the second one is a joint work with A. Kartzow). One is that collapsible pushdown systems are more expressible that higher-order pushdown systems without collapse, for any level. This …
March 28, 2012, 2:15 p.m.
Piotr Hofman (Uniwersytet Warszawski)
joint work with Patrick Totzke
I will briefly present Basic Parallel Processes and the problem of weak bisimulation. Next I will introduce idea of the approximants technique and show a few known facts about them. Then I will present counterexample …
March 21, 2012, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
joint work with Anuj Dawar, Erich Graedel, Bjarki Holm, Wied Pakusa) - continuatio
The quest for a logic for PTIME is one of the central open problems in both finite model theory and database theory. Specifically, it asks whether there is a logic in which a class of …
March 14, 2012, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
joint work with Anuj Dawar, Erich Graedel, Bjarki Holm, Wied Pakusa
The quest for a logic for PTIME is one of the central open problems in both finite model theory and database theory. Specifically, it asks whether there is a logic in which a class of …
March 7, 2012, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
joint work with Mikołaj Bojańczyk
We introduce a variant of nominal sets that is well-suited for languages recognized by timed automata. We state and prove a machine-independent characterization of languages recognized by deterministic timed automata. Finally, in the setting of …
Feb. 29, 2012, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
Descriptive properties of regular languages of thin trees
Feb. 22, 2012, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Thomas Place
Using nominal sets, we define a uniform approach to logics over data words, data trees, data graphs and so on. The key technical result is that, in the equality symmetry, formulas that quantify over data …