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

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 (Turing Machines with Atoms and Constraint Satisfaction Problems)
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 (Turing Machines with Atoms and Constraint Satisfaction Problems)
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 (Weak MSO: Automata and Expressiveness Modulo Bisimilarity)
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 (Infinite-State Energy Games)
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 (Regular Sensing)
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 …
Jan. 15, 2014, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Weak MSO+U with path quantifiers
Over infinite trees, satisfiability is decidable for weak monadic second-order logic extended by the unbounding quantifier U and quantification over infinite paths. The proof is by reduction to emptiness for a certain automaton model, while …
Jan. 8, 2014, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
Infinite sets in practice
We present a C++ library allowing computation over infinite sets. The programmer is able to represent infinite sets (in finite memory), as well as loop over them (in finite time). The elements of these sets …
Dec. 18, 2013, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
joint work with Achim Blumensath, Thomas Colcombet, Denis Kuperberg and Michael Vanden Boom (Two-Way Cost Automata and Cost Logics over Infinite Trees)
This work is a step towards solving regular cost functions on infinite trees (which is already done for words - finite and infinite - and for finite words).We consider cost functions over infinite trees defined …
Dec. 11, 2013, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
joint work with Tomasz Gogacz, Henryk Michalewski and Matteo Mio (Harrington's game and measurability of regular tree languages)
I will present some investigations on measure properties of regular tree languages. The motivation for this research comes from the dissertation of Matteo Mio. I plan to focus on two aims: the first aim is …
Dec. 4, 2013, 2:15 p.m.
Denis Kuperberg (Uniwersytet Warszawski)
joint work with Udi Boker, Orna Kupferman, Michał Skrzypczak (Nondeterminism in the Presence of a Diverse or Unknown Future)
One of the advantages of deterministic automata is that they composewell with trees and games. In the theory of cost functions, suchdeterministic automata are not always available, so a weaker notionwas introduced: history-deterministic automata, which …
Nov. 27, 2013, 2:15 p.m.
Adam Witkowski (Uniwersytet Warszawski)
Regular Tree Pattern Queries and Datalog
Regular Tree Pattern Queries (RTPQ) are queries for data trees that were defined during a research on Active XML.We found that this formalism is interesting on its own and closely connected to Datalog.I will talk …