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

April 30, 2014, 2:15 p.m.
-
No seminar this week
April 23, 2014, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Star height via games
I will show a simplified proof of decidability for the star height problem. The simplified proof follows the same lines as the proof of Daniel Kirsten: first the star height problem is reduced to the …
April 16, 2014, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
Kolmogorov's R-sets and regular tree languages
R-sets, introduced in 1928 by Andrey Kolmogorov, were designed as a wide class of well-behaved sets that can be described in a constructible way. One of the crucial properties of this class is universal measurability …
April 9, 2014, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
Determinisation of History Deterministic Automata
A non-deterministic automaton is history deterministic if it is possible to resolve its choices in a way that depends only on the already read input. Such automata appear naturally in synthesis problems and qualitative models.One …
April 2, 2014, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Turing Machine with Atoms and Descriptive Complexity
We relate Turing Machines with Atoms to a certain logic over finite structures. As an application to Descriptive Complexity Theory, within a substantial class of relational structures including Cai-Fürer-Immerman graphs, we precisely characterize those subclasses …
March 26, 2014, 2:15 p.m.
Luc Dartois (LIAFA, Paris)
Adding Modular predicates
When considering classes of regular languages, it is a primordial question to be able to determine if a given language belongs to it. Over fragments of logic, this question has been largely studied since McNaughton-Papert …
March 25, 2014, 2:15 p.m.
Olivier Serre (LIAFA, Paris)
Playing with Automata and Trees
Roughly speaking a finite automaton on infinite trees is a finite memory machine that takes as input an infinite node-labelled binary tree and processes it in a top-down fashion as follows. It starts at the …
March 19, 2014, 2:15 p.m.
Nathanaël Fijalkow (Uniwersytet Warszawski)
The value 1 problem for probabilistic automata
I will talk about probabilistic automata, which are automata assigning to each word a probability to be accepted. Specifically, I will be interested in the value 1 problem, which asks whether for a given probabilistic …
March 12, 2014, 2:15 p.m.
Joanna Ochremiak (Uniwersytet Warszawski)
joint work with Bartek Klin, Sławomir Lasota, Szymon Toruńczyk) - continuatio
We study deterministic computability over sets with atoms. We characterize those alphabets for which Turing machines with atoms determinize. To this end, the determinization problem is expressed as a Constraint Satisfaction Problem, and a characterization …
March 5, 2014, 2:15 p.m.
Joanna Ochremiak (Uniwersytet Warszawski)
joint work with Bartek Klin, Sławomir Lasota, Szymon Toruńczyk
We study deterministic computability over sets with atoms. We characterize those alphabets for which Turing machines with atoms determinize. To this end, the determinization problem is expressed as a Constraint Satisfaction Problem, and a characterization …
Feb. 26, 2014, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Transducers with origin information
Call a string-to-string transducer regular if it can be realised by one of the following equivalent models: mso transductions, two-way deterministic automata with output, and streaming transducers with registers. In the talk, I will propose …
Feb. 19, 2014, 2:15 p.m.
Alessandro Facchini (Uniwersytet Warszawski)
joint work with F. Carreiro, Y. Venema and F. Zanasi
We prove that the bisimulation-invariant fragment of weak monadic second-order logic (WMSO) is equivalent to the fragment of the modal μ-calculus where the application of the least fixpoint operator μp.φ is restricted to formulas φ …
Feb. 5, 2014, 2:15 p.m.
Piotr Hofman (Bayreuth Universität)
joined work with Parosh Aziz Abdulla, Mohamed Faouzi Atig, Richard Mayr, K. Narayan Kumar and Patrick Totzke
Energy games are a well-studied class of2-player turn based games on a finite graphwhere transitions are labelled with integer vectors which representchanges in a multidimensional resource (the energy). One player tries to keep the cumulative …
Jan. 29, 2014, 2:15 p.m.
Denis Kuperberg (Uniwersytet Warszawski)
joint work with Shaull Almagor and Orna Kupferman
The size of deterministic automata required for recognizing regular and omega-regular languages is a well-studied measure for the complexity of languages. We introduce and study a new complexity measure, based on the sensing required for …
Jan. 22, 2014, 2:15 p.m.
Achim Blumensath (Technische Universität Darmstadt)
Recognisability and Algebras of Infinite Trees
In this talk I give an overview of an algebraic language theory for languages of infinite trees based on algebras called omega-hyperclones. Recognisability with respect to these algebras has the same expressive power as tree …