Nominal rewriting

Nominal rewriting is based on the observation that if we add support for α-equivalence to first-order syntax using the nominal-set approach, then systems with binding, including higher-order reduction schemes such as λ-calculus beta-reduction, can be smoothly represented. Nominal rewriting maintains a strict distinction between variables of the object-language (atoms) and of the meta-language (variables or unknowns). Atoms may be bound by a special abstraction operation, but variables cannot be bound, giving the framework a pronounced first-order character, since substitution of terms for variables is not capture-avoiding. We show how good properties of first-order rewriting survive the extension, by giving an efficient rewriting algorithm, a critical pair lemma, and a confluence theorem for orthogonal systems.     

Encoding Abstract Syntax Without Fresh Names

This paper introduces a variant of nominal abstract syntax in which bindable names are represented by normal meta-variables as opposed to a separate class of globally fresh names. Distinct meta-variables can be instantiated with the same concrete name, which we call aliasing. The possible aliasing patterns are controlled by explicit constraints on the distinctness (freshness) of names. This approach has already been used in the nominal meta-programming language ??ML. We recap that language and develop a theory of contextual equivalence for it. The central result of the paper is that abstract syntax trees (ASTs) involving binders can be encoded into ??ML in such a way that ??-equivalence of ASTs corresponds with contextual equivalence of their encodings. This is novel because the encoding does not rely on the existence of globally fresh names and fresh name generation, which are fundamental to the correctness of the pre-existing encoding of abstract syntax into FreshML.     

Implementing Nominal Unification

Nominal matching and unification underly the dynamics of nominal rewriting. Urban, Pitts and Gabbay gave a nominal unification algorithm which finds the most general solution to a nominal matching or unification problem, if one exists. Later the algorithm was extended by Fernández and Gabbay to deal with name generation and locality.In this paper we describe first a direct implementation of the nominal unification algorithm, including the extensions, in Maude. This implementation is not efficient (it is exponential in time), but we will show that we can obtain a feasible implementation by using termgraphs.     

Fresh O'Caml: Nominal Abstract Syntax for the Masses

Nominal abstract syntax, as pioneered by the 'FreshML' series of metalanguages, provides first-order tools for the representation and manipulation of syntax involving bound names, binding operations and α-equivalence. Fresh O'Caml fuses nominal abstract syntax with the full Objective Caml language to yield a functional programming language with powerful facilities for representing and manipulating syntax. In this paper, we first provide an examples-driven overview of the language and its functionality. Then we proceed to comment on some of the difficult issues involved in implementing nominal abstract syntax and explain how they have been addressed in the latest version of the compiler.     

Hierarchical Nominal Terms and Their Theory of Rewriting

Nominal rewriting introduced a novel method of specifying rewriting on syntax-with-binding. We extend this treatment of rewriting with hierarchy of variables representing increasingly 'meta-level' variables, e.g. in hierarchical nominal term rewriting the meta-level unknowns (representing unknown terms) in a rewrite rule can be 'folded into' the syntax itself (and rewritten). To the extent that rewriting is a mathematical meta-framework for logic and computation, and nominal rewriting is a framework with native support for binders, hierarchical nominal term rewriting is a meta-to-the-omega level framework for logic and computation with binders.     

Nominal logic, a first order theory of names and binding

This paper formalises within first-order logic some common practices in computer science to do with representing and reasoning about syntactical structures involving lexically scoped binding constructs. It introduces Nominal Logic, a version of first-order many-sorted logic with equality containing primitives for renaming via name-swapping, for freshness of names, and for name-binding. Its axioms express properties of these constructs satisfied by the FM-sets model of syntax involving binding, which was recently introduced by the author and M.J. Gabbay and makes use of the Fraenkel–Mostowski permutation model of set theory. Nominal Logic serves as a vehicle for making two general points. First, name-swapping has much nicer logical properties than more general, non-bijective forms of renaming while at the same time providing a sufficient foundation for a theory of structural induction/recursion for syntax modulo α-equivalence. Secondly, it is useful for the practice of operational semantics to make explicit the equivariance property of assertions about syntax – namely that their validity is invariant under name-swapping.     

基于Vague等价关系的粗糙集分解

首先,提出了基于Vague等价关系的（α_t,α_f）-等价类,并在（α_t,α_f）-等价类基础上定义了（α_t,α_f）-粗糙集,得到（α_t,α_f）-粗糙集是λ-粗糙集的推广,研究了（α_t,α_f）-等价类和（α_t,α_f）-粗糙集的性质。其次,给出（α_t,α_f）-等价类分解、（α_t,α_f）-粗糙集分解以及（α_t,α_f）-粗糙集的边界的概念。最后,分别得到等价类、粗糙集以及粗糙集的边界基于Vague等价关系的分解结构。     

Equivariant Unification

Nominal logic is a variant of first-order logic with special facilities for reasoning about names and binding based on the underlying concepts of swapping and freshness. It serves as the basis of logic programming, term rewriting, and automated theorem proving techniques that support reasoning about languages with name-binding. These applications often require nominal unification, or equational reasoning and constraint solving in nominal logic. Urban, Pitts and Gabbay developed an algorithm for a broadly applicable class of nominal unification problems. However, because of nominal logic’s equivariance property, these applications also require a different form of unification, which we call equivariant unification. In this article, we first study the complexity of the decision problem for equivariant unification and equivariant matching. We show that these problems are NP-hard in general, as is nominal unification without the ground-name restrictions employed in previous work on nominal unification. Moreover, we present an exponential-time algorithm for equivariant unification that can be used to decide satisfiability, or produce a complete finite set of solutions. We also study special cases that can be solved efficiently. In particular, we present a polynomial time algorithm for swapping-free equivariant matching, that is, for matching problems in which the swapping operation does not appear.     

Signatures versus histograms: Definitions, distances and algorithms

The aim of this paper is to present a new method to compare histograms. The main advantage is that there is an important time-complexity reduction with respect to the methods presented before. This reduction is statistically and analytically demonstrated in the paper.The distances between histograms that we presented are defined on a structure called signature, which is a lossless representation of histograms. Moreover, the type of the elements of the sets that the histograms represent are ordinal, nominal and modulo.We show that the computational cost of these distances is O(z^′) for the ordinal and nominal types and O(z^′2) for the modulo one, z^′ being the number of non-empty bins of the histograms. The computational cost of the algorithms presented in the literature depends on the number of bins of the histograms. In most of the applications, the obtained histograms are sparse; then considering only the non-empty bins drastically decreases the time consumption of the comparison.The distances and algorithms presented in this paper are experimentally validated on the comparison of images obtained from public databases and positioning of mobile robots through the recognition of indoor scenes (captured in a learning stage).     

Algorithms and reductions for rewriting problems. II

In this paper we give polynomial-time reductions between a version of joinability for rewrite systems and the word problem for rewrite systems. We prove log-space hardness or completeness for P for several problems of ground rewrite systems. We show that matching (and unification) modulo ground equations is NP-hard even when variables are restricted to at most two occurrences in the pattern and the subject is just a constant. Finally, we give the first polynomial-time algorithms for matching modulo ground equations with linear pattern and for joinability problem with ground rewrite systems. The joinability result leads to polynomial time algorithms for: local confluence of ground rewrite systems, confluence of terminating ground rewrite systems, and completeness of ground rewrite systems. The results for matching modulo ground equations are optimal with respect to occurrences of variables.     

Shape modeling and matching in identifying 3D protein structures

In this paper, we describe a novel geometric approach in the process of recovering 3D protein structures from scalar volumes. The input to our method is a sequence of α-helices that make up a protein, and a low-resolution protein density volume where possible locations of α-helices have been detected. Our task is to identify the correspondence between the two sets of helices, which will shed light on how the protein folds in space. The central theme of our approach is to cast the correspondence problem as that of shape matching between the 3D volume and the 1D sequence. We model both shapes as attributed relational graphs, and formulate a constrained inexact graph matching problem. To compute the matching, we developed an optimal algorithm based on the A*-search with several choices of heuristic functions. As demonstrated in a suite of synthetic and authentic inputs, the shape-modeling approach is capable of identifying helix correspondences in noise-abundant volumes at high accuracy with minimal or no user intervention.     

Model reduction and controller synthesis in the presence of parameter uncertainty

COVariance Equivalent Realizations COVERs have been used recently to obtain reduced models that match a specified number of output covariances and Markov parameters of the original model. This paper extends this theory to models with uncertain parameters. The approach is to take an nth order nominal system with h uncertain parameters, form its (n + nh) order sensitivity model, then reduce the sensitivity model to size (n + γk), where k is the number of outputs and γ is an integer chosen by the designer. The reduced-order model then matches (γ + 1) output covariances and γ Markov parameters of the original sensitivity system. This method leaves the nominal system unchanged, and hence (1) retains all dynamical information of the nominal system, (2) maintains the correct cross-correlation between nominal outputs and sensitivity outputs and (3) preserves the distinction between plant and sensitivity states in the reduced model. This last property enables one to use the reduced model to generate a controller which minimizes a cost function that includes both output (trajectory) sensitivity and input (control) sensitivity terms. The order of this desensitized controller can then be further reduced using the same general covariance equivalence theory applied to controller reduction.     

Fuzzy Cognitive Maps for stereovision matching

This paper outlines a method for solving the stereovision matching problem using edge segments as the primitives. In stereovision matching the following constraints are commonly used: epipolar, similarity, smoothness, ordering and uniqueness. We propose a new matching strategy under a fuzzy context in which such constraints are mapped. The fuzzy context integrates both Fuzzy Clustering and Fuzzy Cognitive Maps. With such purpose a network of concepts (nodes) is designed, each concept represents a pair of primitives to be matched. Each concept has associated a fuzzy value which determines the degree of the correspondence. The goal is to achieve high performance in terms of correct matches. The main findings of this paper are reflected in the use of the fuzzy context that allows building the network of concepts where the matching constraints are mapped. Initially, each concept value is loaded via the Fuzzy Clustering and then updated by the Fuzzy Cognitive Maps framework. This updating is achieved through the influence of the remainder neighboring concepts until a good global matching solution is achieved. Under this fuzzy approach we gain quantitative and qualitative matching correspondences. This method works as a relaxation matching approach and its performance is illustrated by comparative analysis against some existing global matching methods.     

Pseudo-Randomness of Certain Sequences of <Emphasis Type="Italic">k</Emphasis> Symbols with Length <Emphasis Type="Italic">pq</Emphasis>

The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sárközy and later extended to sequences of k symbols (or k-ary sequences). Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.     

Linear complexity and autocorrelation values of a polyphase generalized cyclotomic sequence of length <Emphasis Type="Italic">pq</Emphasis>

A construction of a family of generalized polyphase cyclotomic sequences of length pq is presented in terms of the generalized cyclotomic classes modulo pq. Their linear complexity and corresponding minimal polynomials are deduced. Some upper bounds on periodic and aperiodic autocorrelation values of resulting sequences are also estimated by using certain exponential sums.     

基于语言和约束匹配器融合的元素匹配研究

在模式匹配方面已经出现了许多使用于特定应用领域的部分自动匹配方法,这种匹配方法结合了多种匹配技术以便能够在大规模的多样匹配环境中得到高的匹配率。提出了一种基于模式的元素匹配方法,它融合了语言和约束匹配器,使用了复合元素名称匹配器和神经网络匹配器,结合基于语言的匹配算法和最大优先策略的原则,以多重标准条件下复合名称匹配器的结果作为约束对模式元素进行归类。通过组合使用复合名称匹配器和神经网络匹配器,使得本方法可以应用于更复杂的匹配环境。     

On measuring the distance between histograms

A distance measure between two histograms has applications in feature selection, image indexing and retrieval, pattern classification and clustering, etc. We propose a distance between sets of measurement values as a measure of dissimilarity of two histograms. The proposed measure has the advantage over the traditional distance measures regarding the overlap between two distributions; it takes the similarity of the non-overlapping parts into account as well as that of overlapping parts. We consider three versions of the univariate histogram, corresponding to whether the type of measurement is nominal, ordinal, and modulo and their computational time complexities are Θ(b), Θ(b) and O(b²) for each type of measurements, respectively, where b is the number of levels in histograms.     

A Canonical Locally Named Representation of Binding

This paper is about completely formal representation of languages with binding. We have previously written about a representation following an approach going back to Frege, based on first-order syntax using distinct syntactic classes for locally bound variables vs. global or free variables?(Sato and Pollack, J Symb Comput 45:598?C616, 2010). The present paper differs from our previous work by being more abstract. Whereas we previously gave a particular concrete function for canonically choosing the names of binders, here we characterize abstractly the properties required of such a choice function to guarantee canonical representation, and focus on the metatheory of the representation, proving that it is in substitution preserving isomorphism with the nominal Isabelle representation of pure lambda terms. This metatheory is formalized in Isabelle/HOL. The final section outlines a formalization in Matita of a challenging language with multiple binding and simultaneous substitution. The Isabelle and Matita proof files are available online.     

Efficient subsequence matching over large video databases

Video similarity matching has broad applications such as copyright detection, news tracking and commercial monitoring, etc. Among these applications, one typical task is to detect the local similarity between two videos without the knowledge on positions and lengths of each matched subclip pair. However, most studies so far on video detection investigate the global similarity between two short clips using a pre-defined distance function. Although there are a few works on video subsequence detection, all these proposals fail to provide an effective query processing mechanism. In this paper, we first generalize the problem of video similarity matching. Then, a novel solution called consistent keyframe matching (CKM) is proposed to solve the problem of subsequence matching based on video segmentation. CKM is designed with two goals: (1) good scalability in terms of the query sequence length and the size of video database and (2) fast video subsequence matching in terms of processing time. Good scalability is achieved by employing a batch query paradigm, where keyframes sharing the same query space are summarized and ordered. As such, the redundancy of data access is eliminated, leading to much faster video query processing. Fast subsequence matching is achieved by comparing the keyframes of different video sequences. Specifically, a keyframe matching graph is first constructed and then divided into matched candidate subgraphs. We have evaluated our proposed approach over a very large real video database. Extensive experiments demonstrate the effectiveness and efficiency of our approach.