Lista referatów

• 2007-04-03, godz. 14:15, 5870

  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 a strict hierarchy of the parity-game tree languages, in the sense of Wadge reducibility. Next, we observ...

• 2007-03-21, godz. 14:15, 5870

  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 of paths". For regular linear-time specifications, probabilistic and topological largness coinci...

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

  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....

• 2007-02-28, godz. 14:15, 5870

  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....

• 2007-01-03, godz. 14:15, 5870

  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 output). I will present several classes of ration...

• 2006-12-20, godz. 14:15, 5870

  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 equivalence for the abovementioned class....

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

  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 if a given regular tree language can be expressed by a formula of this logic....

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

  Marcin Jurdziński (Uniwersytet Warszawski)

  Subexponential algorithms for solving parity games

  Solving parity games is polynomial time equivalent to the modal mu-calculus model checking problem and its exact computational complexity is an intriguing open problem: it is known to be in UP (unambiguous NP) and co-UP, but no polynomial time algorithm is known. This talk surveys a few recent algor...

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

  Filip Murlak (Uniwersytet Warszawski)

  Weak automata and Wadge hierarchy

  I will show a new lower bound for the height of the Wadge hierarchy of weak tree languages, i. e., the languages of infinite trees recognizable with weak automata. To this end I will prove that the family of weak tree languages is closed by three natural set-theoretic operations that can be used to ...

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

  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 second-order automata to second-order grammars. I will show how a panic ...

Strony