Organizers

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

Information

Wednesdays, 2:15 p.m. , room: 5050

Research fields

List of talks

Feb. 27, 2019, 2:15 p.m.
Bartosz Klin (joint work with Clovis Eberhart) (Uniwersytet Warszawski)
with atoms
Motto: Those who cannot remember the past are free to reinvent it. Abstract: Mu-calculus with atoms extends the classical mu-calculus with orbit-finitary boolean operators, to describe properties of transition systems with atoms. Its expressivity …
Feb. 20, 2019, 2:15 p.m.
Rafał Stefański (joint work with Mikołaj Bojańczyk) (Uniwersytet Warszawski)
Single use register automata for data words
We introduce a new automaton model for data words, called single use register automata. These are like register automata for data words (introduced by Kaminski and Francez), with the restriction that every read access to …
Feb. 13, 2019, 2:15 p.m.
Amina Doumane (Uniwersytet Warszawski)
Completeness for Identity-free Kleene Lattices
We provide a finite set of axioms for identity-free Kleene lattices, which we prove sound and complete for the equational theory of their relational models. Our proof builds on the complete- ness theorem for Kleene …
Jan. 30, 2019, 2:15 p.m.
Sebastian Rudolph (TU Dresden)
On the Verge of Decidability: Querying Description Logics with Counting, Inverses and Nominals
Description Logics (DLs) are Knowledge Representation formalisms with a great significance for Semantic Web technologies. In this context, the most central reasoning task considered today is query answering over Description Logic knowledge bases under the …
Jan. 23, 2019, 2:15 p.m.
Jędrzej Kołodziejski (Uniwersytet Warszawski)
Bisimulational Categoricity
The notion of bisimulation – which can be thought of as behavioral equivalence – is ubiquitous and in many contexts it appears more appropriate than isomorphism. Therefore, it is natural to introduce a notion of …
Jan. 16, 2019, 2:15 p.m.
Ian Pratt-Hartmann (School of Computer Science University of Manchester)
Transitivity and Equivalence in Two-Variable First-Order Logic
The notions of transitive relation and equivalence relation number among the most salient concepts in logic. On the other hand, it is well-known that these properties are not expressible in various well-known fragments of first-order …
Jan. 9, 2019, 2:15 p.m.
Julian Salamanca Tellez (Uniwersytet Warszawski)
Determinization, an algebraic approach
The algebraic approach to recognizability has been proposed since the 1960s and an instance of non-determinism can be formulated by means of direct images of homomorphisms. In this talk, I will present the general problem …
Dec. 19, 2018, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Polyregular functions
I will describe a class of string-to-string transducers, which goes beyond rational or regular functions, but still shares many of their good properties (e.g. the inverse image of a regular language is regular). Unlike many …
Dec. 12, 2018, 2:15 p.m.
Piotr Hofman (Uniwersytet Warszawski)
Joint work with Utkarsh Gupta, Preey Shah, S. Akshay
What is the best way to reduce complexity? The simple answer is "change the problem". Considering the hardness of Petri net reachability people developed a different notion, namely continuous reachability. During the talk, I will …
Dec. 5, 2018, 2:15 p.m.
Alexandre Vigny (Uniwersytet Warszawski)
Query enumeration and nowhere dense classes of graphs
Given a query q and a relational structure D the enumeration of q over D consists in computing, one element at a time, the set q(D) of all solutions to q on D. The delay …
Nov. 28, 2018, 2:15 p.m.
Ian Pratt-Hartmann (University of Manchester)
The Return of the Syllogism
The Aristotelian syllogistic is known to do a good job of accounting for the validity of inferences couched in a certain common fragment of many natural languages. To take an example from English: Every man …
Nov. 14, 2018, 2:15 p.m.
Laurent Doyen (CNRS & LSV, ENS Paris-Saclay)
Graph Planning with Expected Finite Horizon
A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon …
Nov. 7, 2018, 2:15 p.m.
Bartosz Klin (Uniwersytet Warszawski)
joint work with Julian Salamanca
Monads are mathematical objects that can be understood as "well-structured ways to collect things". Examples include the monad of finite words, the powerset monad P, the multiset monad, etc. In the talk I will explain …
Oct. 31, 2018, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
The Reachability Problem for Vector Addition Systems is Not Elementary
I will present a recent result about tower lower bound for reachability problem in VASes. I plan to first illustrate a few phenomena occuring in VASes by examples. Then I will show a full proof …
Oct. 24, 2018, 2:15 p.m.
Nathan Lhote (Uniwersytet Warszawski)
Logics for Transductions
Logics over words such as Monadic Second-Order Logic, or Linear Temporal Logic provide a way to specify properties of systems in a high-level formalism, close to natural language. From such formulas one would like to …