讲座题目：(Max,+)-automata algebraically and co-algebraically, their determinization and applications to supervisory control of timed systems

讲座人：  Jan Komenda，PH. D

讲座时间：15:00-17:00

讲座日期： 2016-6-1

地点：   长安校区 图书馆西附楼一层报告厅 

主办单位：必赢线路检测中心  图书馆

讲座内容简介：

    (Max,+) automata are weighted automata with weights (multiplicities) in the $(\mathbb{R} \cup \{-\infty\},\max,+)$ semiring.They have a strong expressive power in terms of timed Petri nets: every 1-safe timed Petri net can be represented by a special (max,+) automaton, called heap model (or heap automaton). We have proposed recently a direc and compositional transformation of (max,+) automata into  timed Petri nets. (Max,+) automata and corresponding formal power series can be studied both algebraically and co-algebraically. Co-algebraic approach in the category of Sets, where formal power series form a final co-algebra (with weighted automaton structure defined in terms of left quotiens) is limited to deterministic weighted automata. On the other hand, the co-algebraic approach in the category of Vec of vector spaces can be used for general nondeterministic weighted automata.

The synchronous product of (max,+) automata will be presented that clearly separates the quantitative (timing) and logical (support language) aspects. Interestingly, the state explosion problem is not an issue for the quantitative aspect as the state set of the synchronous product is the union and not the cartesian product of local carrier sets. However, resulting nondeterministic automata are difficult to use in performance evaluation and supervisory control. Therefore, we have studied determinization of (max, +) automata (which is not always possible in terms of a finite state automaton) and proposed new sufficient conditions for termination of the determinization procedure based on the normalization.

We will also discuss an alternative approach based on the concept of fairness well known in the concurrency theory.

讲座人简介

Jan Komenda is a researcher at Institute of Mathematics, Czech Academy of Sciences, Czech Republic.