Realization and synthesis of reversible functions

Reversible circuits play an important role in quantum computing. This paper studies the realization problem of reversible circuits. For any n-bit reversible function, we present a constructive synthesis algorithm. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N≤2ⁿ, and the other (2ⁿ−N) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2n⋅N ‘(n−1)’-CNOT gates and 4n²⋅N NOT gates. The time and space complexities of the algorithm are Ω(n⋅4ⁿ) and Ω(n⋅2ⁿ), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms.     

一类并发实时系统的自动验证

一个被广泛用于验证实时系统的方法是根据被验证的实时性质,使用适当的双向模拟等价关系使无限的状态空间转化为有限的状态等价类空间.算法只需要在这个有限的等价类空间里搜索就可以得到正确答案.但是,这个等价类空间的规模一般随着系统规模的增大而产生爆炸性的增长,以至于在很多情况下,穷尽搜索这个空间是不现实的.该文引入了一个等价关系来验证一个由多个实时自动机通过共享变量组成的并发系统是否满足一个线性时段特性.同时,还引入了格局之间的兼容关系来避免对状态等价类空间的穷尽搜索.基于这两个关系,文章提出了一个算法来验证是否一个实时自动机网满足一个线性时段特性.实例研究显示,此算法在某些情况下比其他一些工具有更好的时间和空间效率.     

Convergence analysis of convex incremental neural networks

Recently, a convex incremental algorithm (CI-ELM) has been proposed in Huang and Chen (Neurocomputing 70:3056–3062, 2007), which randomly chooses hidden neurons and then analytically determines the output weights connecting with the hidden layer and the output layer. Though hidden neurons are generated randomly, the network constructed by CI-ELM is still based on the principle of universal approximation. The random approximation theory breaks through the limitation of most conventional theories, eliminating the need for tuning hidden neurons. However, due to the random characteristic, some of the neurons contribute little to decrease the residual error, which eventually increase the complexity and computation of neural networks. Thus, CI-ELM cannot precisely give out its convergence rate. Based on Lee’s results (Lee et al., IEEE Trans Inf Theory 42(6):2118–2132, 1996), we first show the convergence rate of a maximum CI-ELM, and then systematically analyze the convergence rate of an enhanced CI-ELM. Different from CI-ELM, the hidden neurons of the two algorithms are chosen by following the maximum or optimality principle under the same structure as CI-ELM. Further, the proof process also demonstrates that our algorithms achieve smaller residual errors than CI-ELM. Since the proposed neural networks remove these “useless” neurons, they improve the efficiency of neural networks. The experimental results on benchmark regression problems will support our conclusions. The work is under the funding of Singapore MOE AcRF Tier 1 grant WBS No: R 252-000-221-112.     

Efficient Phrase-Based Document Similarity for Clustering

In this paper, we propose a phrase-based document similarity to compute the pair-wise similarities of documents based on the Suffix Tree Document (STD) model. By mapping each node in the suffix tree of STD model into a unique feature term in the Vector Space Document (VSD) model, the phrase-based document similarity naturally inherits the term tf-idf weighting scheme in computing the document similarity with phrases. We apply the phrase-based document similarity to the group-average Hierarchical Agglomerative Clustering (HAC) algorithm and develop a new document clustering approach. Our evaluation experiments indicate that, the new clustering approach is very effective on clustering the documents of two standard document benchmark corpora OHSUMED and RCV1. The quality of the clustering results significantly surpass the results of traditional single-word textit{tf-idf} similarity measure in the same HAC algorithm, especially in large document data sets. Furthermore, by studying the property of STD model, we conclude that the feature vector of phrase terms in the STD model can be considered as an expanded feature vector of the traditional single-word terms in the VSD model. This conclusion sufficiently explains why the phrase-based document similarity works much better than the single-word tf-idf similarity measure.     

Medical displays by using plasma‐beam‐alignment technology

Abstract— Novel anode layer plasma within minimum chamber space was developed for non‐contact alignment process. The plasma‐treated polyimide (PI) surface showed no particle contamination and no micro‐scratches. Surface morphology was investigated by using scanning electron microscope (SEM), an atomic force microscope (AFM), and X‐ray photoemission spectroscopy. The different oxygen‐to‐carbon ratio ([O]/[C] ratio) for XPS spectra indicated a composition change after plasma treatment. Surface pretilt angles were varied from 0 to 2.1° under different plasma exposure times. Finally, a prototype 20.8‐in. QXGA IPS‐mode gray‐scale medical liquid‐crystal display was successfully demonstrated with high contrast ratio, excellent uniformity, and wide viewing angle using this new plasma‐beam‐alignment technique.     

Surface treatment,reflectance, and age effects on electronic‐paper reading performance

Abstract— This study is intended to explore the legibility and visual fatigue of different age users under various surface treatments and reflectance of electronic paper. Through the method of character‐search task, the results indicated that compared with single types of treatment [anti‐reflection (AR) 0.8%, anti‐glare, 43% haze), the compound treatment of anti‐reflection and anti‐glare (ARC) exhibited the same legibility, and it showed superior properties to effectively reduce visual fatigue. Hence, it is suggested that electronic‐paper manufacturers should choose the compound surface treatment for better visual performance. On the other hand, the findings also validated that enhancing the reflectance of electronic paper to the same level as regular paper (about 80%) is worthy to be practically implemented. Based on the results of this study, electronic‐paper manufacturers can take useful information to fulfill ergonomic requirements on product design.     

Ergonomic evaluation of electronic paper: Influences of anti‐reflection surface treatment,illumination, and curvature on legibility and visual fatigue

Abstract— The intent of this study is to investigate some critical factors that affect legibility and visual fatigue while reading on an electronic‐paper display in terms of ergonomics. Anti‐reflection surface treatment, ambient illumination, and bending curvature are taken into account to evaluate their effects by using the method of letter‐search task. The results showed that the surface treatment with high degrees of anti‐reflection significantly improved the legibility and reduces visual fatigue. Thus, electronic‐paper manufacturers may choose a much better surface treatment in order to meet ergonomic demand. In addition, the findings in the present study also indicate that subjects reported less visual fatigue on a bending surface of a visual display unit, in comparison with a plane surface. It is proven that these ergonomic evaluations for electronic paper provide manufactures with useful information to design suitable products for users.     

Leveraging online communities in fostering adaptive schools

There has long been a call for schools to prepare students for the twenty-first century where skills and dispositions differ significantly from much of what has historically characterized formal education. The knowledge based economy calls for policy and pedagogical efforts that would transform schools. Schools are to foster communities of learners. This paper suggests that para-communities may be points of leverage in the fostering of adaptive schools. A critical analysis is done on the differences between para-communities (such as online communities) and schools; and an argument is made that they each serve differing goals and should be left distinct because they achieve different societal and economic demands.     

Unimodality,Independence Lead to NP-Hardness of Interval Probability Problems

In many real-life situations, we only have partial information about probabilities. This information is usually described by bounds on moments, on probabilities of certain events, etc. –i.e., by characteristics c(p) which are linear in terms of the unknown probabilities p _j. If we know interval bounds on some such characteristics , and we are interested in a characteristic c(p), then we can find the bounds on c(p) by solving a linear programming problem. In some situations, we also have additional conditions on the probability distribution –e.g., we may know that the two variables x ₁ and x ₂ are independent, or that the joint distribution of x ₁ and x ₂ is unimodal. We show that adding each of these conditions makes the corresponding interval probability problem NP-hard.