Organizatorzy

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

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

4 grudnia 2013 14:15
Denis Kuperberg (Uniwersytet Warszawski)
Nondeterminism in the Presence of a Diverse or Unknown Future (joint work with Udi Boker, Orna Kupferman, Michał Skrzypczak)
One of the advantages of deterministic automata is that they composewell with trees and games. In the theory of cost functions, suchdeterministic automata are not always available, so a weaker notionwas introduced: history-deterministic automata, which …
27 listopada 2013 14:15
Adam Witkowski (Uniwersytet Warszawski)
Regular Tree Pattern Queries and Datalog
Regular Tree Pattern Queries (RTPQ) are queries for data trees that were defined during a research on Active XML.We found that this formalism is interesting on its own and closely connected to Datalog.I will talk …
20 listopada 2013 14:15
Thomas Colcombet (LIAFA, Université Paris 7)
Regular Cost-Functions and Internal Set Theory (continuation)
We will show how to solve cost-MSO over finite words, paying a particular attention to the use of the non-standard aspect of Internal Set Theory.
13 listopada 2013 14:15
Thomas Colcombet (LIAFA, Université Paris 7)
Regular Cost-Functions and Internal Set Theory
In this talk, I will take as an excuse regular cost-functions (an extension of regular languages with quantitative capabilities) for presenting "Internal Set Theory" (IST), an axiomatic extension of ZFC that has native non-standard analysis …
6 listopada 2013 14:15
Paweł Parys (Uniwersytet Warszawski)
Asymptotic MSO and lossy tiling problems (joint work with Achim Blumensath and Thomas Colcombet)
I will talk about a new extension of the MSO logic in the style of MSO+U, which is called Asymptotic MSO. This logic refers to structures (in particular omega-words) whose elements are weighted with natural …
30 października 2013 14:15
Matteo Mio (CWI - Amsterdam)
Game Semantics for Probabilistic mu-Calculi
In this talk I will consider (a family of) probabilistic (or quantitative) variants of Kozen's Modal mu-Calculus, designed for expressing properties of probabilistic-nondeterministic transition systems. Two type of semantics can be defined for these logics: …
23 października 2013 14:15
Matteo Mio (CWI - Amsterdam)
Foundations of Quantitative Logics based on Functional Analysis
Several notions of bisimulation relations for Probabilistic Nondeterministic Transition Systems (PNTS's) have been proposed in the literature. I will develop the theory of what I call "Upper-Expectation bisimilarity" using standard results of linear algebra and …
16 października 2013 14:15
Teodor Knapik (joint work with Didier Caucal) (University of New Caledonia)
Two MSO-compatible operations: Shelah-Stupp's iteration and Muchnik's iteration
In the early seventies, Shelah proposed a model-theoretic construction,nowadays called "iteration". This construction is an infinitereplication in a tree-like manner where every vertex possesses its owncopy of the original structure. Stupp proved that the decidability …
19 czerwca 2013 14:15
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 …
12 czerwca 2013 14:15
Laure Daviaud (LIAFA, Université Paris 7)
Approximate comparison of distance automata (joint work with Thomas Colcombet)
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 …
5 czerwca 2013 14:15
Claire David (Université Paris-Est Marne-la-Vallée)
Deciding Definability by Deterministic Regular Expressions (joint work with W.Czerwinski, K. Losemann, W. Martens)
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 …
29 maja 2013 14:15
Piotr Hofman (Uniwersytet Warszawski)
Simulation of one-counter automata (joint work with Sławek Lasota, Patrick Toetzke and Richard Mayr)
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 …
15 maja 2013 14:15
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 …
8 maja 2013 14:15
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 …
24 kwietnia 2013 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Verification of Database-driven Systems via Amalgamation (joint work with Luc Segoufin and Szymon Toruńczyk)
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 …