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

  • Jan. 9, 2008, 2:15 p.m.
    Leszek Kolodziejczyk (Uniwersytet Warszawski)
    The polynomial and linear time hierachies in a weak theory of arithmetic
    I will show that a very weak theory of arithmetic associated with the complexity class AC^0 does not prove that the polynomial time hierarchy is equal to the linear time hierarchy. The proof uses Ajtai's …

  • Nov. 28, 2007, 2:15 p.m.
    Andrzej Nagorko (Uniwersytet Warszawski)
    Automatic groups, continued

  • Nov. 21, 2007, 2:15 p.m.
    Wieslaw Zielonka
    Games with priorities

  • Nov. 14, 2007, 2:15 p.m.
    Andrzej Nagorko (Uniwersytet Warszawski)
    Automatic groups
    I'll talk about automatic groups, which incorporate finite state automata into geometric group theory in a prolific way. The class of automatic groups was introduced by Cannon and Thurston in the eighties.

  • Nov. 7, 2007, 2:15 p.m.
    Mikolaj Bojanczyk (Uniwersytet Warszawski)
    Automata and logics for data values
    An XML document is commonly modeled as a tree, with nodes labeled by a finite alphabet. Properties of such documents can be expressed using finite tree automata, which are well understood and admit efficient algorithms. …

  • Oct. 24, 2007, 2:15 p.m.
    Wojciech Czerwinski (Uniwersytet Warszawski)
    Simulation between games
    I will show some results of my investigations on bisimulation with a weakened winning condition for Spoiler. I will present a polynomial algorithm deciding this (modified) bisimulation between Buchi games. I will also talk about …

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