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

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 …
Dec. 2, 2009, 2:15 p.m.
Konrad Zdanowski (Uniwersytet Warszawski)
joint work with Thomas Colcombet (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 …
Nov. 25, 2009, 2:15 p.m.
Marcin Dziubinski (Uniwersytet Warszawski)
joint work with Jaideep Roy and Debabrata Datta (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 …
Nov. 18, 2009, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Algorithm computing Simon decomposition in polynomial time
Simon decomposition is a very important tool in the finite monoid theory. I will present a new, efficient construction of the Simon decomposition. All previous constructions were starting from a finite monoid. When we have …
Nov. 4, 2009, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
joint work with Shunichi Amano and Leonid Libkin (Consistency of XML Schema Mappings)
Relational schema mappings have been extensively studied in connection with data integration and exchange problems, but mappings between XML schemas have not received the same amount of attention. I will present an attempt to develop …
Oct. 28, 2009, 2:15 p.m.
Diego Figueira (Laboratoire Spécification et Vérification (LSV))
Huge lower bounds of weak logics for data words
I will show how to code very hard problems into the satisfiability of the linear temporal logic (LTL) equipped with one register to store and test data values from positions of a data word. I …
Oct. 21, 2009, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski) (Uniwersytet Warszawski)
Languages over Commutative Alphabets (part 2)
We consider languages accepted by non-deterministic finite automata and context-free grammars, except that we treat the language in a commutative way: we do not care about the order of letters in the accepted word, but …
Oct. 14, 2009, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
Languages over Commutative Alphabets
We consider languages accepted by non-deterministic finite automata and context-free grammars, except that we treat the language in a commutative way: we do not care about the order of letters in the accepted word, but …
Oct. 7, 2009, 2:15 p.m.
Wouter Gelade (Hasselt)
Dynamic Complexity of Formal Languages
We will discuss the dynamic complexity of formal languages. As opposed to static complexity theory, which investigates the complexity of problems over fixed structures, dynamic complexity theory concerns the complexity necessary to maintain the answer …