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

June 12, 2013, 2:15 p.m.
Laure Daviaud (LIAFA, Université Paris 7)
joint work with Thomas Colcombet (Approximate comparison of distance automata)
Distance automata are automata weighted over the semiring (N U {+infinity},min,+) (the tropical semiring). Such automata compute functions from words to N U {+infinity} such as the number of occurrences of a given letter. It …
June 5, 2013, 2:15 p.m.
Claire David (Université Paris-Est Marne-la-Vallée)
joint work with W.Czerwinski, K. Losemann, W. Martens (Deciding Definability by Deterministic Regular Expressions)
Intuitively, a regular expression is deterministic if, when reading a word from left to right without looking ahead, one always knows where in the expression the next symbol will be matched. The set of languages …
May 29, 2013, 2:15 p.m.
Piotr Hofman (Uniwersytet Warszawski)
joint work with Sławek Lasota, Patrick Toetzke and Richard Mayr (Simulation of one-counter automata)
The talk will be devoted to the following decision problem: for two given one-counter automata, find the winner of Simulation Game between these automata. We will discuss variants of the problems, influencing its decidability and …
May 15, 2013, 2:15 p.m.
Denis Kuperberg (The Hebrew University of Jerusalem)
Regular cost functions on finite words
The theory of regular cost functions, initiated by Thomas Colcombet and following work with Mikołaj Bojańczyk, is a satisfying framework to extend a large spectrum of results on regular languages to a quantitative setting. I …
May 8, 2013, 2:15 p.m.
Howard Straubing (Boston College)
Quantifier Alternation in First-order Logic with Two Variables over Words
It has long been known that every first-order formula over linear order is equivalent to one that uses only three bound variables. This talk is about what properties of finite words can be defined if …
April 24, 2013, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Luc Segoufin and Szymon Toruńczyk (Verification of Database-driven Systems via Amalgamation)
We describe a general framework for static verification of systems that base their decisions upon queries to databases. The database is specified using constraints, typically a schema, and is not modified during a run of …
April 17, 2013, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
Decidable properties of game automata
For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognise this language with a non-deterministic or alternating parity automaton. These questions are known as, respectively, …
April 10, 2013, 2:15 p.m.
Michał Szynwelski (Uniwersytet Warszawski)
Deterministic nominal automata minimization algorithm
My talk will be about the new representation of structures based on the nominal sets. I will present the minimization algorithm of deterministic nominal automata that use this representation. But the purpose of my work …
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 …