Nie jesteś zalogowany |
Cotygodniowe seminarium badawcze
Organizatorzy
- prof. dr hab. Mikołaj Bojańczyk
- prof. dr hab. Damian Niwiński
Informacje
środy, 14:15 , sala: 5440Dziedziny badań
Lista referatów
-
-
-
-
11 maja 2011 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Nominal Computation
I will present a programming language that manipulates nominal sets.In the programming language, an orbit finite set behaves like a finiteset. One can execute in finite time a loop over all elements of anorbit finite …
-
-
27 kwietnia 2011 14:15
Martin Zimmermann (RWTH Aachen)
Solving Muller Games via Safety Games
Using results on finite-time Muller Games (which are defined using scoring functions that measure how often a given loop in the arena has been visited) we showhow to determine the winner and a finite-state winning …
-
20 kwietnia 2011 14:15
Laurent Braud (Uniwersytet Warszawski)
Limits of interpretations and unfoldings
The original motivation was the characterisation of more structureswith decidable MSO theory. We consider the transformation approach :operations that preserve decidability include MSO-interpretations andunfoldings, which can be used to build the Caucal hierarchy. In anattempt …
-
13 kwietnia 2011 14:15
Paweł Parys (Uniwersytet Warszawski)
The excluded grid theorem
I will present a proof of the excluded grid theorem of Robertson and Seymour: a graph has no large grid minor if and only if it has small tree-width.
-
6 kwietnia 2011 14:15
Michał Pilipczuk (Uniwersytet Warszawski)
Solving problems parameterized by tree-width in single exponential time: a logical approach
We introduce a variant of modal logic on graphs, dubbed EXISTENTIAL COUNTINGMODAL LOGIC (ECML), which captures a vast majority of problems knownto be tractable in single exponential time when parameterized by treewidth. Itappears that all …
-
30 marca 2011 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Towards decidability of weak bisimilarity on BPP
Consider transition system generated by commutative context-free grammar,so called BPP. Strong bisimilarity is known to be PSPACE-complete on this classof infinite graphs, weak bisimilarity (with possible epsilon transitions) is important and longstanding open problem.I will …
-
23 marca 2011 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
No satisfiability measure for first-order logic on graphs
Consider MSO on graphs, with quantification over sets of edges andsets of nodes.Tree-width is a good measure of graphs for this logic because: a) for every k,satisfiability is decidable over graphs of tree-width at most …
-
16 marca 2011 14:15
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 …
-
9 marca 2011 14:15
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 …
-
2 marca 2011 14:15
Vince Barany (Uniwersytet Warszawski)
Guarded negation (joint work with Balder ten Cate and Luc Segoufin)
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 …
-
23 lutego 2011 14:15
Alessandro Facchini (Uniwersytet Warszawski)
Characterizations of EF over Infinite Trees (joint work with Balder ten Cate)
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, …
