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 19, 2013, 2:15 p.m.
Aleksander Zabłocki (Uniwersytet Warszawski)
Squeezing theory into practice: automata in natural language processing
I will sketch some aspects of using automata in natural language processing: more precisely, in efficient applying a set of search-replace rules for richly annotated text. Although this might seem trivial (build-determinize-compose-run), our practical applications …
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 …