Lista referatów

• 2006-10-11, godz. 14:15, 5870

  Eryk Kopczynski (Uniwersytet Warszawski)

  Half-positionally determined winning conditions

  Basic definitions: games, half-positional determinacy. - Half-positional winning conditions and omega-regular languages. How to check whether the given omega-regular winning condition is finitely half-positional? - Positional/suspendable conditions (PS). Definitions and examples. Half-positional det...

• 2006-10-04, godz. 14:15, 5870

  Henrik Bjorklund (Dortmund)

  Toward Regular Data Languages

• 2006-06-07, godz. 14:15, 5870

  Sibylle Froeschle

  The computational dichotomy of true-concurrency

  In concurrency theory there is a divide between the interleaving approach, in which concurrency is reduced to nondeterministic sequentialization, and the truly-concurrent approach, which represents concurrency in a more faithful way. In this talk I will give an inroduction to true-concurrency, and s...

• 2006-05-31, godz. 14:15, 5870

  Piotr Hoffman (Uniwersytet Warszawski)

  Word problems

  The talk will be an introduction to the world of word problems, in particular word problems for varieties of semigroups. Attention will be paid especially to commutative semigroups (reversible Petri nets). I intend to prove Redei's Theorem on finitely generated commutative semigroups and, if time al...

• 2006-05-24, godz. 14:15, 5870

  Michał Strojnowski (Uniwersytet Warszawski)

  Impossibility Proofs for Distributed Computing

  Many problems have no solution in distributed computing. One of the best known examples is Byzantine Generals Problem, for which it is shown that if at least one third of the generals are malicious, there is no way to achieve mutual consensus among the rest. There are many more such examples, especi...

• 2006-05-10, godz. 14:15, 5870

  Slawomir Lasota (joint work with Wojciech Rytter) (Uniwersytet Warszawski)

  On language and bisimulation equivalence of context-free processes

  In contrast to language equivalence, being undecidable for (normed) context-free grammars, the bisimulation equivalence is decidable; and it is even polynomial for normed grammars.The fastest known algorithm for checking bisimulation equivalence worked in $O(n^{13})$ time. We give an alternative alg...

• 2006-04-26, godz. 14:15, 5870

  Linh Anh Nguyen (joint work with Rajeev Gore) (Uniwersytet Warszawski)

  Tableaux for Regular Grammar Logics of Agents Using Automaton-Modal Formulae

  A grammar logic is a multimodal logic extending Kn with inclusion axioms of the form [t1]...[th]j (r) [s1]...[sk]j where t1, ..., th, s1, ..., sk are modal indices. Such an axiom can be seen as the grammar rule t1...th (r) s1...sk where the corresponding side stands for the empty word if k =...

• 2006-03-29, godz. 14:15, 5870

  Mikolaj Bojanczyk (Uniwersytet Warszawski)

  Reachability in vector-addition systems

  An (n-dimensional) vector addition system is a finite set V of n-dimensional integer vectors. The reachability problem is as follows: given V and two n-dimensional vectors of *naturals * v and w, determine if one can produce a sequence v=v(1),v(2),..,v(k)=w of vectors of naturals, such that each dif...

• 2006-03-22, godz. 14:15, 5870

  Piotr Hoffman (Uniwersytet Warszawski)

  Word problems in sums of monoids

  In the talk I will investigate the decidability of word problems for amalgams (sums) of monoids. Word problems for amalgams of monoids are equivalent to sums of congruence relations on words. They are also equivalent to unions of equational theories over signatures in which only unary function symbo...

• 2006-03-15, godz. 14:15, 5870

  Hugo Gimbert

  Positional Stochastic Strategies

  We present ongoing work on positionality of full-information, two-player, zero-sum stochastic games with finitely many states....

Strony