Organizatorzy

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Informacje

środy, 14:15 , sala: 5050

Dziedziny badań

Lista referatów

10 listopada 2010 14:15
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 …
3 listopada 2010 14:15
Thomas Place (Uniwersytet Warszawski)
Expressive power of $FO_2
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 …
27 października 2010 14:15
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 …
20 października 2010 14:15
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 …
13 października 2010 14:15
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 …
6 października 2010 14:15
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 …
30 września 2010 14:15
- (Uniwersytet Warszawski)
holiday
2 czerwca 2010 14:15
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 …
26 maja 2010 14:15
Tibor Szabo (Freie Univeritaet Berlin)
Probabilistic intuition in positional games
19 maja 2010 14:15
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 …
12 maja 2010 14:15
Mr. Nobody (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
5 maja 2010 14:15
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.
28 kwietnia 2010 14:15
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 …
21 kwietnia 2010 14:15
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 …
14 kwietnia 2010 14:15
Arnaud Carayol (Institut Gaspard-Monge)
Linear orderings in the pushdown hierarchy.