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

12 stycznia 2011 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Fast equivalence checking for normed context-free processes. Joint work with Sławomir Lasota.
We consider graphs generated by context free grammars and ask the question if given two states in such an infinite graph are equivalent. I will talk about the new algorithm which answers this question using …
5 stycznia 2011 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Ramsey Theorems for Compact Colors. Joint work with Eryk Kopczyński and Szymon Toruńczyk
When applied to omega-words, the Ramsey Theorem says the following. Suppose that finite factors (=infixes) of an omega-word are colored by a finite number of colors. Then one factorize a suffix of the omega-word so …
8 grudnia 2010 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Efficient evaluation for temporal logic on changing XML documents joint work with Diego Figueira
We consider a sequence $t_1,\ldots,t_k$ of XML documents that isproduced by a sequence of local edit operations. To describeproperties of such a sequence, we use a temporal logic. The logic cannavigate both in time and …
1 grudnia 2010 14:15
Sławomir Lasota (Uniwersytet Warszawski)
Minimisation of automata over data words
(a joint work with Mikołaj Bojańczyk and Bartek Klin) I will state and prove an analog of the Myhill-Nerode theorem for register automata. The difficulty comes from the fact that the input alphabet contains data …
24 listopada 2010 14:15
- (Uniwersytet Warszawski)
No seminar.
17 listopada 2010 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
Equational theories of profinite structures
I will present a simple way of defining profinite structures in a very general framework. The applications include such objects as words, trees and generic finite structures. The procedure gives interesting results in the context …
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 (<_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 …
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