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

March 16, 2011, 2:15 p.m.
Marcin Bilkowski (Uniwersytet Warszawski)
Complements of unambiguous languages.
An automaton is unambiguous if it has at most one accepting run for every input.A language is unambiguous if there exists an unambiguous automaton recognizingthat language. It is known that not all regular languages of …
March 9, 2011, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
Automata with group actions
Our motivating question is a Myhill-Nerode theorem for infinitealphabets. We consider several kinds of those: alphabets whose letterscan be compared only for equality, but also ones with more structure,such as a total order or a …
March 2, 2011, 2:15 p.m.
Vince Barany (Uniwersytet Warszawski)
joint work with Balder ten Cate and Luc Segoufin (Guarded negation)
We consider restrictions of first-order logic and least fixpoint logic in which all occurrences of negation are required to be guarded by an atomic predicate. The so obtained guarded negation fragments GNFO and GNFP naturally …
Feb. 23, 2011, 2:15 p.m.
Alessandro Facchini (Uniwersytet Warszawski)
joint work with Balder ten Cate (Characterizations of EF over Infinite Trees)
We provide several equivalent effective characterizations of EF (the modallogic of the descendant relation) on arbitrary trees. Morespecifically, we prove that, for EF-bisimulation invariantproperties of trees, being definable by an EF formula, being aBorel set, …
Feb. 2, 2011, 2:15 p.m.
Henryk Michalewski (Uniwersytet Warszawski)
joint result with D. Niwinski). (On the separation property of regular languages)
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 …
Jan. 26, 2011, 2:15 p.m.
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 :).
Jan. 19, 2011, 2:15 p.m.
Diego Figueira (Uniwersytet Warszawski)
joint work with S. Figueira, S. Schmitz and Ph. Schnoebelen (Ackermannian and Primitive-Recursive Bounds with Dickson’s Lemma)
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 …
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 …