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

29 kwietnia 2015 14:15
Adam Witkowski (Uniwersytet Warszawski)
Solving datalog containment via bounded cliquewidth
Containment of monadic datalog over data trees is known to be undecidable in general but decidablefor two fragments: downward programs and linear child-only ones.I will describe a method for deciding the containment by bounding clique-width …
22 kwietnia 2015 14:15
Joost Winter (Uniwersytet Warszawski)
Coinductive stream calculus
In this talk, I will give an introduction to the coinductive stream calculus (developed by Rutten, McIlroy, and others), its connection to coalgebra, automata theory and implementations in the functional programming language Haskell. We take …
15 kwietnia 2015 14:15
Das Anupam (École Normale Supérieure de Lyon)
A Complete Axiomatization of MSO on Infinite Trees
We show that an adaptation of Peano’s axioms for second-orderarithmetic to the language of MSO completely axiomatizes the theoryover infinite trees. This continues a line of work begun by Büchiand Siefkes with axiomatizations of MSO …
8 kwietnia 2015 14:15
Charles Paperman (Uniwersytet Warszawski)
Regular languages of AC_0
I will present a full proof of the theorem of Barington, Compton, Straubing and Therien characterizing regular languages of AC_0 based on a recent algebraic techniques.
1 kwietnia 2015 14:15
Eryk Kopczyński (Uniwersytet Warszawski)
Spectra and variables
Given a formula \phi of some logic, the spectrum of \phi, denoted spec(\phi), is the set of non-negative integers n such that \phi has a model of cardinality n. The notion of a spectrum has …
25 marca 2015 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
The MSO+U theory of (N, <) is undecidable)
We consider the logic MSO+U, which is monadic second-order logic extended with the unbounding quantifier. The unbounding quantifier is used to say that a property of finite sets holds for sets of arbitrarily large size. …
18 marca 2015 14:15
Amaldev Manuel (Uniwersytet Warszawski)
Mu-calculus on data words (joint work with Thomas Colcombet)
I will describe Data automata, FO^2 and some natural fragments of Data automata defined by classes of Mu-calculus formulas and wrap it up by separating two classes using the circuits we discussed last time. If …
11 marca 2015 14:15
Charles Paperman (Uniwersytet Warszawski)
Circuits complexity and regular languages
I will talk about classical and recent developments on the subject: "Deciding the membership of regular languages in circuits complexity classes". This question is deeply interwoven with the algebraic characterization of classes of regular languages …
4 marca 2015 14:15
Henryk Michalewski (Uniwersytet Warszawski)
From parity games to linear optimization and back
Linear programs (LPs) can be solved efficiently, hence thedesire to reduce the parity games (PGs) to LPs. This seminar will bedevoted to a summary of attempted reductions published over the last 20 years.A polynomial solution …
25 lutego 2015 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Tree Pattern Minimisation (joint work with Wim Martens, Matthias Niewerth and Paweł Parys)
I will consider the problem of minimising tree pattern queries. I will show you the example, which contradicted the long standing conjecture that minimality is the same as nonredundancy. Then I will present how this …
18 lutego 2015 14:15
Amaldev Manuel (Uniwersytet Warszawski)
Combinatorial expressions (joint work with Thomas Colcombet)
Combinatorial expressions are expressions built using two kinds of functions --- those having bounded arity unbounded domain (e.g. addition of integers), and those having bounded domain and unrestricted arity (e.g. Boolean OR of k inputs, …
11 lutego 2015 14:15
Szymon Toruńczyk (Uniwersytet Warszawski)
Orbit-finite Constraint Satisfaction Problems (joint work with Joanna Ochremiak, Bartek Klin and Eryk Kopczyński)
We study extensions of the classical Constraint Satisfaction Problem, to the orbit-finite setting. In one direction, we allow the instances to be orbit-finite, while preserving a finite template. We show that the problem remains decidable …
4 lutego 2015 14:15
Sławomir Lasota (Uniwersytet Warszawski)
First-order definable pushdown automata (joint work with Lorenzo Clemente)
We reinterpret the classical definition of pushdown automata in the setting of first-order definable sets (a subclass of sets with atoms). In view of potential applicability of this model in verification of recursive programs that …
28 stycznia 2015 14:15
Paweł Parys (Uniwersytet Warszawski)
892 Theorems about Tree Pattern Containment (joint work with Wojciech Czerwiński, Wim Martens and Marcin Przybyłko)
We study the following problem of tree pattern containment: given two tree patterns, is it the case that the second pattern can be embedded into every tree into which the first pattern can be embedded. …
21 stycznia 2015 14:15
Wim Martens (Universität Bayreuth)
SCULPT: A Schema Language for Tabular Data on the Web
The World Wide Web Consortium has just started to think about a recommendation for tabular data and metadata on the Web. Inspired by these efforts, we develop a concept for a schema language for tabular …