Organizers

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Information

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

Research fields

List of talks

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
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
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
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
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 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 …
Dec. 2, 2009, 2:15 p.m.
Konrad Zdanowski (Uniwersytet Warszawski)
joint work with Thomas Colcombet
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 …
Nov. 25, 2009, 2:15 p.m.
Marcin Dziubinski (Uniwersytet Warszawski)
joint work with Jaideep Roy and Debabrata Datta
Location games are games where players select a subsets of points of some space, determining the division of this spaces into areas of points that are closer to the points of one of the players …