Organizatorzy

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

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

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.
31 marca 2010 14:15
Mr. Nobody. (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
24 marca 2010 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
On topological complexity of MSO+U over infinite words
In [1] Bojańczyk considered WMSO+U logic and a new type of automata: max-automata. His main result is a conclusion that this logic is decidable over Ω. There arise the natural questions about expressive power of …
17 marca 2010 14:15
Clemens Ley (Oxford)
Towards effective characterizations of data languages.
We study the following decision problem. Given a deterministicregister automaton and a logic, decide if the language recognized bythe register automaton can be defined in the logic. This studyrequires new insights into deterministic register automata, …