Combinatorial expressions

Prelegent(ci)

Amaldev Manuel

Afiliacja

Uniwersytet Warszawski

Termin

18 lutego 2015 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Thomas Colcombet

Seminarium

Seminarium „Teoria automatów”

---

Combinatorial expressions are expressions built using two kinds of functions --- those having bounded arity unbounded domain (e.g. addition of integers), and those having bounded domain and unrestricted arity (e.g. Boolean OR of k inputs, where k is as large as necessary). These expressions are used to separate subclasses of Data automata. For the talk, I will introduce the expressions, discuss some normal forms for them and show how to prove inexpressibility results using tools from Combinatorics (in particular Hales-Jewett theorem). This work will be presented in STACS.    

---