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

April 21, 2010, 2:15 p.m.
Vince Barany (Rheinisch-Westfälische Technische Hochschule Aachen)
Querying the Guarded Fragment
Evaluating a boolean conjunctive query q over a guarded first-ordertheory T is equivalent to checking whether (T & not q) is unsatisfiable.This problem is relevant to the areas of database theory anddescription logic. Since q …
April 14, 2010, 2:15 p.m.
Arnaud Carayol (Institut Gaspard-Monge)
Linear orderings in the pushdown hierarchy.
March 31, 2010, 2:15 p.m.
Mr. Nobody. (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
March 24, 2010, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
On topological complexity of MSO+U over infinite words
In [1] Bojańczyk considered WMSO+U logic and a new type of automata: max-automata. His main result is a conclusion that this logic is decidable over Ω. There arise the natural questions about expressive power of …
March 17, 2010, 2:15 p.m.
Clemens Ley (Oxford)
Towards effective characterizations of data languages.
We study the following decision problem. Given a deterministicregister automaton and a logic, decide if the language recognized bythe register automaton can be defined in the logic. This studyrequires new insights into deterministic register automata, …
March 10, 2010, 2:15 p.m.
Vaclav Brozek (Masaryk University)
Simple stochastic games on pushdown automata zoo
I will try to answer some suitable superset of the following questions: What the hell are simple stochastic games? Why should someone want to play it on pushdown automata? What are the natural habitats of …
March 3, 2010, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata. (part 2)
A second order pushdown automaton is a pushdown automaton, which has a stack of stacks. It works like a normal pushdown automaton, seeing only the topmost sybmol on the topmost stack, but it has additional …
Feb. 24, 2010, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata.
A second order pushdown automaton is a pushdown automaton, which has a stack of stacks. It works like a normal pushdown automaton, seeing only the topmost sybmol on the topmost stack, but it has additional …
Feb. 17, 2010, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
joint work with Luc Segouﬁn (Automata based veriﬁcation over linearly ordered data domains)
In this paper we work over linearly ordered data domains equipped with ﬁnitely many unary predicates and constants. We consider nondeterministic automata processing words and storing ﬁnitely many variables ranging over the domain. During a …
Jan. 27, 2010, 1 p.m.
Szczepan Humel & Paweł Parys (Uniwersytet Warszawski)
joint work with Szymon Toruńczyk) & Evaluation of normalized mu-calculus formulas is polynomial for fixed structure size (Topological Complexity of omega-BS regular languages)
Szczepan 13.00Bojańczyk and Colcombet have recently introduced new classes of omega languages, \omega B-, \omega S- and \omega BS-regular languages. All those classes can be characterized by counter automata with different acceptance conditions or by …
Jan. 20, 2010, 2:15 p.m.
Brak
Nie ma seminarium
W najbliższą środę, nie ma seminarium.
Jan. 13, 2010, 2:15 p.m.
Damian Niwiński (Uniwersytet Warszawski)
joint work with Alexander Rabinovich and Adam Radziwonczyk-Syta (On the Borel complexity of MSO definable sets of branches)
What sets of infinite words can be defined by means of MSO formulas interpreted in a binary tree, if we additionally allow some monadic predicates over the nodes ? We show that topologically these languages …
Jan. 6, 2010, 2:15 p.m.
Tomasz Idziaszek (Uniwersytet Warszawski)
Single-Type Approximations of Regular Tree Languages
XML Schema Definitions can be adequately abstracted by the single-type regular tree languages, which form a strict subclass of regular unranked tree languages. Sadly, in this respect, XSDs are not closed under the basic operations …
Dec. 16, 2009, 2:15 p.m.
Konrad Zdanowski (Uniwersytet Warszawski)
joint work with Thomas Colcombet (part 2 / A Tight Lower Bound for Determinization of Transition Labeled Buchi Automata)
We present a lower bound for the problem of translating a Buchi word automaton into a deterministic Rabin word automaton when both the Buchi and the Rabin conditions label transitions rather than states. This lower …
Dec. 9, 2009, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Slawomir Lasota (Query Width)
Query Width is a complexity measure, like Tree Width, or Clique Width. The difference is that Tree Width or Clique Width measure the complexity of a graph, while Query Width measures the complexity of a …