Cotygodniowe seminarium badawcze
Organizatorzy
- prof. dr hab. Mikołaj Bojańczyk
- prof. dr hab. Damian Niwiński
Informacje
środy, 14:15 , sala: 5440Dziedziny badań
Lista referatów
-
31 maja 2006 14:15
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 …
-
24 maja 2006 14:15
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 …
-
10 maja 2006 14:15
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. …
-
26 kwietnia 2006 14:15
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 …
-
29 marca 2006 14:15
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 …
-
22 marca 2006 14:15
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 …
-
15 marca 2006 14:15
Hugo Gimbert
Positional Stochastic Strategies
We present ongoing work on positionality of full-information, two-player, zero-sum stochastic games with finitely many states.
-
3 marca 2006 14:15
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 …
-
22 lutego 2006 14:15
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 …
-
18 stycznia 2006 14:15
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 …
-
14 grudnia 2005 14:15
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 …
-
7 grudnia 2005 14:15
Thomas Colcombet (Rennes) (Uniwersytet Warszawski)
Infnite games on finite graphs
We consider games played on an arena (a graph) by two antagonistic players. In such a game, each player, when there is its turn, chooses an edge to follow, originating in the current position. The …
-
7 grudnia 2005 14:00
Thomas COLCOMBET (Uniwersytet w Rennes (Francja), CNRS)
Infinite games on finite graphs
Autorskie streszczenie wykladu: We consider games played on an arena (a graph) by two antagonistic players. In such a game, each player, when there is its turn, chooses an edge to follow, originating in the …
-
30 listopada 2005 14:15
Slawomir Lasota (Uniwersytet Warszawski)
One-clock timed automata
For timed automata with two clocks emptyness in decidable but universality and containment are not. We will show that all these problems are decidable for alternating timed automata, but with only one clock. The non-primitive-recursive …
-
23 listopada 2005 14:15
Slawomir Lasota (Uniwersytet Warszawski)
Complexity of bisimulation equivalence
An overview of known results and open problems in checking bisimulation equivalence on infinite graphs. In particular, graphs generated by context-free grammars and pushdown automata will be considered. Relationship to language equivalence will be pointed …
-
18 listopada 2005 14:15
Stephan Kreutzer (Uniwersytet Warszawski)
DAG-width and Parity Games
Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm development. Tree-width is characterised by a game known …
-
2 listopada 2005 14:15
Hugo Gimbert (joint work with Wieslaw Zielonka)
Positional Payoff Games
I will present some results about the existence of positional optimal strategies in two-players antagonistic games and of positional Nash equilibria in multiplayer games
-
19 października 2005 14:15
Damian Niwinski (joint work with T. Knapik, P. Urzyczyn, and I. Walukiewicz) (Uniwersytet Warszawski)
Model checking of panic automata
Panic automata, invented by Pawel Urzyczyn, extend the concept of 2nd order pushdown automata (with stacks of stacks), by a destructive move called panic. They are in a sense equivalent to 2nd order tree grammars. …
-
5 października 2005 14:15
Mikolaj Bojanczyk (joint with Igor Walukiewicz) (Uniwersytet Warszawski)
Unranked Tree Algebra
I will present an algebra for recognizing languages of unranked, finite trees. This algebra is a special case of a transformation semigroup. The talk will focus on analyzing algebras that correspond to languages defined in …