Pattern universes

In this essay we explore analogies between macroscopic patterns, which result from a sequence of phase transitions/instabilities starting from a homogeneous state, and similar phenomena in cosmology, where a sequence of phase transitions in the early universe is believed to have separated the fundamental forces from each other, and also shaped the structure and distribution of matter in the universe. We discuss three distinct aspects of this analogy: (i) Defects and topological charges in macroscopic patterns are analogous to spins and charges of quarks and leptons; (ii) Defects in generic 3+1 stripe patterns carry an energy density that accounts for phenomena that are currently attributed to dark matter; (iii) Space-time patterns of interacting nonlinear waves display behaviors reminiscent of quantum phenomena including inflation, entanglement and dark energy.     

A new family of proximity graphs: Class cover catch digraphs

Motivated by issues in machine learning and statistical pattern classification, we investigate a class cover problem (CCP) with an associated family of directed graphs—class cover catch digraphs (CCCDs). CCCDs are a special case of catch digraphs. Solving the underlying CCP is equivalent to finding a smallest cardinality dominating set for the associated CCCD, which in turn provides regularization for statistical pattern classification. Some relevant properties of CCCDs are studied and a characterization of a family of CCCDs is given.     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

Bit-parallel approximate string matching algorithms with transposition

Using bit-parallelism has resulted in fast and practical algorithms for approximate string matching under Levenshtein edit distance, which permits a single edit operation to insert, delete or substitute a character. Depending on the parameters of the search, currently the fastest non-filtering algorithms in practice are the O(km/wn) algorithm of Wu and Manber, the O((k+2)(m−k)/wn) algorithm of Baeza-Yates and Navarro, and the O(m/wn) algorithm of Myers, where m is the pattern length, n is the text length, k is the error threshold and w is the computer word size. In this paper we discuss a uniform way of modifying each of these algorithms to permit also a fourth type of edit operation: transposing two adjacent characters in the pattern. This type of edit distance is also known as Damerau edit distance. In the end we also present an experimental comparison of the resulting algorithms.     

匹配问题实例空间和解空间结构

本文通过研究匹配问题的实例空间，匈牙利算法和解空间三者之间的关系，指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的，而如何对问题的解空间进行合理的分解才能是问题的关键。     

Fold‐2‐covering triangular embeddings

For a graph G and a positive integer m, G_(m) is the graph obtained from G by replacing every vertex by an independent set of size m and every edge by m² edges joining all possible new pairs of ends. If G triangulates a surface, then it is easy to see from Euler's formula that G_(m) can, in principle, triangulate a surface. For m prime and at least 7, it has previously been shown that in fact G_(m) does triangulate a surface, and in fact does so as a “covering with folds” of the original triangulation. For m = 5, this would be a consequence of Tutte's 5‐Flow Conjecture. In this work, we investigate the case m = 2 and describe simple classes of triangulations G for which G₍₂₎ does have a triangulation that covers G “with folds,” as well as providing a simple infinite class of triangulations G of the sphere for which G₍₂₎ does not triangulate any surface. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 79–92, 2003     

Novel pattern formation in the collapse process of floating monolayer at the air-water interface

We have observed a remarkable two-armed spiral in the collapse process of a floating monolayer at the air-water interface by phase contrast microscopy. This demonstrates that the floating monolayer as a form of soft condensed matter reorganizes itself due to a certain kind of macroscopic or collective behavior of molecules as it collapses. This pattern formation is caused by the breakdown of a critical dynamical balance between the deformation of solid domain and the applied surface pressure. The fragility as well as the flexibility of the floating monolayer can be associated with the observed pattern growth. There are also observed interesting, periodically arranged collections of molecules in numerous collapsed regions. Received: 8 July 1997 / Accepted: 4 November 1997     

Neuro-fuzzy approach to processing inputs with missing values in pattern recognition problems

An approach to dealing with missing data, both during the design and normal operation of a neuro-fuzzy classifier is presented in this paper. Missing values are processed within a general fuzzy min–max neural network architecture utilising hyperbox fuzzy sets as input data cluster prototypes. An emphasis is put on ways of quantifying the uncertainty which missing data might have caused. This takes a form of classification procedure whose primary objective is the reduction of a number of viable alternatives rather than attempting to produce one winning class without supporting evidence. If required, the ways of selecting the most probable class among the viable alternatives found during the primary classification step, which are based on utilising the data frequency information, are also proposed. The reliability of the classification and the completeness of information is communicated by producing upper and lower classification membership values similar in essence to plausibility and belief measures to be found in the theory of evidence or possibility and necessity values to be found in the fuzzy sets theory. Similarities and differences between the proposed method and various fuzzy, neuro-fuzzy and probabilistic algorithms are also discussed. A number of simulation results for well-known data sets are provided in order to illustrate the properties and performance of the proposed approach.     

全固态多波长飞秒脉冲激光系统

利用棱镜对引进频谱空间啁啾来补偿飞秒脉冲激光二次谐波产生中的相位失配,提高了倍频效率建立了一套全固态、多波长(1065nm, 532nm,823.1nm, 402nm)飞秒脉冲激光系统自制的Nd:YVO4激光器输出532nm绿光激光,最高平均功率可达5.6W当用2.5W绿光激光泵浦时,从自制的钛宝石激光器及经BBO倍频可分别输出中心波长为823.1nm和402nm,平均功率300mW和73mW,谱宽32.3nm和5.1nm,脉宽22fs和33.3fs、重复率108MHz的近红外和蓝光激光整个系统具有结构紧凑、倍频效率高、运行稳定的特点.     

Enumeration of perfect matchings of a type of Cartesian products of graphs

Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by P_m and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let C_n denote the cycle with n vertices. Then Pm(C₄×T)=∏(2+α²), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C₄×T) is always a square or double a square.2. Let T be a tree. Then Pm(P₄×T)=∏(1+3α²+α⁴), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P₃×T)=∏(2+α²), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C₄×T)=[Pm(P₃×T)]².