Organizers

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Information

Wednesdays, 2:15 p.m. , room: 5440

Research fields

List of talks

Oct. 25, 2006, 2:15 p.m.
Jacek Jurewicz (Uniwersytet Warszawski)
Panic automata
Panic automata are an extension of second-order pushdown automata (that operate on a second-order pushdown store, ie. a stack of stacks) by the destructive "panic" operation introduced by P. Urzyczyn in order to fully relate …
Oct. 11, 2006, 2:15 p.m.
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 determinacy of a …
Oct. 4, 2006, 2:15 p.m.
Henrik Bjorklund (Dortmund)
Toward Regular Data Languages
June 7, 2006, 2:15 p.m.
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 …
May 31, 2006, 2:15 p.m.
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 …
May 24, 2006, 2:15 p.m.
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 …
May 10, 2006, 2:15 p.m.
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. …
April 26, 2006, 2:15 p.m.
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 …
March 29, 2006, 2:15 p.m.
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 …
March 22, 2006, 2:15 p.m.
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 …
March 15, 2006, 2:15 p.m.
Hugo Gimbert
Positional Stochastic Strategies
We present ongoing work on positionality of full-information, two-player, zero-sum stochastic games with finitely many states.
March 3, 2006, 2:15 p.m.
Emanuel Kieronski (Wroclaw, joint work with Martin Otto)
Logic with two variables and equivalence relations
We study first-order logic with two variables FO2 and establish a small substructure property. Similar to the small model property for FO2 we obtain an exponential size bound on embedded substructures, relative to a fixed …
Feb. 22, 2006, 2:15 p.m.
Mikolaj Bojanczyk (Joint work with C. David, A. Muscholl, L. Segoufin and T. Schwentick. ) (Uniwersytet Warszawski)
Data words
A data word is a word that is annotated with data values. Every position in a data word has the usual label from a finite alphabet, but it also has a label from an infinite …
Jan. 18, 2006, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
Games for the Wadge Hierarchy of Deterministic Tree Languages
In the case of infinite words, the hierarchy of regular languages defined by continuous reductions is well understood since Wagner's 1977 paper. In particular, there exists a procedure calculating the exact level of a given …
Dec. 14, 2005, 2:15 p.m.
Eryk Kopczynski (Uniwersytet Warszawski)
Half-positionally determined winning conditions in infinite games
We consider half-positionally determined winning conditions in infinite games played on a graph by two antagonistic players Eve and Adam. We call a winning condition W _positionally determined_ if, for every infinite game (G,W) using …