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

April 1, 2015, 2:15 p.m.
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 …
March 25, 2015, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
N, <) is undecidable (The MSO+U theory of)
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. …
March 18, 2015, 2:15 p.m.
Amaldev Manuel (Uniwersytet Warszawski)
joint work with Thomas Colcombet (Mu-calculus on data words)
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 …
March 11, 2015, 2:15 p.m.
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 …
March 4, 2015, 2:15 p.m.
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 …
Feb. 25, 2015, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Wim Martens, Matthias Niewerth and Paweł Parys (Tree Pattern Minimisation)
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 …
Feb. 18, 2015, 2:15 p.m.
Amaldev Manuel (Uniwersytet Warszawski)
joint work with Thomas Colcombet (Combinatorial expressions)
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, …
Feb. 11, 2015, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
joint work with Joanna Ochremiak, Bartek Klin and Eryk Kopczyński (Orbit-finite Constraint Satisfaction Problems)
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 …
Feb. 4, 2015, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
joint work with Lorenzo Clemente (First-order definable pushdown automata)
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 …
Jan. 28, 2015, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
joint work with Wojciech Czerwiński, Wim Martens and Marcin Przybyłko (892 Theorems about Tree Pattern Containment)
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. …
Jan. 21, 2015, 2:15 p.m.
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 …
Jan. 14, 2015, 2:15 p.m.
Matthias Niewerth (Universität Bayreuth)
joint work with Thomas Schwentick (Reasoning about XML Constraints based on XML-to-relational mappings)
I will introduce a framework for XML integrity constraints. AnXML-to-relational constraint consists of a mapping m, that maps trees to relations and a relational integrity constraint. We will have a look onthe complexity of the …
Jan. 7, 2015, 2:15 p.m.
Igor Walukiewicz (CNRS and Bordeaux University)
joint work with Sylvain Salvati (A semantic model for verification of higher-order programs)
We consider simply typed lambda-calculus with fixpoints as anon-interpreted functional programming language: the result of theexecution of a program is its normal form that can be seen as a,potentially infinite, tree of calls to built-in …
Dec. 17, 2014, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
note the change of room (Monads rulez)
The algebraic approach to regular languages is to use monoids instead of automata. The algebraic approach has been extended to other settings, such as infinite words, countable total orders, and various kinds of trees. I …
Dec. 10, 2014, 2:15 p.m.
Adam Witkowski (Uniwersytet Warszawski)
Datalog over trees strikes back
I will present the proof of decidability of containment of monadic, connected, linear Datalog programs over trees with infinite alphabet.