Lista referatów

• 2008-04-02, godz. 14:15, 5870

  Sybille Froeschle (Oldenburg) (Uniwersytet Warszawski)

  The Insecurity Problem: Tackling Unbounded Data

  In this talk we focus on tackling the insecurity problem of security protocols in the presence of an unbounded number of data such as nonces or session keys. First, we pinpoint four open problems in this category. The first two problems concern protocols with natural restrictions that any `realist...

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

  Christof Loeding (Aachen) (Uniwersytet Warszawski)

  The nondeterministic Mostowski hierarchy and distance-parity automata

  The number of priorities that nondeterministic Mostowski or parity automata on infinite trees can use in their acceptance condition induces a hierarchy of regular tree languages. This talk is about the problem of deciding for a given regular language of infinite trees on which level of the hierarch...

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

  Szymon Toruńczyk (Uniwersytet Warszawski)

  Property testing regular languages

  Property testing is concerned with the following type of problems: Let L be a property of a class of objects. A property tester for L is an algorithm, which, given an input object w, uses a small number of (possibly random) queries about w to determine with high probability whether w has the proper...

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

  Sławomir Lasota (Uniwersytet Warszawski)

  Lossy Machines

  FIFO- and counter-automata are Turing complete models. I will present a weakening of these models, allowing for spontaneous and non-controllable loss of messages from FIFO (or, respectively, decrements of counters). I will discuss how much this weakening decreases complexity of verification problem...

• 2008-02-27, godz. 14:15, 5870

  Filip Murlak (Uniwersytet Warszawski)

  Weak index versus Borel rank

  I will talk about weak recognizability of deterministic languages of infinite trees. I will prove that for deterministic languages the Borel hierarchy and the weak index hierarchy coincide. Furthermore, I will propose a procedure computing for a deterministic automaton an equivalent minimal index we...

• 2008-01-16, godz. 14:15, 5870

  Aymeric Vincent (Uniwersytet Warszawski)

  Mec 5 and AltaRica

  In this presentation, we will present the Mec 5 verification tool and its environment. In particular, we will talk about the AltaRica formalism which has been developed in Bordeaux for more than ten years. We will then focus on two aspects of Mec 5: - its technical basis, mainly BDDs. We will tr...

• 2008-01-09, godz. 14:15, 5870

  Leszek Kolodziejczyk (Uniwersytet Warszawski)

  The polynomial and linear time hierachies in a weak theory of arithmetic

  I will show that a very weak theory of arithmetic associated with the complexity class AC^0 does not prove that the polynomial time hierarchy is equal to the linear time hierarchy. The proof uses Ajtai's old bounds on how well polysize bounded depth circuits can compute parity....

• 2007-11-28, godz. 14:15, 5870

  Andrzej Nagorko (Uniwersytet Warszawski)

  Automatic groups, continued

• 2007-11-21, godz. 14:15, 5870

  Wieslaw Zielonka

  Games with priorities

• 2007-11-14, godz. 14:15, 5870

  Andrzej Nagorko (Uniwersytet Warszawski)

  Automatic groups

  I'll talk about automatic groups, which incorporate finite state automata into geometric group theory in a prolific way. The class of automatic groups was introduced by Cannon and Thurston in the eighties....

Strony