Automatic verification for a class of distributed systems

Summary. The paper presents a new analysis method for a class of concurrent systems which are formed of several interacting components with the same structure. The model for these systems is composed of a control process and a set of homogeneous user processes. The control and user processes are modeled by finite labeled state transition systems which interact by means of enabling functions and triggering mechanisms. Based on this structure, an analysis method is presented which allows system properties, derived by reachability analysis for a finite number of user processes, to be generalized to an arbitrary number of user processes. A procedure for the automatic verification of properties such as mutual exclusion and absence of deadlocks is presented and is then used to provide for the first time a fully automated verification of the Lamport's fast mutual exclusion algorithm. Received: October 1998/Accepted January 2000     

Automatic transaction of signal via statistical modeling

The statistical information processing can be characterized by the likelihood function defined by giving an explicit form for an approximation to the true distribution. This mathematical representation, which is usually called a model, is built based on not only the current data but also prior knowledge on the object and the objective of the analysis. Akaike^2,3) showed that the log-likelihood can be considered as an estimate of the Kullback-Leibler (K-L) information which measures the similarity between the predictive distribution of the model and the true distribution. Akaike information criterion (AIC) is an estimate of the K-L information and makes it possible to evaluate and compare the goodness of many models objectively. In consequence, the minimum AIC procedure allows us to develop automatic modeling and signal extraction procedures. In this article, we give a simple explanation of statistical modeling based on the AIC and demonstrate four examples of applying the minimum AIC procedure to an automatic transaction of signals observed in the earth sciences. Genshiro, Kitagawa, Ph.D.: He is a Professor in the Department of Prediction and Control at the Institute of Statistical Mathematics. He is currently Deputy Director of the Institute of Statistical Mathematics and Professor of Statistical Science at the Graduate University for Advanced Study. He obtained his Ph.D. from the Kyushu University in 1983. His primary research interests are in time series analysis, non-Gaussian nonlinear filtering, and statistical modeling. He has published over 50 research papers. He was awarded the 2nd Japan Statistical Society Prize in 1997. Tomoyuki Higuchi, Ph.D.: He is an Associate Professor in the Department of Prediction and Control at the Institute of Statistical Mathematics. He is currently an Associate Professor of Statistical Science at the Graduate University for Advanced Study. He obtained his Ph.D. from the University of Tokyo in 1989. His research interests are in statistical modeling of space-time data, stochastic optimization techniques, and data mining. He has published over 30 research papers.     

The <Emphasis Type="Italic">B</Emphasis><Superscript><Emphasis Type="Italic">dual</Emphasis></Superscript>-Tree: indexing moving objects by space filling curves in the dual space

Existing spatiotemporal indexes suffer from either large update cost or poor query performance, except for the B ^x -tree (the state-of-the-art), which consists of multiple B ⁺-trees indexing the 1D values transformed from the (multi-dimensional) moving objects based on a space filling curve (Hilbert, in particular). This curve, however, does not consider object velocities, and as a result, query processing with a B ^x -tree retrieves a large number of false hits, which seriously compromises its efficiency. It is natural to wonder “can we obtain better performance by capturing also the velocity information, using a Hilbert curve of a higher dimensionality?”. This paper provides a positive answer by developing the B ^dual -tree, a novel spatiotemporal access method leveraging pure relational methodology. We show, with theoretical evidence, that the B ^dual -tree indeed outperforms the B ^x -tree in most circum- stances. Furthermore, our technique can effectively answer progressive spatiotemporal queries, which are poorly supported by B ^x -trees.     

Cooperation of categorical and behavioral learning in a practical solution to the abstraction problem

Real robots should be able to adapt autonomously to various environments in order to go on executing their tasks without breaking down. They achieve this by learning how to abstract only useful information from a huge amount of information in the environment while executing their tasks. This paper proposes a new architecture which performs categorical learning and behavioral learning in parallel with task execution. We call the architectureSituation Transition Network System (STNS). In categorical learning, it makes a flexible state representation and modifies it according to the results of behaviors. Behavioral learning is reinforcement learning on the state representation. Simulation results have shown that this architecture is able to learn efficiently and adapt to unexpected changes of the environment autonomously. Atsushi Ueno, Ph.D.: He is a research associate in the Artificial Intelligence Laboratory at the Graduate School of Information Science at the Nara Institute of Science and Technology (NAIST). He received the B.E., the M.E., and the Ph.D. degrees in aeronautics and astronautics from the University of Tokyo in 1991, 1993, and 1997 respectively. His research interest is robot learning and autonomous systems. He is a member of Japan Association for Artificial Intelligence (JSAI). Hideaki Takeda, Ph.D.: He is an associate professor in the Artificial Intelligence Laboratory at the Graduate School of Information Science at the Nara Institute of Science and Technology (NAIST). He received his Ph.D. in precision machinery engineering from the University of Tokyo in 1991. He has conducted research on a theory of intelligent computer-aided design systems, in particular experimental study and logical formalization of engineering design. He is also interested in multiagent architectures and ontologies for knowledge base systems.     

Application of a Recurrent Neural Network to Space Deversity in SDMA and CDMA Mobile Communication Systems

Linear and non-linear adaptive algorithms are investigated for Space Division Multiple Access (SDMA). SDMA is one of the emerging techniques for multiple access of users in mobile radio, which uses spatial distribution of users for their differentiation. The performance of the linear Square Root Kalman (SRK) algorithm for SDMA is compared to that of the non-linear Recurrent Neural Network (RNN) technique. The proposed SDMA-RNN technique is evaluated over Rician fading channels, and it shows improved Bit Error Rate (BER) performance in comparison with the linear SRK-based technique. The performance of SDMA-RNN is also compared with that of Code Division Multiple Access (CDMA) systems, showing that it could be used as a viable alternative scheme for multiple access of users. Finally, a Hybrid CDMA-SDMA system is proposed combining CDMA and SDMA-RNN systems. Hybrid CDMA-SDMA exhibits a very good potential for increase in the capacity and the performance of mobile communications systems.     

面向空间监视应用的空间目标数据库的建立

阐述了面向空间监视应用的空间目标数据库的建立技术与方法,并给出了它在空间监视的目标分类、识别应用中的样例。     

基于Google的个性化搜索系统的设计与实现

互联网用户使用网络获取信息过程中,搜索引擎已成为必不可少的工具。传统的WWW搜索引擎是“提问——搜索”方式．对于所有用户给出同样的关键宇得到的检索结果都是一样的。本文基于传统搜索引擎Google的基础上,实现了个性化的搜索。论文重点阐述了基于向量空间模型的个性化搜索系统的设计和实现过程。系统返回结果能够根据不同用户的兴趣爱好给出用户满意度较好的结果。     

DNA计算求解连续空间优化问题

首先构造了二进制编码的网络空间,其两个节点连接权的四条边对应到DNA编码,设计了相应的算子起到DNA计算酶的作用,该算法设计使得DNA计算能够求解连续空间优化问题。通过测试函数表明该算法具有较好的收敛速度和稳定性,求解结果非常好。     

中科院声学所知识创新工程项目基于内容分析的中文问答处理算法及系统实现*

提出了一种基于HNC自然语言理解框架下的中文问答处理算法,并在此算法基础上加以系统实现。试验证明,该系统在中等规模常识库基础上效果显著、准确率高。     

Web文本特征选择算法的研究

以向量空间模型作为Web文本的表示方法,结合Web文本的结构特征对向量空间模型中的特征选择算法进行了分析并加以改进。在改进的算法中,体现出了特征词在Web文档结构中的位置信息;引入了信息论中熵的概念,用词的熵函数对权值进行调整,从而更加准确地选取有效的特征词。实验验证了改进算法的可行性和有效性。