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

2 lutego 2011 14:15
Henryk Michalewski (Uniwersytet Warszawski)
On the separation property of regular languages (joint result with D. Niwinski).)
We will show that separation property fails for the regular languagesof index (1,3) on infinite trees. More specifically, we willconstruct two disjoint tree languages B_1 and B_2 of index (1,3) notseparable by any set C …
26 stycznia 2011 14:15
Crocodile Dundee (Tasmania)
Holiday
Because of 26.01 which is Australia Day we have holiday. You should use those days to prepare for next week seminar :).
19 stycznia 2011 14:15
Diego Figueira (Uniwersytet Warszawski)
Ackermannian and Primitive-Recursive Bounds with Dickson’s Lemma (joint work with S. Figueira, S. Schmitz and Ph. Schnoebelen)
Dickson’s Lemma is a simple yet powerful tool widely used indecidability proofs, especially when dealing with counters or relateddata structures in algorithmics, verification and model-checking,constraint solving, logic, etc. While Dickson’s Lemma is well-known,most computer scientists …
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 …