Organizatorzy

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

Informacje

środy, 14:15 , sala: 5050

Dziedziny badań

Lista referatów

9 stycznia 2013 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Compactness in sets with atoms
This is another talk about sets with atoms (also known as Fraenkel-Mostowski sets, or nominal sets). Specifically, the topic is the notion of models for formulas of first-order logic. The problem is that a natural …
19 grudnia 2012 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
Uniformization and selection for FO and MSO
Uniformization problem asks whether for a given formula phi(X,Y) there exists a formula psi(X,Y) that for every X selects exactly one Y satisfying phi(X,Y). Quite natural arguments show that MSO logic has uniformization property in …
5 grudnia 2012 14:15
Alessandro Facchini (Uniwersytet Warszawski)
Modal correspondence and fixpoints
Modal correspondence theory is the comparative study of expressiveness of modal languages and classical languages, like first order logic (FO) and monadic second order logic (MSO). The two main results in this context are van …
14 listopada 2012 14:15
Tomasz Gogacz (Uniwersytet Wrocławski)
On BDD/FC Conjecture
Bounded Derivation Depth property (BDD) and Finite Controllability (FC) are two properties of sets of tuple generating dependencies, which recently attracted some attention. We conjecture that the first of these properties implies the second, and …
7 listopada 2012 14:15
Charles Paperman (LIAFA, University Paris-Diderot)
Two-variable first order logic with modular predicates is decidable over words
We consider first order formulae over the signature consisting of the symbols of the alphabet, the symbol $<$ (interpreted as a linear order) and the set $\MOD$ of modular numerical predicates. We study the expressive …
31 października 2012 14:15
Piotr Hofman (Uniwersytet Warszawski)
Weak simulation problem for one counter nets
One counter net is actually a one counter automaton without a possibility of testing the value 0. For example it can recognize a language a^n b^m for m less or equal n. Weak simulation is …
24 października 2012 14:15
Martin Zimmermann (Uniwersytet Warszawski)
Degrees of Lookahead in Context-free Infinite Games
We consider delay games, infinite games in which one player may postpone her moves for some time to obtain a lookahead on her opponent's moves. For regular winning conditions, Hosch and Landweber and later Holtmann, …
17 października 2012 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
Choice on thin trees and unambiguity
During the talk I will almost provide a decidable characterisation of strongly unambiguous languages - regular languages of infinite trees L such that both L and its complement can be recognised by an unambiguous automaton. …
11 października 2012 14:30
Andrew Pitts (University of Cambridge)
Notions of Finiteness for Nominal Sets
In the generalised version of nominal sets developed by the group in Warsaw, the property of a structure having only finitely many orbits plays a central role. I will discuss the relationship between "orbit-finiteness" and …
10 października 2012 14:15
Bartek Klin (Uniwersytet Warszawski)
P!=NP
After a brief recap on nominal sets, and following a standard definition of deterministic and nondeterministic Turing machines, I will show a nominal language that is in NP, but is not deterministically recognizable by a …
3 października 2012 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Automating automata exams
Online education is hot. One weakness is grading students' solutions to problems. So far, automatic systems can do superficial grading of genuine problems (e.g. multiple choice questions about theory, or testing algorithms), or genuine grading …
18 lipca 2012 14:15
Marcin Przybyłko (Uniwersytet Warszawski)
Between tree patterns and conjunctive queries: computational complexity of boolean combinations of patterns.
In static analysis of patterns, negation causes drastic increase of complexity. When consider patterns that allow both data comparison and negation, undecidability can be reached with simple queries. Even without data, potential complexity is unacceptably …
28 czerwca 2012 14:15
Wojciech Kazana (INRIA and ENS Cachan)
First-order logic over classes of graphs with bounded expansion
In 2010 it has been shown by Dvorak, Kral and Thomas that the model-checking problem for first-order logic over classes of graphs with bounded expansion can be solved in linear time. In this talk I …
20 czerwca 2012 14:15
Nathanaël Fijalkow (Uniwersytet Warszawski)
Cost-Parity Games
The starting point of this work is the following observation: although similar in flavor, parity games and finitary parity games are very different from an algorithmic perspective. Both are two-player games on graphs whose vertices …
13 czerwca 2012 14:15
Szczepan Hummel (Uniwersytet Warszawski)
Unambiguous Tree Languages Are Topologically Harder Than Deterministic Ones
Topological complexity becomes more and more popular set complexity measure in automata theory. One of its remarkable uses is the separation of the classes of languages.I will address the question of the topological complexity of …