**Seminar 1**

**Title**: Introduction to AIST/CVS

**Speaker**:Prof. Yoshiki Kinoshita £¨National Institute of Advances
Industrial Science and Technology Japan£©

**Time**:From 3£º00pm, Thursday£¬April 23

**Seminar 2**

**Title**:Tree Automata for Non-Linear Arithmetic

**Speaker**:Dr. Hitoshi Ohsaki£¨National Institute of Advances
Industrial Science and Technology Japan£©

**Venue**:Lecture Room,State Key Lab of Computer Science, Level
3 Building #5, Institute of Software, CAS

**Abstract:**

Tree automata modulo associativity and commutativity axioms,called AC tree automata,
accept trees by iterating the transition modulo equational reasoning. The class
of languages accepted by monotone AC tree automata is known to include the solution
set of the inequality x * y >= z, which implies that the class properly includes
the AC closure of regular tree languages. In the talk, we attempt to characterize
the expressiveness of monotone AC tree automata, based on the observation that,
in addition to

polynomials, a class of exponential constraints (called monotone exponential
Diophantine inequalities) can be expressed by monotone AC tree automata with
a minimal signature. Moreover, we show that a class of arithmetic logic consisting
of monotone exponential Diophantine inequalities is definable by monotone AC
tree automata. The results to be presented in the talk are

obtained by applying our novel tree automata technique, called "linearly
bounded projection." This is a joint work with Naoki Kobayashi of Tohoku
University, Japan.