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 3, 2013, 2:15 p.m.
Andrea Calì (University of London, Birkbeck College & University of Oxford)
Decidable logics for the Semantic Web
The notion of Semantic Web involves the publication of data in machine-readable format. Such data are intended to be enriched with so-called ontologies, which express information about the domain of the data, in particular about …
March 27, 2013, 2:15 p.m.
Filip Mazowiecki (Uniwersytet Warszawski)
joint work with Witold Charatonik and Emanuel Kieroński (Complexity of two-variable logic over finite trees)
We consider the satisfiability problem for the two-variable fragment of first-order logic over finite unranked trees. We work with signatures consisting of some unary predicates and the binary navigational predicates child, right sibling, and their …
March 20, 2013, 2:15 p.m.
Nathanaël Fijalkow (Uniwersytet Warszawski)
joint work with Sophie Pinchinat and Olivier Serre (Emptiness of alternating tree automata through games of imperfect information)
In this talk, I will consider the emptiness problem for alternating tree automata with two different acceptance semantics: classical (all branches are accepted) and qualitative (almost all branches are accepted). I will show a new …
March 13, 2013, 2:15 p.m.
Petr Jančar (Technical University of Ostrava)
joint work with Stanislav Böhm and Stefan Göller (Equivalence of Deterministic One-Counter Automata is NL-complete)
We prove that language equivalence of deterministic one-counter automata is NL-complete. This improves the superpolynomial time complexity upper bound shown by Valiant and Paterson in 1975. Our main contribution is to prove that two deterministic …
March 6, 2013, 2:15 p.m.
Wojciech Czerwiński (University of Bayreuth)
joint work with Wim Martens and Tomas Masopust (Separability of Regular Languages by Piecewise Testable Languages)
The separation problem is formulated as follows: given two regular languages K and L, does there exists a "simple" regular language S separating them, i.e. including all words from K and no words from L? …
Feb. 27, 2013, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
Trees in trees: is the incomplete information about a tree consistent?
We are interested in the following problem: given a tree automaton $\Aut$ and an incomplete tree description $P$, does a tree $T$ exist such that $T$ is accepted by $\Aut$ and consistent with $P$? A …
Feb. 20, 2013, 2:15 p.m.
Piotr Hofman and Filip Murlak (Uniwersytet Warszawski)
joint work with Claire David and Michał Pilipczuk (Synthesizing transformations from XML schema mappings)
XML schema mappings have been developed and studied in the context of XML data exchange, where a source document has to be restructured under the target schema according to certain rules. The rules are specified …
Jan. 23, 2013, 2:15 p.m.
Leszek Kołodziejczyk (Uniwersytet Warszawski)
A collapse result for constant depth propositional proof systems with modular counting connectives - continuation
In the second part of my talk, I would like to discuss in more detail some issues that were mentioned only briefly in the first part. In particular, I would like to say some more …
Jan. 16, 2013, 2:15 p.m.
Leszek Kołodziejczyk (Uniwersytet Warszawski)
A collapse result for constant depth propositional proof systems with modular counting connectives
A major open problem in propositional proof complexity is to obtain strong (ideally, exponential) lower bounds for the size of proofs of tautologies in constant depth proof systems with the usual boolean connectives and a …
Jan. 9, 2013, 2:15 p.m.
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 …
Dec. 19, 2012, 2:15 p.m.
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 …
Dec. 5, 2012, 2:15 p.m.
Alessandro Facchini (Uniwersytet Warszawski)
joint work with Yde Venema and Fabio Zanasi (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 …
Nov. 14, 2012, 2:15 p.m.
Tomasz Gogacz (Uniwersytet Wrocławski)
joint work with Jerzy Marcinkowski (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 …
Nov. 7, 2012, 2:15 p.m.
Charles Paperman (LIAFA, University Paris-Diderot)
joint work with Luc Dartois (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 …
Oct. 31, 2012, 2:15 p.m.
Piotr Hofman (Uniwersytet Warszawski)
joint work with Patrick Totzke and Richard Mayr (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 …