Lista referatów

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

  Mikolaj Bojanczyk (Uniwersytet Warszawski)

  Automata and logics for data values

  An XML document is commonly modeled as a tree, with nodes labeled by a finite alphabet. Properties of such documents can be expressed using finite tree automata, which are well understood and admit efficient algorithms. However, the finite alphabet representation does not capture some aspects of a d...

• 2007-10-24, godz. 14:15, 5870

  Wojciech Czerwinski (Uniwersytet Warszawski)

  Simulation between games

  I will show some results of my investigations on bisimulation with a weakened winning condition for Spoiler. I will present a polynomial algorithm deciding this (modified) bisimulation between Buchi games. I will also talk about positionality, and other types of bisimulation....

• 2007-10-17, godz. 14:15, 5870

  Balder ten Cate (joint work with J. van Benthem and J. Vaananen) (Uniwersytet Warszawski)

  Lindstrom theorems for fragments of first-order logic

  Lindstrom theorems characterize logics in terms of model-theoretic conditions such as Compactness and the Loewenheim-Skolem property. Most existing Lindstrom theorems concern extensions of first-order logic. On the other hand, many logics relevant to computer science are fragments or extensions of f...

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

  Hugo Gimbert (joint work with F. Horn) (Uniwersytet Warszawski)

  Algorithms for Solving Simple Stochastic Games

  A Simple Stochastic Game is played by two players called Min and Max, moving turn by turn a pebble along edges of a graph. Player Max wants the pebble to reach a special vertexc called the target vertex. On some special vertices called random vertices, the next vertex is chosen randomly according to...

• 2007-05-30, godz. 14:15, 5870

  Paweł Parys (joint work with Krzysztof Onak) (Uniwersystet Warszawski)

  Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders

  We extend the binary search technique to searching in trees. We consider two models of queries: questions about vertices and questions about edges. We present a general approach to this sort of problem, and apply it to both cases, achieving algorithms constructing optimal decision trees. In the edge...

• 2007-05-23, godz. 14:15, 5870

  Anna Niewiarowska (Uniwersytet Warszawski)

  Probalistically Checkable Proofs and approximation hardness (continued)

• 2007-05-16, godz. 14:15, 5870

  Artur Jeż (Uniwersytet Warszawski)

  Conjunctive grammars

  I discuss the notion of conjunctive grammars, introduced by A. Okhotin in 2001. In short they can be described as extension of context-free grammars with additional operation of intersection within the body of any production. This natural extension still leads to inheriting many nice properties from...

• 2007-05-09, godz. 14:15, 5870

  Anna Niewiarowska

  Probalistically Checkable Proofs and approximation hardness

  The PCP theorem states that for each NP language there is a verifier that checks membership proofs probabilistically, using only logaritmic number of random bits and reading constant number of proof bits. I will show that many approximation hardness results are consequences of that theorem. I will a...

• 2007-04-25, godz. 14:15, 5870

  Mikołaj Bojańczyk (Uniwersytet Warszawski)

  Forest expressions

  I will talk about a type of regular expression for unranked trees. The main focus is on connections with logic: the expressions correspond to chain logic, the star-free expressions correspond to first-order logic, and finally, a concatenation hierarchy is shown to correspond to the quantifier altern...

• 2007-04-18, godz. 14:15, 5870

  Konrad Zdanowski (Uniwersytet Warszawski)

  Undecidability methods for the word problem in finite semigroups

Strony