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 27, 2016, 2:15 p.m.
Damien Pous (ENS Lyon)
Kleene algebra, from automata algorithms to proof assistants
Kleene algebra are the algebraic counterpart to finite automata on finite words. First I will describe two recent algorithms for finite automata: one exploiting bisimulations up to congruence to tame non-determinism, and one exploiting binary …
April 20, 2016, 2:15 p.m.
Marcin Przybyłko (Uniwersytet Warszawski, University of New Caledonia)
joint work with Michał Skrzypczak (Branching games with regular winning sets)
A branching game is a game that produces trees instead of paths. This is achieved by introducing new type of positions -- branching positions -- that split the game into two independent sub-games. M.Mio defined …
April 13, 2016, 2:15 p.m.
Adam Witkowski (Uniwersytet Warszawski)
joint work with Wim Martens (SCULPT: describing the tabular data)
SCULPT is a schema language for tabular data (like CSV files) proposed by Wim Martens, Frank Neven and Stan Vansummeren. I will talk about a variant of satisfiability problem which is tractable for a robust …
April 6, 2016, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Wim Martens, Lorijn van Rooijen, Marc Zeitoun and Georg Zetzsche (Separability of context-free languages by piecewise testable languages)
I will show that separability of context-free languages by piecewise testable languages is decidable (which is surprising as deciding whether a context-free language is piecewise testable is undecidable). Then I will generalize this result and …
March 30, 2016, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
A gap property for Buchi languages of infinite trees
In this talk I will speak about classes of languages of infinite treesdefinable in monadic second-order (MSO) logic. My main interest willbe in two such classes: languages that are definable in the weakvariant of MSO …
March 23, 2016, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
joint work with L. Clemente, S. Salvati, I. Walukiewicz (The Diagonal Problem for Higher-Order Recursion Schemes is Decidable)
A non-deterministic recursion scheme recognizes a language of finite trees. This very expressive model can simulate, among others, higher-order pushdown automata with collapse. We show the decidability of the diagonal problem for schemes: given a …
March 16, 2016, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Michał Pilipczuk (On the Courcelle Conjecture)
We prove a conjecture of Courcelle, which states that a graph property is definable in mso with modular counting predicates on graphs of constant treewidth if, and only if it is recognizable in the following …
March 9, 2016, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
Expressivity of probabilistic modal logic, the easy way
Probabilistic modal logic is a very basic modal logic (propositional logic plus a diamond-like modality) interpreted on probabilistic transition systems. It is expressive, i.e., its logical equivalence coincides with bisimilarity, and the proof of this …
March 2, 2016, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
joint work with B.Klin, S. Lasota, J. Ochremiak (Homomorphism problems for first-order definable structures)
We prove decidability of the existence of a homomorphism between two given infinite structures with finite signatures which are definable, or interpret, in the natural numbers with equality. The result uses Pestov's theorem from topological …
Jan. 27, 2016, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
joint work with S. Lasota, J. Ochremiak and S. Toruńczyk (Homomorphism problems for first-order definable structures)
Consider infinite relational structures where both the universe and the relations are definable by first-order formulas over natural numbers with equality. An example of such a structure is the countable clique graph, or a graph …
Jan. 20, 2016, 2:15 p.m.
Amal Dev Manuel (Uniwersytet Warszawski)
joint work with Thomas Colcombet, Denis Kuperberg, and Szymon Toruńczyk (Expressiveness of Min/Max Automata)
In this work we show how to decide if a given regular cost function isrecognised by a Min (Max) automaton. This is achieved bycharacterising the classes of cost functions of the these automataalgebraically. Also a …
Jan. 13, 2016, 2:15 p.m.
Marcin Wrochna (Uniwersytet Warszawski)
On space efficiency of algorithms working on structural decompositions of graphs
Motivated by failed attempts at making dynamic algorithms on tree-width use less space (without using more time), we look at this from a complexity-theoretic point of view. I will mention relations to Savitch's theorem and …
Dec. 16, 2015, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
Invisible pushdown languages
Context free languages allow one to express data with hierarchical structure, at the cost of losing some of the useful properties of languages recognized by finite automata on words. However, it is possible to restore …
Dec. 9, 2015, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
Timed pushdown automata, equations over sets of integers, and branching vector addition systems with states in dimension 1
Mutual reductions between the three models will be discussed. Decidability of emptiness is an intriguing open problem.
Dec. 2, 2015, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
A probabilistic logic for infinite trees
Consider the following quantifier for infinite trees: “the set of paths π which make φ(π) true has zero probability”.We consider weak MSO over infinite trees extended with this quantifier. I would like to report on …