Search

This paper analyses the chaotic characteristics of violent abnormal vibration signals of a large rolling mill, and studies phase space reconstruction techniques of the signals. On this basis, the vibration model of wavelet neural networks and the model of backpropagation neural networks are set up, respectively, through inversion methods. The properties of these two models are tested and compared with each other. The result shows that the wavelet neural networks have an advantage over the backpropagation neural networks in rapid convergence and high accuracy. [ABSTRACT FROM AUTHOR]

This paper presents a model of generalized timetabling problem and a decomposition algorithm which can decompose large problems into independent smaller subproblems—the search for a feasible solution can then be easily parallelized. The timetabling problem consists in fixing a sequence of meetings between teachers and students in a prefixed period of time (typically a week), satisfying a set of constraints of various types [9]. Course timetabling is a multi-dimensional NP-complete problem [4]. In this paper we present the multi-resource timetabling problem (MRTP), our model for the generalized high-school timetabling problem. The MRTP is a search problem—a feasible solution is searched. The main contribution of this paper is the Decomposition Algorithm for MRTP to parallelize the search, so the whole MRTP can be easily distributed and parallelized. Our approach was applied to real-life instances of high-school timetabling problems. Results are discussed at the end of this paper and parallelized search is compared with the centralized one. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new framework to provide continuous services to users by a collection of mobile servers distributed over an interconnection network. We model those mobile servers as a subset of host computers, and assume that a user host can receive the service if at least one adjacent host computer (including itself) plays the role of a server; i.e., we assume that the service could not be routed via the interconnection network. The main results obtained in this paper are summarized as follows: For the class of trees with n hosts, ⌈(n+1)/2⌉ mobile servers are necessary and sufficient to realize continuous services by the mobile servers, and for the class of Hamiltonian graphs with n hosts, ⌈(n+1)/3⌉ mobile servers are necessary and sufficient. [ABSTRACT FROM AUTHOR]

In an orthogonal projection of a convex polyhedron P the visibility ratio of a face f (similarly of an edge e) is the ratio of orthogonally projected area of f (length of e) and its actual area (length). In this paper we give algorithms for nice projections of P such that the minimum visibility ratio over all visible faces (over all visible edges) is maximized. [ABSTRACT FROM AUTHOR]

In a planar straight-line drawing of a tree T on k layers, each vertex is placed on one of k horizontal lines called layers and each edge is drawn as a straight-line segment. A planar straight-line drawing of a rooted tree T on k layers is called an upward drawing of T on k layers if, for each vertex u of T, no child of u is placed on a layer vertically above the layer on which u has been placed. For a tree T having pathwidth h, a linear-time algorithm is known that produces a planar straight-line drawing of T on ⌈3h/2⌉ layers. A necessary condition characterizing trees that admit planar straight-line drawings on k layers for a given value of k is also known. However, none of the known algorithms focuses on drawing a tree on the minimum number of layers. Moreover, although an upward drawing is the most useful visualization of a rooted tree, the known algorithms for drawing trees on k layers do not focus on upward drawings. In this paper, we give a linear-time algorithm to compute the minimum number of layers required for an upward drawing of a given rooted tree T. If T is not a rooted tree, then we can select a vertex u of T in linear time such that an upward drawing of T rooted at u would require the minimum number of layers among all other upward drawings of T rooted at the vertices other than u. We also give a linear-time algorithm to obtain an upward drawing of a rooted tree T on the minimum number of layers. [ABSTRACT FROM AUTHOR]

This paper deals with the Circular Pattern Matching Problem (CPM). In CPM, we are interested in pattern matching between the text $\mathcal T$ and the circular pattern $\mathcal C(\mathcal P)$ of a given pattern $\mathcal P = \mathcal P_1 \ldots \mathcal P_m$. The circular pattern $\mathcal C(\mathcal P)$ is formed by concatenating $\mathcal P_1$ to the right of $\mathcal P_m$. We can view $\mathcal C(\mathcal P)$ as a set of m patterns starting at positions j ∈ [1..m] and wrapping around the end and if any of these patterns matches $\mathcal T$, we find a match for $\mathcal C(\mathcal P)$. In this paper, we present two efficient data structures to index circular patterns. This problem has applications in pattern matching in geometric and astronomical data as well as in computer graphics and bioinformatics. [ABSTRACT FROM AUTHOR]

Linear Feedback Shift Registers (LFSRs) are used as building blocks for many stream ciphers, wherein, an n-degree primitive connection polynomial is used as a feedback function to realize an n-bit LFSR. This paper shows that such LFSRs are susceptible to power analysis based Side Channel Attacks (SCA). The major contribution of this paper is the observation that the state of an n-bit LFSR can be determined by making O(n) power measurements. Interestingly, neither the primitive polynomial nor the value of n be known to the adversary launching the proposed attack. The paper also proposes a simple countermeasure for the SCA that uses n additional flipflops. [ABSTRACT FROM AUTHOR]

The Data Encryption Standard (DES) is a 64-bit block cipher. Despite its short key size of 56 bits, DES continues to be used to protect financial transactions valued at billions of Euros. In this paper, we investigate the strength of DES against attacks that use a limited number of plaintexts and ciphertexts. By mounting meet-in-the-middle attacks on reduced-round DES, we find that up to 6-round DES is susceptible to this kind of attacks. The results of this paper lead to a better understanding on the way DES can be used. [ABSTRACT FROM AUTHOR]

In this paper, we study the security of AES-192 against related-key differential-linear cryptanalysis, which is the first attempt using this technique. Among our results, we present two variant attacks on 7-round AES-192 and one attack on 8 rounds using a 5-round related-key differential-linear distinguisher. One key point of the construction of the distinguisher is the special property of MC operation of AES. Compared with the best known results of related-key impossible differential attacks and related-key rectangle attacks on AES-192, the results presented in this paper are not better than them, but the work is a new attempt, and we hope further work may be done to derive better results in the future. [ABSTRACT FROM AUTHOR]

The stream cipher TPypy has been designed by Biham and Seberry in January 2007 as the strongest member of the Py-family ciphers, after weaknesses in the other members Py, Pypy, Py6 were discovered. One main contribution of the paper is the detection of related-key weaknesses in the Py-family of ciphers including the strongest member TPypy. Under related keys, we show a distinguishing attack on TPypy with data complexity 2192.3 which is lower than the previous best known attack on the cipher by a factor of 288. It is shown that the above attack also works on the other members TPy, Pypy and Py. A second contribution of the paper is design and analysis of two fast ciphers RCR-64 and RCR-32 which are derived from the TPy and the TPypy respectively. The performances of the RCR-64 and the RCR-32 are 2.7 cycles/byte and 4.45 cycles/byte on Pentium III (note that the speeds of the ciphers Py, Pypy and RC4 are 2.8, 4.58 and 7.3 cycles/byte). Based on our security analysis, we conjecture that no attacks lower than brute force are possible on the RCR ciphers. [ABSTRACT FROM AUTHOR]

We characterize the traceability properties of linear codes. It is well known that any code of length n and minimum distance d is a c-TA code if c2 < n/(n − d). In this paper, we show that a less restrictive condition can be derived. In other words, there exists a value ZC, with n − d ≤ ZC ≤ c(n − d), such that any linear code is c-TA if c < n/ZC. We also prove that in many cases this condition is also necessary. These results are applied to cyclic and Reed-Solomon codes. [ABSTRACT FROM AUTHOR]

The abstraction of cryptographic operations by term algebras, called Dolev-Yao models or symbolic cryptography, is essential in almost all tool- supported methods for proving security protocols. Recently significant progress was made - using two conceptually different approaches - in proving that Dolev-Yao models can be sound with respect to actual cryptographic realizations and security definitions. One such approach is grounded on the notion of simulatability, which constitutes a salient technique of Modern Cryptography with a longstanding history for a variety of different tasks. The other approach strives for the so-called mapping soundness - a more recent technique that is tailored to the soundness of specific security properties in Dolev-Yao models, and that can be established using more compact proofs. Typically, both notions of soundness for similar Dolev-Yao models are established separately in independent papers. This paper relates the two approaches for the first time. Our main result is that simulatability soundness entails mapping soundness provided that both approaches use the same cryptographic implementation. Hence, future research may well concentrate on simulatability soundness whenever applicable, and resort to mapping soundness in those cases where simulatability soundness constitutes too strong a notion. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study communication in networks where nodes fail in a random dependent way. In order to capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, and cause faults in the given node and all of its neighbors. Faults at distance at most 2 become dependent in this model and are positively correlated. We investigate the impact of spot probability on feasibility and time of communication in the fault-free part of the network. We show a network which supports fast communication with high probability, if p ≤ 1/clogn. We also show that communication is not feasible with high probability in most classes of networks, for constant spot probabilities. For smaller spot probabilities, high probability communication is supported even by bounded degree networks. It is shown that the torus supports communication with high probability when p decreases faster than 1/n1/2, and does not when p ∈ 1/O(n1/2). Furthermore, a network built of tori is designed, with the same fault-tolerance properties and additionally supporting fast communication. We show, however, that networks of degree bounded by a constant d do not support communication with high probability, if p ∈ 1/O(n1/d). While communication in networks with independent faults was widely studied, this is the first analytic paper which investigates network communication for random dependent faults. [ABSTRACT FROM AUTHOR]

We initiate a study on automata recognizing labelled posets constructed from scattered and countable linear orderings. More precisely, the class of labelled posets considered in this paper is the smallest containing letters, closed under finite parallel operation and sequential product indexed by all countable and scattered linear orderings. The first result of this paper establishes that those labelled posets are precisely the N-free ones. The second result is a Kleene-like theorem, which establishes that the class of languages of labelled posets accepted by branching automata is exactly the class of rational languages. This generalizes both the finite [9] and ω-labelled posets [2,6] cases, and the Kleene-like theorem on words on linear orderings [3]. [ABSTRACT FROM AUTHOR]

Compression is most important when space is in short supply, so compression algorithms are often implemented in limited memory. Most analyses ignore memory constraints as an implementation detail, however, creating a gap between theory and practice. In this paper we consider the effect of memory limitations on compression algorithms. In the first part of the paper we assume the memory available is fixed and prove nearly tight upper and lower bound on how much is needed to compress a string close to its k-th order entropy. In the second part we assume the memory available grows (slowly) as more and more characters are read. In this setting we show that the rate of growth of the available memory determines the speed at which the compression ratio approaches the entropy. In particular, we establish a relationship between the rate of growth of the sliding window in the LZ77 algorithm and its convergence rate. [ABSTRACT FROM AUTHOR]

Requirements inconsistencies, caught early in a software lifecycle, prevents unnecessary work later in that lifecycle. Testing requirements for consistency early and automatically is a key to catching errors. This paper will share an experience with a mature software project that involved translating software requirements with overlapping definitions into a conceptual graph and recommends the use of several new actors to help automatically test a requirements consistency graph. [ABSTRACT FROM AUTHOR]

The system of Peirce's existential graphs is a diagrammatic version of first order logic. To be more precise: As Peirce wanted to develop a logic of relatives (i.e., relations), existential graphs correspond to first order logic with relations and identity, but without constants or functions. In contemporary elaborations of first order logic, constants and functions are usually employed. In this paper, it is described how the syntax, semantics and calculus for Peirce's existential graphs has to be extended in order to encompass constants and functions as well. [ABSTRACT FROM AUTHOR]

Detecting the boundaries of protein domains has been an important and challenging problem in experimental and computational structural biology. In this paper the domain detection is first taken as an imbalanced data learning problem. A novel undersampling method using distance-based maximal entropy in the feature space of SVMs is proposed. On multiple sequence alignments that are derived from a database search, multiple measures are defined to quantify the domain information content of each position along the sequence. The overall accuracy is about 87% together with high sensitivity and specificity. Simulation results demonstrate that the utility of the method can help not only in predicting the complete 3D structure of a protein but also in the machine learning system on general imbalanced datasets. [ABSTRACT FROM AUTHOR]

Provide these intelligent medical services, it is necessary to understand the situation information generated in a hospital. There should be infra technologies that can classify and control the information for processing situation data, not mere collection of conceptual information, with clear standards. This paper, as a study to seize the information generated from medical situation more clearly, understood the property of data using neural network and applied the security ratings of information so that the system to provide the user appropriate to designated rating with analyzed medical information is established. It will be an effective measure to enhance the effectiveness of medical devices and backup data already introduced and understand the various medical data that will be generated from medical devices to be introduced. [ABSTRACT FROM AUTHOR]

An edge detection method by combining image entropy and Self -Organizing Map (SOM) is proposed in this paper. First, according to information theory image entropy is used to curve up the smooth region and the region of gray level abruptly changed. Then we transform the gray level image to ideal binary pattern of pixels. We define six classes' edge and six edge prototype vectors. These edge prototype vectors are fed into input layer of the Self-Organizing Map (SOM). Classifying the type of edge through this network, the edge image is obtained. At last, the speckle edges are discarded from the edge image. Experimental results show that it gained better edge image compared with Canny edge detection method. [ABSTRACT FROM AUTHOR]

With the development of Intelligent Transport Systems (ITS), automatic license plate recognition (LPR) plays an important role in numerous applications in reality. In this paper, a coarse to fine algorithm to detect license plates in images and video frames with complex background is proposed. First, the method based on Component Connect (CC) is used to detect the possible license plate regions in the coarse detection. Second, the method based on texture analysis is applied in the fine detection. Finally, a BP Neural Network is adopted as classifier, parts of the features is selected based on statistic diagram to make the network efficient. The average accuracy of detection is 95.3% from the images with different angles and different lighting conditions. [ABSTRACT FROM AUTHOR]

In this paper, synchronization is investigated for an array of nonlinearly coupled identical connected neural networks with delay. By employing the Lyapunov functional method and the Kronecker product technique, several sufficient conditions are derived. It is shown that global exponential synchronization of the coupled neural networks is guaranteed by a suitable design of the coupling matrix, the inner linking matrix and some free matrices representing the relationships between the system matrices. The conditions obtained in this paper are in the form of linear matrix inequalities, which can be easily computed and checked in practice. A typical example with chaotic nodes is finally given to illustrate the effectiveness of the proposed synchronization scheme. [ABSTRACT FROM AUTHOR]

Of the possible interactions between human and robot, touch is an important means of providing human beings with emotional relief. However, most previous studies have focused on interactions based on voice and images. In this paper, a method of recognizing human touching behaviors is proposed for developing a robot that can naturally interact with humans through touch. In this method, the recognition process is divided into pre-process phase and recognition phase. In the pre-process phase, recognizable characteristics are calculated from the data generated by the touch detector which was fabricated using force sensors. The force sensor used an FSR (force sensing register). The recognition phase classifies human touching behaviors using a multi-layer perceptron which is a neural network model. We measured three different human touching behaviors for six men. The human touching behaviors are ‘hitting,' 'stroking,' and ‘tickling'. In the test conducted with recognizers generated for each user, the average recognition rate was 93.8%, while the test conducted with a single recognizer showed a 79.8% average recognition rate. These results show the feasibility of the proposed human touching behavior recognition method. [ABSTRACT FROM AUTHOR]

This paper investigates the construction of a wide class of singlehidden layer neural networks (SLNNs) with or without tunable parameters in the hidden nodes. It is a challenging problem if both the parameter training and determination of network size are considered simultaneously. Two alternative network construction methods are considered in this paper. Firstly, the discrete construction of SLNNs is introduced. The main objective is to select a subset of hidden nodes from a pool of candidates with parameters fixed ‘a priori'. This is called discrete construction since there are no parameters in the hidden nodes that need to be trained. The second approach is called continuous construction as all the adjustable network parameters are trained on the whole parameter space along the network construction process. In the second approach, there is no need to generate a pool of candidates, and the network grows one by one with the adjustable parameters optimized. The main contribution of this paper is to show that the network construction can be done using the above two alternative approaches, and these two approaches can be integrated within a unified analytic framework, leading to potentially significantly improved model performance and/or computational efficiency. [ABSTRACT FROM AUTHOR]

At present, most of the algorithms for learning Bayesian Networks (BNs) use EM algorithm to deal with incomplete data. They are of low efficiency because EM algorithm has to perform iterative process of probability reasoning to complete the incomplete data. In this paper we present an efficient BN learning algorithm, which use the combination of EMI method and a scoring function based on mutual information theory. The algorithm first uses EMI method to estimate, from incomplete data, probability distributions over local structures of BNs, then evaluates BN structures with the scoring function and searches for the best one. The detailed procedure of the algorithm is depicted in the paper. The experimental results on Asia and Alarm networks show that when achieving high accuracy, the algorithm is much more efficient than two EM based algorithms, SEM and EM-EA algorithms. [ABSTRACT FROM AUTHOR]

Fuzzy Petri net (FPN) is a powerful modeling tool for fuzzy production rules based knowledge systems. But it is lack of learning mechanism, which is the main weakness while modeling uncertain knowledge systems. Fuzzy neural Petri net (FNPN) is proposed in this paper, in which fuzzy neuron components are introduced into FPN as a sub-net model of FNPN. For neuron components in FNPN, back propagation (BP) learning algorithm of neural network is introduced. And the parameters of fuzzy production rules in FNPN neurons can be learnt and trained by this means. At the same time, different neurons on different layers can be learnt and trained independently. The FNPN proposed in this paper is meaningful for Petri net models and fuzzy systems. [ABSTRACT FROM AUTHOR]

Consumer demand for intelligent battery charges is increasing as portable electronic applications continue to grow. Fast charging of battery packs is a problem which is difficult, and often expensive, to solve using conventional techniques. Conventional techniques only perform a linear approximation of a nonlinear behavior of a battery packs. The battery charging is a nonlinear electrochemical dynamic process and there is no exact mathematical model of battery. Better techniques are needed when a higher degree of accuracy and minimum charging time are desired. In this paper we propose soft computing approach based on fuzzy recurrent neural networks (RFNN) training by genetic algorithms to control batteries charging process. This technique does not require mathematical model of battery packs, which are often difficult, if not impossible, to obtain. Nonlinear and uncertain dynamics of the battery pack is modeled by recurrent fuzzy neural network. On base of this FRNN model, the fuzzy control rules of the control system for battery charging is generated. Computational experiments show that the suggested approach gives least charging time and least Tend-Tstart results according to the other intelligent battery charger works. [ABSTRACT FROM AUTHOR]

Tree-based algorithms, such as Patricia, LC-trie, LPFST, etc, are widely used to do longest prefix matching (LPM). These algorithms use all the bits of the prefix to build the tree and the bits are used from the most significant bit to the least significant bit sequentially. Thus the tree is not balanced and the tree depth is high. In this paper, we propose bit selection tree (BS-tree) to do LPM. The bits of the prefix are selected to build BS-tree based on their costs defined in this paper. BS-tree has lower tree depth and is more balanced compared to other tree-based schemes. BS-tree has good scalability to the length of the IP address and is suitable for both IPv4 and IPv6. We evaluate the performances of BS-tree using both IPv4 and IPv6, and specially refine it for IPv6 based on the observations on IPv6 address and real IPv6 routing tables. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a Yet ImprovEd Limited Discrepancy Search (YIELDS), a complete algorithm for solving Constraint Satisfaction Problems. As indicated in its name, YIELDS is an improved version of Limited Discrepancy Search (LDS). It integrates constraint propagation and variable order learning. The learning scheme, which is the main contribution of this paper, takes benefit from failures encountered during search in order to enhance the efficiency of variable ordering heuristic. As a result, we obtain a search which needs less discrepancies than LDS to find a solution or to state a problem is intractable. This method is then less redundant than LDS. The efficiency of YIELDS is experimentally validated, comparing it with several solving algorithms: Depth-bounded Discrepancy Search, Forward Checking, and Maintaining Arc-Consistency. Experiments carried out on randomly generated binary CSPs and real problems clearly indicate that YIELDS often outperforms the algorithms with which it is compared, especially for tractable problems. [ABSTRACT FROM AUTHOR]

Kabastianskii, Krouk and Smeets proposed in 1997 a digital signature scheme based on random error-correcting codes. In this paper we investigate the security and the efficiency of their proposal. We show that a passive attacker who may intercept just a few signatures can recover the private key. We give precisely the number of signatures required to achieve this goal. This enables us to prove that all the schemes given in the original paper can be broken with at most 20 signatures. We improve the efficiency of these schemes by firstly providing parameters that enable to sign about 40 messages, and secondly, by describing a way to extend these few-times signatures into classical multi-time signatures. We finally study their key sizes and a mean to reduce them by means of more compact matrices. [ABSTRACT FROM AUTHOR]

The small world phenomenon, a.k.a. the six degree of separation between individuals, was identified by Stanley Milgram at the end of the 60s. Milgram experiment demonstrated that letters from arbitrary sources and bound to an arbitrary target can be transmitted along short chains of closely related individuals, based solely on some characteristics of the target (professional occupation, state of leaving, etc.). In his paper on small world navigability, Jon Kleinberg modeled this phenomenon in the framework of augmented networks, and analyzed the performances of greedy routing in augmented multi-dimensional meshes. This paper objective is to survey the results that followed up Kleinberg seminal work, including results about: extensions of the augmented network model, and variants of greedy routing,designs of ${\mbox{\rm polylog}}$-navigable graph classes,the quest for universal augmentation schemes, anddiscussions on the validation of the model in the framework of doubling metrics. [ABSTRACT FROM AUTHOR]

Association, or LD (linkage disequilibrium), mapping is an intensely-studied approach to gene mapping (genome-wide or in candidate regions) that is widely hoped to be able to efficiently locate genes influencing both complex and Mendelian traits. The logic underlying association mapping implies that the best possible mapping results would be obtained if the genealogical history of the sampled individuals were explicitly known. Such a history would be in the form of an "ancestral recombination graph (ARG)". But despite the conceptual importance of genealogical histories to association mapping, few practical association mapping methods have explicitly used derived genealogical aspects of ARGs. Two notable exceptions are [35] and [23]. In this paper we develop an association mapping method that explicitly constructs and samples minARGs (ARGs that minimize the number of recombinations). We develop an ARG sampling method that provably samples minARGs uniformly at random, and that is practical for moderate sized datasets. We also develop a different, faster, ARG sampling method that still samples from a well-defined subspace of ARGs, and that is practical for larger sized datasets. We present novel efficient algorithms on extensions of the "phenotype likelihood" problem, a key step in the method in [35]. We also prove that computing the phenotype likelihood for a different natural extension of the penetrance model in [35] is NP-hard, answering a question unresolved in that paper. Finally, we put all of these results into practice, and examine how well the implemented methods perform, compared to the results in [35]. The empirical results show great speed ups, and definite but sometimes small, improvements in mapping accuracy. Speed is particularly important in doing genome-wide scans for causative mutations. [ABSTRACT FROM AUTHOR]

Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. In this paper we introduce a special class of finite circular splicing systems named marked systems. We prove that a marked system S generates a regular circular language if and only if S satisfies a special (decidable) property. As a consequence, we show that we can decide whether a regular circular language is generated by a marked system and we characterize the structure of these regular circular languages. [ABSTRACT FROM AUTHOR]

This paper proposes several approaches to improve the collision attack on MD4 proposed by Wang et al. First, we propose a new local collision that is the best for the MD4 collision attack. Selection of a good message difference is the most important step in achieving effective collision attacks. This is the first paper to introduce an improvement to the message difference approach of Wang et al., where we propose a new local collision. Second, we propose a new algorithm for constructing differential paths. While similar algorithms have been proposed, they do not support the new local collision technique.Finally, we complete a collision attack, and show that the complexity is smaller than the previous best work. [ABSTRACT FROM AUTHOR]

In a Eurocrypt 2006 article entitled "QUAD: A Practical Stream Cipher with Provable Security," Berbain, Gilbert, and Patarin introduced ${\texttt{QUAD}}$, a parametrized family of stream ciphers. The article stated that "the security of the novel stream cipher is provably reducible to the intractability of the MQ problem"; this reduction deduces the infeasibility of attacks on ${\texttt{QUAD}}$ from the hypothesized infeasibility (with an extra looseness factor) of attacks on the well-known hard problem of solving systems of multivariate quadratic equations over finite fields. The ${\texttt{QUAD}}$ talk at Eurocrypt 2006 reported speeds for ${\texttt{QUAD}}$ instances with 160-bit state and output block over the fields GF(2), GF(16), and GF(256). This paper discusses both theoretical and practical aspects of attacking ${\texttt{QUAD}}$ and of attacking the underlying hard problem. For example, this paper shows how to use XL-Wiedemann to break the GF(256) instance ${\texttt{QUAD}}(256,20,20)$ in approximately 266 Opteron cycles, and to break the underlying hard problem in approximately 245 cycles. For each of the ${\texttt{QUAD}}$ parameters presented at Eurocrypt 2006, this analysis shows the implications and limitations of the security proofs, pointing out which ${\texttt{QUAD}}$ instances are not secure, and which ones will never be proven secure. Empirical data backs up the theoretical conclusions; in particular, the 245-cycle attack was carried out successfully. [ABSTRACT FROM AUTHOR]

Pawlak rough set theory is a powerful mathematic tool to deal with imprecise, uncertainty and incomplete dataset. In this paper, we study the fuzzy rough set attribute reduction (fuzzy RSAR) in fuzzy information systems. Firstly, we present the formal definition of a kind new rough set form-the composed fuzzy rough set. The second, some properties of extension forms of Pawlak rough set are also discussed. Lastly, we illustrate the fuzzy RSAR based on composed fuzzy rough set, and a simple example is given to show this approach can retain less attributes and entailing higher classification accuracy than the crisp RST-based reduction method. [ABSTRACT FROM AUTHOR]

Traditional pencil drawing methods have their own drawbacks, such as modeling complexity and higher time-consuming. Thus, they are difficult to be suitable for the real-time applications. In the paper, we present a new pencil texture generating method based on the pencil filter. The method can conveniently generate the pencil drawing effect by convoluting the input image with the pencil filter. Moreover, the method is implemented on GPU, and then satisfies the requirement of real-time synthesis. Optical flow technique is used to guarantee the interframe coherence in video stylization. [ABSTRACT FROM AUTHOR]

In this paper, we propose a modified LSB steganography which resists most of the popular statistical analysis-based steganalysis,such as SPA(Sample Pair Analysis) and RS. The modified algorithm does not solely depends on embedding secret message into the cover image as the conventional LSB watermarking method does, but increases or decreases the candidate pixel's value by two in accordance with the number of the pixel's surrounding pixels whose LSB is positive. We discuss on the basic principle of the proposed algorithm and experiments show that the improved LSB steganography has a good robustness to statistical analysis. An extended cat-mapping is introduced in this paper which will better encrypt the secret message than the standard cat mapping. Experiments show the histogram of the encrypted image will be flat and resembles the white noise's histogram, which significantly enhances the security of the algorithm. [ABSTRACT FROM AUTHOR]

In the paper, we propose a new systematic model, called General Biswapped Networks (GBSNs), to construct hierarchical interconnection networks that are able to maintain many desirable attributes of the underlying basis networks consisting of clusters. The model is inspired by and extended from Biswapped Networks (BSNs) and OTIS networks. A network in the new proposed model Gbsw(Ω, Δ) is composed of m copies of some n-node basis network Ω and n copies of some m-node basis network Δ. Such a network uses a simple rule for connectivity that ensures its semi-regularity, modularity, fault tolerance, and algorithmic efficiency. In particular, the BSNs are special cases in which the two basis networks are the same. The Exchanged Hypercube is another example of GBSNs, i.e., EH(s,t) ≅ Gbsw(H(s), H(t)). The proposed network model is able to reveal the intrinsic relation between Swapped Networks and OTIS architectures. We are to prove the homomorphic relation between GBSNs and the Cartesian product of its two basis networks. We also show the key topological parameters of GBSNs that are related to the parameters of its basis networks. We have obtained the results on inter-node distances, a general simple routing algorithm, Halmitonian cycles for networks composed of Halmitonian basis networks with even number of nodes or same number of nodes. Finally, this paper provides a new layout style for hierarchical interconnection networks that offers the researcher an opportunity to explore the topological properties of networks more intuitively and insightfully. [ABSTRACT FROM AUTHOR]

Recent years, as the wide deployment of embedded and mobile devices, reducing the power consumption in order to extend the battery life becomes a major factor that a designer must consider when designing a new architecture. DVS is regarded as one of the most effective power reduction techniques. This paper focuses on run-time compiler driven DVS for power reduction, especially two key design issues including DVS analysis model and DVS decision algorithm. Based on the design framework presented in this work, we also implement a run-time DVS compiler which is fine-grained, adaptive to the program's running environment without changing its behavior. The obtained system is deployed in a real hardware platform. Experimental results, based on some benchmarks, show that with average 5% performance loss, the benchmarks benefit with 26% dynamic power savings and the energy delay product (EDP) improvement is 22%. [ABSTRACT FROM AUTHOR]

A new method of designing and using virtual array in pipeline reconfigurable system is presented. This method is based on the partition of the configuration data. Using this method not only is helpful to design the virtual hardware, but also is necessary to investigate the application algorithms oriented this virtual hardware. Basing on the analysis of the space-time graph and the configuration plane, this paper explores the structure and application of virtual array integrated in the MPRS (Multi-Pipeline Reconfigurable System), an in-house developed reconfigurable computing system that utilizes virtual pipeline. Finally, the design procedure of mapping the application to the virtual array and the programming procedure of using the MPRS are illustrated by examples. The experiment results show that the method is feasible and the performance of the MPRS with the virtual array nearly reaches the expected level. [ABSTRACT FROM AUTHOR]

Edwards curves have attracted great interest for several reasons. When curve parameters are chosen properly, the addition formulas use only 10M + 1S. The formulas are strongly unified, i.e., work without change for doublings; even better, they are complete, i.e., work without change for all inputs. Dedicated doubling formulas use only 3M + 4S, and dedicated tripling formulas use only 9M + 4S. This paper introduces inverted Edwards coordinates. Inverted Edwards coordinates (X1:Y1:Z1) represent the affine point (Z1/X1,Z1/Y1) on an Edwards curve; for comparison, standard Edwards coordinates (X1:Y1:Z1) represent the affine point (X1/Z1,Y1/Z1). This paper presents addition formulas for inverted Edwards coordinates using only 9M + 1S. The formulas are not complete but still are strongly unified. Dedicated doubling formulas use only 3M + 4S, and dedicated tripling formulas use only 9M + 4S. Inverted Edwards coordinates thus save 1M for each addition, without slowing down doubling or tripling. [ABSTRACT FROM AUTHOR]

This paper studies the problem of computing an upward topological book embedding of an upward planar digraph G, i.e. a topological book embedding of G where all edges are monotonically increasing in the upward direction. Besides having its own inherent interest in the theory of upward book embeddability, the question has applications to well studied research topics of computational geometry and of graph drawing. The main results of the paper are as follows. Every upward planar digraph G with n vertices admits an upward topological book embedding such that every edge of G crosses the spine of the book at most once.Every upward planar digraph G with n vertices admits a point-set embedding on any set of n distinct points in the plane such that the drawing is upward and every edge of G has at most two bends.Every pair of upward planar digraphs sharing the same set of n vertices admits an upward simultaneous embedding with at most two bends per edge. [ABSTRACT FROM AUTHOR]

In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. In this paper we will propose some approximation algorithms for this problem that beat the current best performance ratios. [ABSTRACT FROM AUTHOR]

This paper studies a spanning tree problem with interval data that finds diverse applications in network design. Given an underlying network G = (V,E), each link e ∈ E can be established by paying a cost $c_e\in[\underline{c}_e,\overline{c}_e]$, and accordingly takes a risk $\frac{\overline{c}_e-c_e}{\overline{c}_e-\underline{c}_e}$ of link failure. The minimum risk spanning tree (MRST) problem is to establish a spanning tree in G of total cost no more than a given constant so that the risk sum over the links on the spanning tree is minimized. In this paper, we propose an exact algorithm for the MRST problem that has time-complexity of O(m2logm logn(m + n logn)), where m = E and n = V. [ABSTRACT FROM AUTHOR]

This paper addresses strategies for the stable roommates problem, assuming that a stable matching is chosen at random. We investigate how a cheating man should permute his preference list so that he has a higher-ranking roommate probabilistically. In the first part of the paper, we identify a necessary condition for creating a new stable roommate for the cheating man. This condition precludes any possibility of his getting a new roommate ranking higher than all his stable roommates when everyone is truthful. Generalizing to the case that multiple men collude, we derive another impossibility result: given any stable matching in which a subset of men get their best possible roommates, they cannot cheat to create a new stable matching in which they all get strictly better roommates than in the given matching. Our impossibility result, considered in the context of the stable marriage problem, easily re-establishes the celebrated Dubins-Freedman Theorem. The more generalized Demange-Gale-Sotomayor Theorem states that a coalition of men and women cannot cheat to create a stable matching in which everyone of them gets a strictly better partner than in the Gale-Shapley algorithm (with men proposing). We give a sharper result: a coalition of men and women cannot cheat together so that, in a newly-created stable matching, every man in the coalition gets a strictly better partner than in the Gale-Shapley algorithm while none of the women in the coalition is worse off. In the second part of the paper, we present two cheating strategies that guarantee that the cheating man's new probability distribution over stable roommates majorizes the original one. These two strategies do not require the knowledge of the probability distribution of the cheating man. This is important because the problem of counting stable matchings is #P-complete. Our strategies only require knowing the set of stable roommates that the cheating man has and can be formulated in polynomial time. Our second cheating strategy has an interesting corollary in the context of stable marriage with the Gale-Shapley algorithm. Any woman-optimal strategy will ensure that every woman, cheating or otherwise, ends up with a partner at least as good as when everyone is truthful. [ABSTRACT FROM AUTHOR]

The problem of dynamically recognizing a class of graphs has received much attention recently. Given an input graph and a sequence of operations (vertex and edge additions and deletions) to be performed on that graph, the algorithm must determine after each operation if the resulting graph is still a member of the class in question. This paper presents the first dynamic recognition algorithm for distance-hereditary graphs. The algorithm handles edge additions and deletions, and is optimal in that each operation can be performed in constant time. In doing so, the paper completely characterizes when an edge can be added to and removed from a distance-hereditary graph with the result remaining distance-hereditary, and develops a new representation for these graphs in terms of cographs. [ABSTRACT FROM AUTHOR]

The problem of image matching is to find for two given digital images A and B an admissible transformation that converts image A as close as possible to B. This problem becomes hard if the space of admissible transformations is too complex. Consequently, in many real applications, like the ones allowing nonlinear elastic transformations, the known algorithms solving the problem either work in exponential worst-case time or can only guarantee to find a local optimum. Recently Keysers and Unger have proved that the image matching problem for this class of transformations is NP-complete, thus giving evidence that the known exponential time algorithms are justified. On the other hand, allowing only such transformations as translations, rotations, or scalings the problem becomes tractable. In this paper we analyse the computational complexity of image matching for a larger space of admissible transformations, namely for all affine transformations. In signal processing there are no efficient algorithms known for this class. Similarly, the research in combinatorial pattern matching does not cover this set of transformations neither providing efficient algorithms nor proving intractability of the problem, although it is a basic one and of high practical importance. The main result of this paper is that the image matching problem can be solved in polynomial time even allowing all affine transformations. [ABSTRACT FROM AUTHOR]

In the last decade there has been an ongoing interest in string comparison problems; to a large extend the interest was stimulated by genome rearrangement problems in computational biology but related problems appear in many other areas of computer science. Particular attention has been given to the problem of sorting by reversals(SBR): given two strings, A and B, find the minimum number of reversals that transform the string A into the string B (a reversalρ(i,j), i

LSH (Locality Sensitive Hashing) is one of the best known methods for solving the c-approximate nearest neighbor problem in high dimensional spaces. This paper presents a variant of the LSH algorithm, focusing on the special case of where all points in the dataset lie on the surface of the unit hypersphere in a d-dimensional Euclidean space. The LSH scheme is based on a family of hash functions that preserves locality of points. This paper points out that when all points are constrained to lie on the surface of the unit hypersphere, there exist hash functions that partition the space more efficiently than the previously proposed methods. The design of these hash functions uses randomly rotated regular polytopes and it partitions the surface of the unit hypersphere like a Voronoi diagram. Our new scheme improves the exponent ρ, the main indicator of the performance of the LSH algorithm. [ABSTRACT FROM AUTHOR]