Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Seminarium „Teoria automatów”

Cotygodniowe seminarium badawcze

Lista referatów

  • 2009-02-25, godz. 14:15, 5870

    Paweł Parys (Uniwersytet Warszawski)

    Lower bound for computing fixed points

    We consider the following problem: There is given a monotone K-argument function f defined on N-bit sequences {0,1}^N. There is also given the following simpliest possible mu-calculus expression: mi(x1).ni(x2).mi(x3).ni(x4)...mi(xK).f(x1,...,xK). The function is given as a black-box: we can only que...

  • 2009-02-18, godz. 14:15, 5870

    Łukasz Kaiser (Aachen)

    Basic Analysis of Structure Rewriting Systems

    A single state of an analyzed system has, in practice, often a complex structure in itself, while in theory it is usually simple in some sense, e.g. it can be a tree. We show how the interpretation of structures of bounded clique-width in the binary tree allows to apply tree automata to the analysis...

  • 2009-01-21, godz. 14:15, 5870

    Henryk Michalewski (Uniwersytet Warszawski)

    Complete pairs of coanalytic sets

  • 2009-01-10, godz. 14:15, 5870

    Robert Dąbrowski (Uniwersytet Warszawski)

    Introducing equations in free semigroup

    Let be given a free monoid with a set of generators E whose cardinality is at least 2. We shall call elements of E 'letters' and elements of E* 'words'. Let also be given a set of 'unknowns'; disjoint with letters. A 'word expression' is defined recursively to be either a letter, an unknown or a non...

  • 2009-01-06, godz. 14:15, 5870

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    A geometrical approach to star height

    I will talk about an algorithm deciding limitedness of distance desert automata (which is the hard part in deciding star height). The algorithm itself is quite simple, and the correctness argument involves concepts such as compact metric space and convergent sequence....

  • 2008-12-10, godz. 14:15, 5870

    Tomasz Idziaszek (Uniwersytet Warszawski)

    EF logic

    I will talk about a simple temporal logic EF over finite words, infinite words and finite trees. I will show that a language is definable by an EF formula if and only if its syntactic algebra satisfies certain equations. Eventually I will present some examples which exhibit the difficulty of EF over...

  • 2008-12-03, godz. 14:15, 5870

    Leszek Kołodziejczyk (Uniwersytet Warszawski)

    Parity games in weak arithmetic theories

    Parity games in weak arithmetic theories I will present A. Beckmann and F. Moller's paper "On the complexity of parity games". The main result of the paper is that positional determinacy of parity games can be proved in a weak subtheory of Peano Arithmetic called S^2_2. The provability of determinac...

  • 2008-11-26, godz. 14:15, 5870

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    The star-height problem

  • 2008-11-05, godz. 14:15, 5870

    Tomasz Jurdziński (Wrocław)

    Leftist grammars

    Leftist grammars were introduced as a tool to show decidability of the accessibility problem in certain general protection systems. In the presentation, I will concentrate on complexity of the membership problem for these grammars and their restricted variants....

  • 2008-10-22, godz. 14:15, 5870

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    Max-regular languages (cont.)