joint work with Thomas Colcombet

Speaker(s)

Amaldev Manuel

Affiliation

Uniwersytet Warszawski

Date

Feb. 18, 2015, 2:15 p.m.

Room

room 5870

Title in Polish

Combinatorial expressions

Seminar

Seminar Automata Theory

---

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.    

---