[4-23]Two Seminars on Thursday from AIST

Date:2009-04-19

There will be two seminars given by two researchers from AIST, National Institute of Advances Industrial Science and Technology, Japan, starting from 3pm, Thursday April 23, 2009.

Seminar 1

Title: Introduction to AIST/CVS
Speaker: Prof. Yoshiki Kinoshita

          National Institute of Advances Industrial Science and Technology, Japan

Seminar 2

Title: Tree Automata for Non-Linear Arithmetic
Speaker: Dr. Hitoshi Ohsaki

          National Institute of Advances Industrial Science and Technology, Japan

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.

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