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

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 …
17 kwietnia 2013 14:15
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, …
10 kwietnia 2013 14:15
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 …