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. 17, 2007, 2:15 p.m.
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 …
Oct. 10, 2007, 2:15 p.m.
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 …
May 30, 2007, 2:15 p.m.
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 …
May 23, 2007, 2:15 p.m.
Anna Niewiarowska (Uniwersytet Warszawski)
Probalistically Checkable Proofs and approximation hardness (continued)
May 16, 2007, 2:15 p.m.
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. …
May 9, 2007, 2:15 p.m.
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 …
April 25, 2007, 2:15 p.m.
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, …
April 18, 2007, 2:15 p.m.
Konrad Zdanowski (Uniwersytet Warszawski)
Undecidability methods for the word problem in finite semigroups
April 3, 2007, 2:15 p.m.
Damian Niwiński (Uniwersytet Warszawski)
Two remarks on the role of ranks in parity games
These observations are of very different nature, but they can be read as evidences for the lower bound, and the upper bound, respectively. At first we show that the number of ranks gives rise to …
March 21, 2007, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
Temporal Logics and Model Checking for Fairly Correct Systems
I will present recent results on model checking for fairly correct systems (D. Varacca, H. Voelzer, LICS'06). A fair variant of a specfication is obtained by replacing "for all paths" by "for a large set …
March 14, 2007, 2:15 p.m.
Pawel Parys (Uniwersytet Warszawski)
On Systems of Equations Satisfied in All Commutative Finite Semigroups
I show the algorithmic procedure for solving the problem: check if a system of equations has a solution in every commutative finite semigroup.
Feb. 28, 2007, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
A paradox for CTL
The property "every path belongs to (ab)*a(ab)*" can be expressed in CTL; but necessarily using existential modalities. This shows that ACTL;does not capture the common fragment of CTL and LTL.
Jan. 3, 2007, 2:15 p.m.
Maria Fraczak (Uniwersytet Warszawski)
Defining rational functions by deterministic pushdown transducers
Rational functions are partial functions from words to words. They are implemented by finite state automata extended to produce output; only some of them can be realized by deterministic pushdown transducers (deterministic pushdown automata producing …
Dec. 20, 2006, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
Bisimulation equivalence and commutative context-free grammars
The topic will be the class of processes (transition systems) generated from the commutative context-free grammars. I will present a method enabling to prove decidability (and to compute the complexity) of different variants of bisimulation …
Nov. 29, 2006, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Two-way temporal logic over unranked trees
I will talk about languages of unranked trees that can be defined in a temporal logic with two operators: exists some ancestor, and exists some descendant. The point is to have an algorithm, which decides …