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.     

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     

Indexing text using the Ziv–Lempel trie

Let a text of u characters over an alphabet of size σ be compressible to n phrases by the LZ78 algorithm. We show how to build a data structure based on the Ziv–Lempel trie, called the LZ-index, that takes 4nlog₂n(1+o(1)) bits of space (that is, 4 times the entropy of the text for ergodic sources) and reports the R occurrences of a pattern of length m in worst case time O(m³logσ+(m+R)logn). We present a practical implementation of the LZ-index, which is faster than current alternatives when we take into consideration the time to report the positions or text contexts of the occurrences found.     

Practical algorithms for transposition-invariant string-matching

We consider the problems of (1) longest common subsequence (LCS) of two given strings in the case where the first may be shifted by some constant (that is, transposed) to match the second, and (2) transposition-invariant text searching using indel distance. These problems have applications in music comparison and retrieval. We introduce two novel techniques to solve these problems efficiently. The first is based on the branch and bound method, the second on bit-parallelism. Our branch and bound algorithm computes the longest common transposition-invariant subsequence (LCTS) in time O((m²+loglogσ)logσ) in the best case and O((m²+logσ)σ) in the worst case, where m and σ, respectively, are the length of the strings and the size of the alphabet. On the other hand, we show that the same problem can be solved by using bit-parallelism and thus obtain a speedup of O(w/logm) over the classical algorithms, where the computer word has w bits. The advantage of this latter algorithm over the present bit-parallel ones is that it allows the use of more complex distances, including general integer weights. Since our branch and bound method is very flexible, it can be further improved by combining it with other efficient algorithms such as our novel bit-parallel algorithm. We experiment on several combination possibilities and discuss which are the best settings for each of those combinations. Our algorithms are easily extended to other musically relevant cases, such as δ-matching and polyphony (where there are several parallel texts to be considered). We also show how our bit-parallel algorithm is adapted to text searching and illustrate its effectiveness in complex cases where the only known competing method is the use of brute force.     

Pattern Search Method for Discrete <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>–Approximation

We propose a pattern search method to solve a classical nonsmooth optimization problem. In a deep analogy with pattern search methods for linear constrained optimization, the set of search directions at each iteration is defined in such a way that it conforms to the local geometry of the set of points of nondifferentiability near the current iterate. This is crucial to ensure convergence. The approach presented here can be extended to wider classes of nonsmooth optimization problems. Numerical experiments seem to be encouraging. This work was supported by M.U.R.S.T., Rome, Italy.     

单循环赛赛程安排的一个图论方法

利用图论的边着色理论建立了一个赛程安排的数学模型 .首先建立 n支球队与完全图 Kn的 n个顶点间的一一对应 ,把球队 Ai和 Aj间的比赛关系抽象成 Kn的顶点 i和 j间的边 ( i,j) .然后分别构造出了图K2 m- 1和 K2 m的正常 2 m-1边着色 .从而给出了各球队每两场比赛间得到的休整时间最均等 ,休整的间隔场次数达到上限值 n2 的一个赛程安排方案