Breaking the data encryption standard using networks of evolutionary processors with parallel string rewriting rules

In this paper we introduce a biologically inspired distributed computing model called networks of evolutionary processors with parallel string rewriting rules (NEPPS), which is a variation of the hybrid networks of evolutionary processors introduced by Martin-Vide et al. Such a network contains simple processors that are located in the nodes of a virtual graph. Each processor has strings (each string having multiple copies) and string rewriting rules. The rules are applied parallely on the strings. After the strings have been rewritten, they are communicated among the processors through filters. We show that we can theoretically break the DES (data encryption standard), which is the most widely used cryptosystem, using NEPPS. We prove that, given an arbitrary <plain-text, cipher-text> pair, one can recover the DES key in a constant number of steps.     

Fast approximate string matching

Approximate string matching is an important operation in information systems because an input string is often an inexact match to the strings already stored. Commonly known accurate methods are computationally expensive as they compare the input string to every entry in the stored dictionary. This paper describes a two-stage process. The first uses a very compact n-gram table to preselect sets of roughly similar strings. The second stage compares these with the input string using an accurate method to give an accurately matched set of strings. A new similarity measure based on the Levenshtein metric is defined for this comparison. The resulting method is both computationally fast and storage-efficient.     

基于DNA下推自动机二进制减法和乘法的实现

提出了基于DNA下推自动机二进制减法和乘法的实现方法.一位二进制借位减法,是通过预先构造好的DNA下推自动机模型在一个试管中以该模型的运行方式自动完成运算.m位二进制借位减法,是在一位二进制减法的基础上,按照从低位到高位的顺序,将低位产生的借位作为高位试管操作巾的输入符号串,从而完成高位的减法运算.两位二进制乘法中包含移位和加法操作,在两个试管中分别设计好DNA下推自动机模型,分别完成被乘数与乘数各位的移位操作,同时结合相应的生物操作,将其作为另一个试管加法操作中的输入符号串,则加法操作中产牛的结果即为所求.在此基础上,m位二进制乘法可通过移位操作的并行性和加法操作的串行性来完成运算.这些实现方法为DNA下推自动机实现基本的算术运算提供了比较完整的运算机制.     

Chemical Genetic Programming – evolutionary optimization of the genotype-to-phenotype translation set

A new method of genetic programming, named chemical genetic programming (CGP), which enables evolutionary optimization of the mapping from genotypic strings to phenotypic trees is proposed. A cell is evolved which includes a DNA string that codes the fundamental mapping from the DNA code to computational functionality. Genetic modification of a cell's DNA allows the DNA code and the genotype-to-phenotype translation to coevolve. Building an optimal translation table enhances evolution within a population while maintaining the necessary diversity to explore the entire search space. This work was presented in part at the 9th International Symposium on Artificial Life and Robotics, Oita, Japan, January 28–30, 2004     

Automated String Constraints Solving for Programs Containing String Manipulation Functions

The ability to solve various constraints is a principal factor of automatic constraint solvers. Most object-oriented languages treat a character string as a primitive data type which is manipulated by string library functions. Most constraint solvers have limitations on their input constraints, such as strong restrictions on the expressiveness of constraints or lack of the ability to solve hybrid constraints. These limitations hinder applying automated constraint solvers on program analysis techniques for programs containing strings and string manipulation functions. We propose an approach to automatically solve program constraints involving strings and string manipulation functions. Based on the character array model, we design a constraint language which contains primitive operations to precisely describe the constraints of commonly used string manipulation functions. The translated string constraints together with numeric constraints are then solved by a two-phase test generation procedure: firstly, a partial solution is obtained to satisfy the arithmetic constraints of the position variables, and the solution is utilized to simplify the string constraints into pure character array constraints; secondly, the pure array constraints are solved by an off-the-shelf array-specific theory based constraint solver. We integrate the approach into an automated testing tool to support the generation of string test cases, and then perform experiments. The results of the experiments prove that the integration of the proposed approach promotes the testing coverage of the existing testing tool, and the integrated tool has an advantage of handling specific string manipulation functions compared with an existing string solver.     

The preservation of favored building blocks in the struggle for fitness: the puzzle algorithm

The shortest common superstring (SCS) problem, known to be NP-complete, seeks the shortest string that contains all strings from a given set. In this paper, we present a novel coevolutionary algorithm-the Puzzle Algorithm-where a population of building blocks coevolves alongside a population of solutions. We show experimentally that our novel algorithm outperforms a standard genetic algorithm (GA) and a benchmark greedy algorithm on instances of the SCS problem inspired by deoxyribonucleic acid (DNA) sequencing. We next compare our previously presented cooperative coevolutionary algorithm with the Co-Puzzle Algorithm-the puzzle algorithm coupled with cooperative coevolution-showing that the latter proves to be top gun. Finally, we discuss the benefits of using our puzzle approach in the general field of evolutionary algorithms.     

CASM: a VLSI chip for approximate string matching

The edit distance between two strings a1, ..., a_m and b ₁, ..., b_n is the minimum cost s of a sequence of editing operations (insertions, deletions and substitutions) that convert one string into the other. This paper describes the design and implementation of a linear systolic array chip for computing the edit distance between two strings over a given alphabet. An encoding scheme is proposed which reduces the number of bits required to represent a state in the computation. The architecture is a parallel realization of the standard dynamic programming algorithm proposed by Wagner and Fischer (1974), and can perform approximate string matching for variable edit costs. More importantly, the architecture does not place any constraint on the lengths of the strings that can be compared. It makes use of simple basic cells and requires regular nearest neighbor communication, which makes it suitable for VLSI implementation. A prototype of this array has been built at the University of South Florida     

String-matching with OBDDs

Ordered binary decision diagrams (OBDDs) are a very popular graph representation for Boolean functions. They can be viewed as finite automata recognizing sets of strings of a fixed length, where the letters of the input strings are read at most once in a predefined ordering. The string matching problem with string w as pattern, consists of determining, given an input string, whether or not it contains w as substring. We show that for a fraction of orderings tending to 1 when n increases arbitrarily, the minimal size of an OBDD solving the string matching problem for strings of length n has a growth which is an exponential in n.     

基于基本操作序列的编辑距离顺序验证

两字符串的编辑距离是从一个串转换到另一个串所需要的最少基本操作数。编辑距离广泛应用于字符串近似匹配、字符串相似连接等领域。动态规划法利用编辑距离矩阵来计算两个串的编辑距离,需要计算矩阵中的所有元素,时间效率低。改进的方法改变了矩阵中元素的计算次序,减少了需要比对的元素,但仍需要比对一半以上的元素,时间效率还有待提高。提出基于基本操作序列的编辑距离顺序验证方法。首先,分析了基本操作序列的可列性,给出了列举基本操作序列的方法。然后依次顺序验证基本操作数从小到大的基本操作序列直到某一序列通过验证,得到其编辑距离。在阈值为2的字符串近似搜索实验中发现,所提方法比动态规划类方法具有更高的效率。     

An approach to designing very fast approximate string matchingalgorithms

An approach to designing very fast algorithms for approximate string matching in a dictionary is proposed. Multiple spelling errors corresponding to insert, delete, change, and transpose operations on character strings are considered in the fault model. The design of very fast approximate string matching algorithms through a four-step reduction procedure is described. The final and most effective step uses hashing techniques to avoid comparing the given word with words at large distances. The technique has been applied to a library book catalog textbase. The experiments show that performing approximate string matching for a large dictionary in real-time on an ordinary sequential computer under our multiple fault model is feasible     

汉字／字符串编辑距离和编辑路径的有效求解技术

本文提出了一种有效的编辑距离和编辑路径求解技术，该技术不但适合于单字符字符串而且也适合于双字节汉字串的编辑距离和编辑路径的计算。它首先通过一有效的字符串相似匹配算法计算出串编辑距离，而后通过简单的二进制字位运算正确计算出串（最短）编辑路径。文章也给出了本技术的完整实现算法并分析了算法的复杂性。     

An algorithm for matching run-length coded strings

An algorithm for the computation of the edit distance of run-length coded strings is given. In run-length coding, not all individual symbols in a string are explicitly listed. Instead, one run of identical consecutive symbols is coded by giving one representative symbol together with its multiplicity. The algorithm determines the minimum cost sequence of edit operations transforming one string into another. In the worst case, the algorithm has a time complexity ofO(n·m), wheren andm give the lengths of the strings to be compared. In the best case, the time complexity isO(k·l), wherek andl are the numbers of runs of identical symbols in the two strings under comparison.     

中文日期词的分割与识别

非限定性手写汉字串的分割与识别是当前字符识别领域中的一个难点问题.针对手写日期的特点,提出了整词识别和定长汉字串分割识别相结合的组合识别方法.整词识别将字符串作为一个整体进行识别,无需复杂的字符串分割过程.在定长汉字串分割过程中,首先通过识别来预测汉字串的长度,然后通过投影和轮廓分析确定候选分割线,最后通过识别选取最优分割路径.这两种分割识别方法通过规则进行组合,大大提高了系统的性能.在真实票据图像上的实验表明了该方法的有效性,分割识别正确率达到了93.3%.     

Context free languages in biological systems

A set of definitions is proposed which places a dynamic model of growth and stabilization in biological systems in a formal language framework. The language of stable adult strings achievable in a system without cellular interactions is studied. It is shown that o if every string is considered to be a possible initial string in development, then the class of languages defined is properly included in the class of regular languages. However if, as is biologically reasonable, development can only start from strings drawn from a finite initial set, then the class of languages defined is exactly the class of context free languages.     

Termination Proofs for String Rewriting Systems via Inverse Match-Bounds

Annotating a letter by a number, one can record information about its history during a rewrite derivation. In each rewrite step, numbers in the reduct are updated depending on the redex numbering. A string rewriting system is called match-bounded if there is a global upper bound to these numbers. Match-boundedness is known to be a strong sufficient criterion for both termination and preservation of regular languages. We show that the string rewriting systems whose inverse (left and right hand sides exchanged) is match-bounded, also have exceptional properties, but slightly different ones. Inverse match-bounded systems need not terminate; they effectively preserve context-free languages; their sets of normalizable strings and their sets of immortal strings are effectively regular. These languages can be used to decide the normalization, the uniform normalization, the termination and the uniform termination problem for inverse match-bounded systems. We also prove that the termination problem is decidable in linear time, and that a certain strong reachability problem is decidable, thereby solving two open problems of McNaughton’s. Like match-bounds, inverse match-bounds entail linear derivational complexity on the set of terminating strings.     

基于有序二叉树的快速多模式字符串匹配算法

将有序二叉树和QS算法相结合,提出一种快速多模式字符串匹配算法,实现在多模式匹配过程中不匹配字符的连续跳跃。为提高匹配速度,利用已匹配的字符串信息进行跳跃式的比较,避免文本扫描指针的回溯。实验结果表明,与SMA算法相比,该算法在预处理阶段构造速度和匹配速度更快,在模式串较长的情况下,性能更优越。     

Deformed fuzzy automata for correcting imperfect strings of fuzzy symbols

Presents a fuzzy method for the recognition of strings of fuzzy symbols containing substitution, deletion, and insertion errors. As a preliminary step, we propose a fuzzy automaton to calculate a similarity value between strings. The adequate selection of fuzzy operations for computing the transitions of the fuzzy automaton allows us to obtain different string similarity definitions (including the Levenshtein distance). A deformed fuzzy automaton based on this fuzzy automaton is then introduced in order to handle strings of fuzzy symbols. The deformed fuzzy automaton enables the classification of such strings having an undetermined number of insertion, deletion and substitution errors. The selection of the parameters determining the deformed fuzzy automaton behavior would allow to implement recognizers adapted to different problems. The paper also presents algorithms that implement the deformed fuzzy automaton. Experimental results show good performance in correcting these kinds of errors.     

A model-based connected-digit recognition system using either hidden Markov models or templates

Although a great deal of effort has gone into studying large-vocabulary speech-recognition problems, there remains a number of interesting, and potentially exceedingly important, problems which do not require the complexity of these large systems. One such problem is connected-digit recognition, which has applications to telecommunications, order entry, credit-card entry, forms automation, and data-base management, among others. Connected-digit recognition is also an interesting problem for another reason, namely that it is one in which whole-word training patterns are applicable as the basic speech-recognition unit. Thus one can bring to bear all the fundamental speech recognition technology associated with whole-word recognition to solve this problem. As such, several connected digit recognizers have been proposed in the past few years. The performance of these systems has steadily improved to the point where high digit-recognition accuracy is achievable in a speaker-trained mode.In this paper we present a unified system for automatically recognizing fluently spoken digit strings based on whole-word reference units. The system that we will describe can use either hidden Markov model (HMM) technology or template-based technology. In fact the overall system contains features from both approaches.A key factor in the success of the various connected digit recognizers is the ability to derive, via a training procedure, a good set of representations of the behavior of the individual digits in actual connected digit strings. For most applications, isolated digit training does not provide a good enough characterization of the variability of the digits in strings. The “best” training procedure is to derive the digit reference patterns (either templates or statistical models) from connected digit strings. Such a connected word training procedure, based on a segmental k-means loop, has been proposed and was tested on seven experienced users of speech recognizers. For these seven talkers, average string accuracies of greater than 98% for unknown length strings, and greater than 99% for known length strings were obtained on an independent test set of 525 variable length strings (1–7 digits) recorded over local dialed-up telephone lines.To evaluate the performance of the overall connected digit recognizer under more difficult conditions, a set of 50 people (25 men, 25 women), from the non-technical local population, was each asked to record 1200 random digit strings over local dialed-up telephone lines. Both a speaker-trained and a multi-speaker training set was created, and a full performance evaluation was made. Results show that the average string accuracy for unknown- and known-length strings, in the speaker-trained mode, was 98% and 99% respectively; in the multi-speaker mode the average string accuracies were 94% and 96.6% respectively. A complete analysis of these results is given in this paper.     

Classes of cost functions for string edit distance

Finding a sequence of edit operations that transforms one string of symbols into another with the minimum cost is a well-known problem. The minimum cost, or edit distance, is a widely used measure of the similarity of two strings. An important parameter of this problem is the cost function, which specifies the cost of each insertion, deletion, and substitution. We show that cost functions having the same ratio of the sum of the insertion and deletion costs divided by the substitution cost yield the same minimum cost sequences of edit operations. This leads to a partitioning of the universe of cost functions into equivalence classes. Also, we show the relationship between a particular set of cost functions and the longest common subsequence of the input strings. This work was supported in part by the U.S. Department of Defense and the U.S. Department of Energy.     

Modeling concurrency with partial orders

Concurrency has been expressed variously in terms of formal languages (typically via the shuffle operator), partial orders, and temporal logic,inter alia. In this paper we extract from these three approaches a single hybrid approach having a rich language that mixes algebra and logic and having a natural class of models of concurrent processes. The heart of the approach is a notion of partial string derived from the view of a string as a linearly ordered multiset by relaxing the linearity constraint, thereby permitting partially ordered multisets orpomsets. Just as sets of strings form languages, so do sets of pomsets form processes. We introduce a number of operations useful for specifying concurrent processes and demonstrate their utility on some basic examples. Although none of the operations is particularly oriented to nets it is nevertheless possible to use them to express processes constructed as a net of subprocesses, and more generally as a system consisting of components. The general benefits of the approach are that it is conceptually straightforward, involves fewer artificial constructs than many competing models of concurrency, yet is applicable to a considerably wider range of types of systems, including systems with buses and ethernets, analog systems, and real-time systems.Revision of Some Constructions for Order-Theoretic Models of Concurrency [Ref. 1].