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

  • 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 (r) 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....