Process algebra based analysis and verification for asynchronous communications appeared in parallel programs

本年度，我们研究了正则表达式模式匹配问题（称为RPM）的Knuth-Morris-Pratt类型算法及其位置和长度的特征，这些研究来自我们前几年的研究，其中我们研究了基于协调语言和元组空间的并行程序。在这种情况下，元组空间被建模的fineite stae机（FSM）和跟踪的过程被建模的字符串或动作序列，在协调语言的基本操作。对于RPM，我们采用基于字符串左商的正则表达式函数代替有限自动机方法，以避免并行过程基于状态建模中的“状态空间爆炸问题”。因此，我们构造了基于正则表达式函数的算法来求解RPM，并在正则表达式的某些情况下找到它的位置和长度。我们在“Ouyou-suugaku Goudou Kenkyu Syukai”和“The 67^ National Convention of IPSJ”上发表了这些结果<th>。

In this year, we investigated Knuth-Morris-Pratt type algorithms for regular expression pattern matching problems (called RPM) and for characterize its position and length.These investigations were derived from our research at the previous years, in which we study parallel programs base on coordination language and tuple space. In this situation, tuple space is modeled by fineite stae machine(FSM) and trace of process is modeled by string or sequence of actions that are primitive operations in coordination language. And we treat some problems in the field of model checking as acceptance problems for FSM or equivalently RPM.To treat RPM, we adopt regular expression function based on left quotient for strings instead of finite automata approach in order to avoid the "explosion problems for state space" in state based modeling of parallel processes. As a result we constructed algorithms based on regular expression function for solving RPM and for finding the position and length of it in some case of regular expressions.We presented these results at "Ouyou-suugaku Goudou Kenkyu Syukai" and "The 67^<th> National Convention of IPSJ".