You are not logged in | Log in
Return to the list of seminars

Seminar Automata Theory

Weekly research seminar


Organizers

Information

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

Research fields

List of talks

  • 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 …

  • Nov. 23, 2006, 2:15 p.m.
    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, …

  • Nov. 15, 2006, 2:15 p.m.
    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 …

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