Organizatorzy

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

Informacje

środy, 14:15 , sala: 5050

Dziedziny badań

Lista referatów

31 marca 2010 14:15
Mr. Nobody. (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
24 marca 2010 14:15
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 …
17 marca 2010 14:15
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, …
10 marca 2010 14:15
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 …
3 marca 2010 14:15
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 …
24 lutego 2010 14:15
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 …
17 lutego 2010 14:15
Szymon Toruńczyk (Uniwersytet Warszawski)
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 …
27 stycznia 2010 13:00
Szczepan Humel & Paweł Parys (Uniwersytet Warszawski)
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 …
20 stycznia 2010 14:15
Brak
Nie ma seminarium
W najbliższą środę, nie ma seminarium.
13 stycznia 2010 14:15
Damian Niwiński (Uniwersytet Warszawski)
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 …
6 stycznia 2010 14:15
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 …
16 grudnia 2009 14:15
Konrad Zdanowski (Uniwersytet Warszawski)
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 …
9 grudnia 2009 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
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 …
2 grudnia 2009 14:15
Konrad Zdanowski (Uniwersytet Warszawski)
part 1/ 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 …
25 listopada 2009 14:15
Marcin Dziubinski (Uniwersytet Warszawski)
Location games on multiple disjoint spaces: circles and lines.
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 …