Organizers

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

Information

Wednesdays, 2:15 p.m. , room: 5440

Research fields

List of talks

Jan. 12, 2011, 2:15 p.m.
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 …
Jan. 5, 2011, 2:15 p.m.
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 …
Dec. 8, 2010, 2:15 p.m.
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 …
Dec. 1, 2010, 2:15 p.m.
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 …
Nov. 24, 2010, 2:15 p.m.
- (Uniwersytet Warszawski)
No seminar.
Nov. 17, 2010, 2:15 p.m.
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 …
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 (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 …
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