Dynamically Reconfigurable Regular Expression Matching Architecture

Regular Expressions are generic representations for a string or a collection of strings. This paper focuses on implementation of a regular expression matching architecture on reconfigurable fabric like FPGA. We present a Nondeterministic Finite Automata based implementation with extended regular expression syntax set compared to previous approaches. We also describe a dynamically reconfigurable generic block that implements the supported regular expression syntax. This enables formation of the regular expression hardware by a simple cascade of generic blocks as well as a possibility for reconfiguring the generic blocks to change the regular expression being matched. Further,we have developed an HDL code generator to obtain the VHDL description of the hardware for any regular expression set. Our optimized regular expression engine achieves a throughput of 2.45 Gbps. Our dynamically reconfigurable regular expression engine achieves a throughput of 0.8 Gbps using 12 FPGA slices per generic block on Xilinx Virtex2Pro FPGA.

A Combinatorial Family of Near Regular LDPC Codes

An elementary combinatorial Tanner graph construction for a family of near-regular low density parity check (LDPC) codes achieving high girth is presented. These codes are near regular in the sense that the degree of a left/right vertex is allowed to differ by at most one from the average. The construction yields in quadratic time complexity an asymptotic code family with provable lower bounds on the rate and the girth for a given choice of block length and average degree. The construction gives flexibility in the choice of design parameters of the code like rate, girth and average degree. Performance simulations of iterative decoding algorithm for the AWGN channel on codes designed using the method demonstrate that these codes perform better than regular PEG codes and MacKay codes of similar length for all values of Signal to noise ratio.

On Pushing Multilingual Query Operators into Relational Engines

To effectively support today’s global economy, database systems need to manage data in multiple languages simultaneously. While current database systems do support the storage and management of multilingual data, they are not capable of querying across different natural languages. To address this lacuna, we have recently proposed two cross-lingual functionalities, LexEQUAL[13] and SemEQUAL[14], for matching multilingual names and concepts, respectively. In this paper, we investigate the native implementation of these multilingual functionalities as first-class operators on relational engines. Specifically, we propose a new multilingual storage datatype, and an associated algebra of the multilingual operators on this datatype. These components have been successfully implemented in the PostgreSQL database system, including integration of the algebra with the query optimizer and inclusion of a metric index in the access layer. Our experiments demonstrate that the performance of the native implementation is up to two orders-of-magnitude faster than the corresponding outsidethe- server implementation. Further, these multilingual additions do not adversely impact the existing functionality and performance. To the best of our knowledge, our prototype represents the first practical implementation of a crosslingual database query engine.

Role of Nonplanar Peptide Unit in Regular Polypeptide Helices - New Model for Pply-Beta-Benzyl-L-Aspartate

The effect of non-planarity of the peptide unit on helical structures stabilized by intrachain hydrogen bonds is discussed. While the present calculations generally agree with those already reported in the literature for right-handed helical structures, it is found that the most stable left-handed structure is a novel helix, called the delta-helix. Its helical parameters are close to these reported for poly-beta-benzyl-L -aspartate. Conformational energy calculations show that poly-beta-benzyl-L -aspartate with the delta-helical structure is considerably more stable than the structure it is generally believed to take up (the omega-helix) by about 15 kcal/mol-residue.

Noncommutative vortices and instantons from generalized Bose operators

Generalized Bose operators correspond to reducible representations of the harmonic oscillator algebra. We demonstrate their relevance in the construction of topologically non-trivial solutions in noncommutative gauge theories, focusing our attention to flux tubes, vortices, and instantons. Our method provides a simple new relation between the topological charge and the number of times the basic irreducible representation occurs in the reducible representation underlying the generalized Bose operator. When used in conjunction with the noncommutative ADHM construction, we find that these new instantons are in general not unitarily equivalent to the ones currently known in literature.

Is saccade averaging determined by visual processing or movement planning?

Bhutani N, Ray S, Murthy A. Is saccade averaging determined by visual processing or movement planning? J Neurophysiol 108: 3161-3171, 2012. First published September 26, 2012; doi:10.1152/jn.00344.2012.-Saccadic averaging that causes subjects' gaze to land between the location of two targets when faced with simultaneously or sequentially presented stimuli has been often used as a probe to investigate the nature of computations that transform sensory representations into an oculomotor plan. Since saccadic movements involve at least two processing stages-a visual stage that selects a target and a movement stage that prepares the response-saccade averaging can either occur due to interference in visual processing or movement planning. By having human subjects perform two versions of a saccadic double-step task, in which the stimuli remained the same, but different instructions were provided (REDIRECT gaze to the later-appearing target vs. FOLLOW the sequence of targets in their order of appearance), we tested two alternative hypotheses. If saccade averaging were due to visual processing alone, the pattern of saccade averaging is expected to remain the same across task conditions. However, whereas subjects produced averaged saccades between two targets in the FOLLOW condition, they produced hypometric saccades in the direction of the initial target in the REDIRECT condition, suggesting that the interaction between competing movement plans produces saccade averaging.

Efficient Regular Expression Pattern Matching for Network Intrusion Detection Systems using Modified Word-based Automata

Network Intrusion Detection Systems (NIDS) intercept the traffic at an organization's network periphery to thwart intrusion attempts. Signature-based NIDS compares the intercepted packets against its database of known vulnerabilities and malware signatures to detect such cyber attacks. These signatures are represented using Regular Expressions (REs) and strings. Regular Expressions, because of their higher expressive power, are preferred over simple strings to write these signatures. We present Cascaded Automata Architecture to perform memory efficient Regular Expression pattern matching using existing string matching solutions. The proposed architecture performs two stage Regular Expression pattern matching. We replace the substring and character class components of the Regular Expression with new symbols. We address the challenges involved in this approach. We augment the Word-based Automata, obtained from the re-written Regular Expressions, with counter-based states and length bound transitions to perform Regular Expression pattern matching. We evaluated our architecture on Regular Expressions taken from Snort rulesets. We were able to reduce the number of automata states between 50% to 85%. Additionally, we could reduce the number of transitions by a factor of 3 leading to further reduction in the memory requirements.

Multiple parents crossover operators: A new approach removes the overlapping solutions for sequencing problems

Maintaining population diversity throughout generations of Genetic Algorithms (GAs) is key to avoid premature convergence. Redundant solutions is one cause for the decreasing population diversity. To prevent the negative effect of redundant solutions, we propose a framework that is based on the multi-parents crossover (MPX) operator embedded in GAs. Because MPX generates diversified chromosomes with good solution quality, when a pair of redundant solutions is found, we would generate a new offspring by using the MPX to replace the redundant chromosome. Three schemes of MPX will be examined and will be compared against some algorithms in literature when we solve the permutation flowshop scheduling problems, which is a strong NP-Hard sequencing problem. The results indicate that our approach significantly improves the solution quality. This study is useful for researchers who are trying to avoid premature convergence of evolutionary algorithms by solving the sequencing problems.

Performance improvement of short-length regular low-density parity-check codes with low-complexity post-processing

It is well known that extremely long low-density parity-check (LDPC) codes perform exceptionally well for error correction applications, short-length codes are preferable in practical applications. However, short-length LDPC codes suffer from performance degradation owing to graph-based impairments such as short cycles, trapping sets and stopping sets and so on in the bipartite graph of the LDPC matrix. In particular, performance degradation at moderate to high E-b/N-0 is caused by the oscillations in bit node a posteriori probabilities induced by short cycles and trapping sets in bipartite graphs. In this study, a computationally efficient algorithm is proposed to improve the performance of short-length LDPC codes at moderate to high E-b/N-0. This algorithm makes use of the information generated by the belief propagation (BP) algorithm in previous iterations before a decoding failure occurs. Using this information, a reliability-based estimation is performed on each bit node to supplement the BP algorithm. The proposed algorithm gives an appreciable coding gain as compared with BP decoding for LDPC codes of a code rate equal to or less than 1/2 rate coding. The coding gains are modest to significant in the case of optimised (for bipartite graph conditioning) regular LDPC codes, whereas the coding gains are huge in the case of unoptimised codes. Hence, this algorithm is useful for relaxing some stringent constraints on the graphical structure of the LDPC code and for developing hardware-friendly designs.

Analysis of the degrees-of-freedom of spatial parallel manipulators in regular and singular configurations

This paper presents a study of the nature of the degrees-of-freedom of spatial manipulators based on the concept of partition of degrees-of-freedom. In particular, the partitioning of degrees-of-freedom is studied in five lower-mobility spatial parallel manipulators possessing different combinations of degrees-of-freedom. An extension of the existing theory is introduced so as to analyse the nature of the gained degree(s)-of-freedom at a gain-type singularity. The gain of one- and two-degrees-of-freedom is analysed in several well-studied, as well as newly developed manipulators. The formulations also present a basis for the analysis of the velocity kinematics of manipulators of any architecture. (C) 2013 Elsevier Ltd. All rights reserved.

Infinitely divisible metrics and curvature inequalities for operators in the Cowen-Douglas class

The curvature (T)(w) of a contraction T in the Cowen-Douglas class B-1() is bounded above by the curvature (S*)(w) of the backward shift operator. However, in general, an operator satisfying the curvature inequality need not be contractive. In this paper, we characterize a slightly smaller class of contractions using a stronger form of the curvature inequality. Along the way, we find conditions on the metric of the holomorphic Hermitian vector bundle E-T corresponding to the operator T in the Cowen-Douglas class B-1() which ensures negative definiteness of the curvature function. We obtain a generalization for commuting tuples of operators in the class B-1() for a bounded domain in C-m.

On Averaging Multiview Relations for 3D Scan Registration

In this paper, we present an extension of the iterative closest point (ICP) algorithm that simultaneously registers multiple 3D scans. While ICP fails to utilize the multiview constraints available, our method exploits the information redundancy in a set of 3D scans by using the averaging of relative motions. This averaging method utilizes the Lie group structure of motions, resulting in a 3D registration method that is both efficient and accurate. In addition, we present two variants of our approach, i.e., a method that solves for multiview 3D registration while obeying causality and a transitive correspondence variant that efficiently solves the correspondence problem across multiple scans. We present experimental results to characterize our method and explain its behavior as well as those of some other multiview registration methods in the literature. We establish the superior accuracy of our method in comparison to these multiview methods with registration results on a set of well-known real datasets of 3D scans.

Flag structure for operators in the Cowen-Douglas class

The explicit description of homogeneous operators and localization of a Hilbert module naturally leads to the definition of a class of Cowen-Douglas operators possessing a flag structure. These operators are irreducible. We show that the flag structure is rigid in the sense that the unitary equivalence class of the operator and the flag structure determine each other. We obtain a complete set of unitary invariants which are somewhat more tractable than those of an arbitrary operator in the Cowen-Douglas class. (C) 2014 Academie des sciences. Published by Elsevier Masson SAS. All rights reserved.

Revisiting neutrino masses from Planck scale operators

Planck scale lepton number violation is an interesting and natural possibility to explain nonzero neutrino masses. We consider such operators in the context of Randall-Sundrum (RS1) scenarios. Implementation of this scenario with a single Higgs localized on the IR brane (standard RS1) is not phenomenologically viable as they lead to inconsistencies in the charged lepton mass fits. In this paper we propose a setup with two Higgs doublets. We present a detailed numerical analysis of the fits to fermion masses and mixing angles. This model solves the issues regarding the fermion mass fits but solutions with consistent electroweak symmetry breaking are highly fine-tuned. A simple resolution is to consider supersymmetry in the bulk and a detailed discussion of which is provided. Constraints from flavor are found to be strong and minimal flavor violation (MFV) is imposed to alleviate them.