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

May 8, 2019, 2:15 p.m.
Nathan Lhote (Uniwersytet Warszawski)
Computability and continuity of regular functions over ω-words
The class of regular functions from infinite words to infinite words is characterised by MSO-transducers, streaming ω-string transducers (transducers with registers) as well as deterministic two-way transducers with regular look-ahead. In their one-way restriction, the …
April 24, 2019, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
Finite Query Answering in Expressive Description Logics
Evaluating queries in the presence of background knowledge has been extensively studied in several communities. In database theory, it is known as query answering under integrity constraints: given a finite database instance and a set …
April 17, 2019, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Register Automata with Extrema Constraints, and an Application to Two-Variable Logic
I will present joint work with Thomas Zeume. In this work, we study a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain …
April 10, 2019, 2:15 p.m.
Alexander Rabinovich (Tel Aviv University)
Degrees of Ambiguity of Büchi Tree Automata
An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is finitely (respectively, countable) ambiguous if for every input it has at most finitely (respectively, countable) many accepting …
April 3, 2019, 2:15 p.m.
Nir Piterman (Chalmers University of Technology)
Synthesis From Temporal Specifications
In this talk I will present the GR[1] approach to synthesis, the automatic production of designs from their temporal logic specifications. We are interested in reactive systems, systems that continuously interact with other programs, users, …
March 27, 2019, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Georg Zetzsche (Towards Regular Separability of Vector Addition Systems)
I will present a general approach to regular separability in subclasses of vector addition systems. I will sketch the proofs of two new decidability results for regular separability: 1-VASS languages vs VASS languages and Z-VASS …
March 20, 2019, 2:15 p.m.
Joanna Ochremiak (CNRS, LaBRI, Bordeaux)
On the power of symmetric linear programs
We consider families of symmetric linear programs (LPs) that decide a property of graphs in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer …
March 13, 2019, 2:15 p.m.
Marcin Przybyłko (Uniwersytet Warszawski)
On computing measures of open sets of trees
Since Gogacz et al. proved that regular languages of infinite trees are universally measurable, the problem of computing a measure of a given regular set became an appealing and, it seems, difficult problem. Up …
March 6, 2019, 2:15 p.m.
Mikołaj Bojańczyk (joint work with Szymon Toruńczyk) (Uniwersytet Warszawski)
Fixed dimension polynomial time
We describe a complexity class for sets with atoms, which contains problems on orbit-finite inputs like graph reachability, emptiness and minimisation for automata. The idea is that the algorithm must be polynomial for inputs that …
Feb. 27, 2019, 2:15 p.m.
Bartosz Klin (joint work with Clovis Eberhart) (Uniwersytet Warszawski)
with atoms (History-dependent mu-calculus)
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 …