Matching natural language patterns to graphical system models

We outline an approach to parsing based on system modelling. The underlying assumption, which determines the limits of the approach, is that a narrative natural language text constitutes a symbolic model of the system described, written for the purpose of communicating static and/or dynamic system aspects.     

Matching relational patterns in nucleic acid sequences

We describe a program that efficiently searches sequence data banks for complex patterns where sites are linked by common relations such as identity, complementarity or span. Its algorithm is closer to those of automatic demonstration than to the finite state machines used in fast pattern matching. The repertory of relations can be enriched at will without rewriting the core of the program. The program is written in Pascal-ISO and runs on a microcomputer.     

Similarity measures between strings extended to sets of strings

Similarity measures between strings (finite-length sequences of symbols) are extended to apply to sets of strings in an intuitive way which also preserves some of the desired properties of the initial similarity measure. Two quite different measures are used in the examples: the first for applications where numerical computation of pointwise similarity is needed; the second for applications which depend more heavily on substring similarity. It is presumed throughout that alphabets may be nondenumerable; in particular, the unit interval [0, 1] is used as the alphabet in the examples.     

Splitting-shooting methods for nonlinear transformations ofdigitized patterns

New splitting-shooting methods are presented for nonlinear transformations T: (ξ,η)→(x,y) where x=x(ξ,η), y=y(ξ,η). These transformations are important in computer vision, image processing, pattern recognition, and shape transformations in computer graphics. The methods can eliminate superfluous holes or blanks, leading to better images while requiring only modest computer storage and CPU time. The implementation of the proposed algorithms is simple and straightforward. Moreover, these methods can be extended to images with gray levels, to color images, and to three dimensions. They can also be implemented on parallel computers or VLSI circuits. A theoretical analysis proving the convergence of the algorithms and providing error bounds for the resulting images is presented. The complexity of the algorithms is linear. Graphical and numerical experiments are presented to verify the analytical results and to demonstrate the effectiveness of the methods     

Kinship verification in multi-linear coherent spaces

Multimedia Tools and Applications - Discovering kinship relations from face images in the wild has become an interesting and important problem in multimedia and computer vision. Despite the rapid...     

A generic approach to detect design patterns in model transformations using a string-matching algorithm

Software and Systems Modeling - Maintaining software artifacts is a complex and time-consuming task. Like any other program, model transformations are subject to maintenance. In a maintenance...     

Correct-by-construction synthesis of model transformations using transformation patterns

Model transformations are an essential part of model-based development approaches, such as Model-driven Architecture (MDA) and Model-driven Development (MDD). Model transformations are used to refine and abstract models, to re-express models in a new modelling language, and to analyse, refactor, compare and improve models. Therefore, the correctness of model transformations is critically important for successful application of model-based development: software developers should be able to rely upon the correct processing of their models by transformations in the same way that they rely upon compilers to produce correct executable versions of their programs. In this paper, we address this problem by defining standard structures for model transformation specifications and implementations, which serve as patterns and strategies for constructing a wide range of model transformations. These are incorporated into a tool-supported process which automatically synthesises implementations of model transformations from their specifications, these implementations are correct-by-construction with respect to their specifications.     

Matching of complex patterns by energy minimization

Two patterns are matched by putting one on top of the other and iteratively moving their individual parts until most of their corresponding parts are aligned. An energy function and a neighborhood of influence are defined for each iteration. Initially, a large neighborhood is used such that the movements result in global features being coarsely aligned. The neighborhood size is gradually reduced in successive iterations so that finer and finer details are aligned. Encouraging results have been obtained when applied to match complex Chinese characters. It has been observed that computation increases with the square of the number of moving parts which is quite favorable compared with other algorithms. The method was applied to the recognition of handwritten Chinese characters. After performing the iterative matching, a set of similarity measures are used to measure the similarity in topological features between the input and template characters. An overall recognition rate of 96.1% is achieved.     

Proving and applying program transformations expressed with second-order patterns

Summary We propose a program transformation method based on rewriting-rules composed of second-order schemas. A complete second-order matching algorithm is presented that allows effective use of these rules. We show how to formally prove the correctness of the rules using a denotational semantics for the programming language. We establish the correctness of the transformation method itself, and give techniques pertaining to its actual implementation. The paper is illustrated with recursion removal examples.A preliminary version of this paper appeared in the Proceedings of the International School of Theory and Application of Computers, ERICE (Sicily), May 1976     

MUPPIT: a method for using proper patterns in model transformations

Software and Systems Modeling - Model transformation plays an important role in developing software systems using the model-driven engineering paradigm. Examples of applications of model...     

On converting character strings to integers

Most programs which involve character to integer conversion fail to detect integer overflow correctly. This paper describes some of the pitfalls of not recognizing overflow, and presents a correct method for doing so in an arbitrary base for any precision.     

Using fuzzy logic to match strings in documents

This paper describes a new method that utilizes technology from soft computing to understand words after any OCR software system generated the proper database. First, the problem will be defined very precisely, and then, the algorithm for solving the problem of recognizing words will be presented. Finally, examples are provided to show how the algorithm is applied to recognize different types of words. © 2001 John Wiley & Sons, Inc.     

Ropes: An alternative to strings

Programming languages generally provide a ‘string’ or ‘text’ type to allow manipulation of sequences of characters. This type is usually of crucial importance, since it is normally mentioned in most interfaces between system components. We claim that the traditional implementations of strings, and often the supported functionality, are not well suited to such general-purpose use. They should be confined to applications with specific, and unusual, performance requirements. We present ‘ropes’ or ‘heavyweight’ strings as an alternative that, in our experience leads to systems that are more robust, both in functionality and in performance. Ropes have been in use in the Cedar environment almost since its inception, but this appears to be neither well-known, nor discussed in the literature. The algorithms have been gradually refined. We have also recently built a second similar, but somewhat lighter weight, C-language implementation, which is included in our publically released garbage collector distribution. We describe the algorithms used in both, and give some performance measurements for the C version.     

Implementing strings in Pascal

Sale¹ has proposed that strings be realized in Pascal using the existing sequence abstraction. This short note supports this proposal and shows how strings can be efficiently implemented in standard Pascal. The implementation is done in such a way as to leave existing programs undisturbed should strings be subsequently incorporated in the language and/or compiler.     

Weak repetitions in Sturmian strings

In this paper, we analyze the weak repetitions in Sturmian strings and show that an optimally efficient algorithm to compute the weak repetitions in Sturmian strings according to the output encodings defined in the literature is quadratic in the string length. Finally, we present an encoding that leads to a linear-time algorithm.     

Practical fast searching in strings

The problem of searching through text to find a specified substring is considered in a practical setting. It is discovered that a method developed by Boyer and Moore can outperform even special-purpose search instructions that may be built into the computer hardware. For very short substrings however, these special purpose instructions are fastest—provided that they are used in an optimal way.     

Finding approximate palindromes in strings

We introduce a novel definition of approximate palindromes in strings, and provide an algorithm to find all maximal approximate palindromes in a string with up to k errors. Our definition is based on the usual edit operations of approximate pattern matching, and the algorithm we give, for a string of size n on a fixed alphabet, runs in O(k²n) time. We also discuss two implementation-related improvements to the algorithm, and demonstrate their efficacy in practice by means of both experiments and an average-case analysis.     

Generalized approximate regularities in strings

We concentrate on generalized string regularities and study the minimum approximate λ-cover problem and the minimum approximate λ-seed problem of a string. Given a string x of length n and an integer λ, the minimum approximate λ-cover (respectively, seed) problem is to find a set of λ substrings each of equal length that covers x (respectively, a superstring of x) with the minimum error, under a variety of distance models containing the Hamming distance, the edit distance and the weighted edit distance. Both problems can be solved in polynomial time.