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

Nov. 10, 2010, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Languages of infinite and profinite words
I will present connections between three classes of objects:1) languages of infinite words, such as B- and S-regular languages defined by Mikolaj Bojańczyk and Thomas Colcombet 2) regular cost functions, defined by Thomas Colcombet3) languages …
Nov. 3, 2010, 2:15 p.m.
Thomas Place (Uniwersytet Warszawski)
<_h,<_v)$ on finite tree
I will present results about the expressive power of$FO_2(<_h,<_v)$ on finite trees. In particular I will present acharacterization of this logic on finite trees. $FO_2(<_h,<_v)$is the two variable fragment of first order logic built from …
Oct. 27, 2010, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
Solutions in XML Data Exchange
The task of XML data exchange is to restructure a document conforming to a source schema under a target schema according to certain mapping rules. The rules are typically expressed as source-to-target dependencies using various …
Oct. 20, 2010, 2:15 p.m.
Laurent Braud (Institut Gaspard Monge in Marne-la-Vallée)
Morphic words and recursion schemes
We will look at infinite words which are the leaves in lexicographic order of a deterministic tree (in the case where the order type of this object is omega). When the tree can be generated …
Oct. 13, 2010, 2:15 p.m.
Diego Figueira (Laboratoire Spécification et Vérification)
Satisfiability of downward XPath
XPath is a logic for finite data trees, and the downward fragment restricts the syntax by allowing only descending paths. I will show that downward XPath has a decidable satisfiability problem. For this, I will …
Oct. 6, 2010, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Opening Session
Dear colleagues, On Wednesday, 6 October, we start the new academic year at the Automata Theory Seminar. The room is 5870. We have are happy to have a new group of international visitors, and also …
Sept. 30, 2010, 2:15 p.m.
- (Uniwersytet Warszawski)
holiday
June 2, 2010, 2:15 p.m.
Piotrek Hofman (Uniwersytet Warszawski)
time becomes data on the other side of the mirror
Timed automata and register automata are well-known models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes …
May 26, 2010, 2:15 p.m.
Tibor Szabo (Freie Univeritaet Berlin)
Probabilistic intuition in positional games
May 19, 2010, 2:15 p.m.
Marek Grabowski (Uniwersytet Warszawski)
On simulation and trace inclusion
Simulation preorder and trace inclusion between transition systems asexamples of branching andlinear time problems. The talk will be devoted to the case when thetwo systems are given as a kindof product of finite-state ones. The …
May 12, 2010, 2:15 p.m.
Mr. Nobody (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
May 5, 2010, 2:15 p.m.
Tomasz Kazana (Uniwersytet Warszawski)
connection between cryptography and a pebble game
I will define a specific game in which a player puts pebbles on a board. Then I will show some properties of this game and connections with cryptrography.
April 28, 2010, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Data monoids
A data monoid is like a monoid, but it is used to recognize languagesof data words, and not languages of words over finite alphabets. Iwill say what kind of languages of data words can be …
April 21, 2010, 2:15 p.m.
Vince Barany (Rheinisch-Westfälische Technische Hochschule Aachen)
Querying the Guarded Fragment
Evaluating a boolean conjunctive query q over a guarded first-ordertheory T is equivalent to checking whether (T & not q) is unsatisfiable.This problem is relevant to the areas of database theory anddescription logic. Since q …
April 14, 2010, 2:15 p.m.
Arnaud Carayol (Institut Gaspard-Monge)
Linear orderings in the pushdown hierarchy.