Search

Abstract: In this paper, we address the problem of outdoor, appearance-based topological localization, particularly over long periods of time where seasonal changes alter the appearance of the environment. We investigate a straightforward method that relies on local image features to compare single-image pairs. We first look into which of the dominating image feature algorithms, SIFT or the more recent SURF, that is most suitable for this task. We then fine-tune our localization algorithm in terms of accuracy, and also introduce the epipolar constraint to further improve the result. The final localization algorithm is applied on multiple data sets, each consisting of a large number of panoramic images, which have been acquired over a period of nine months with large seasonal changes. The final localization rate in the single-image matching, cross-seasonal case is between 80% to 95%. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of scheduling with release dates and rejection on a single parallel batching machine, where the jobs have non-identical sizes. Our objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs. First, we give a polynomial time approximation scheme (PTAS) for the case where jobs can be split. Then, we propose a -approximation algorithm for the special case with identical release dates. Finally, we present an approximation algorithm for the general problem with worst-case ratio , where is an arbitrarily small constant. [Copyright &y& Elsevier]

Abstract: In supervised learning tasks, boosting can combine multiple weak learners into a stronger one. AdaBoost is one of the most popular boosting algorithms, which is widely used and stimulates extensive research efforts in the boosting research community. Different from supervised learning, semi-supervised learning aims to make full use of both labeled and unlabeled data to improve learning performance, and has drawn considerable interests in both research and applications. To harness the power of boosting, it is important and interesting to extend AdaBoost to semi-supervised scenarios. Moreover, in semi-supervised learning, it is believed that incorporating pairwise constraints such as side-information is promising to obtain more satisfiable results. However, how to extend AdaBoost with pairwise constraints remains an open problem. In this paper, we propose a novel framework to solve this problem based on the gradient descent view of boosting. The proposed framework is almost as simple and flexible as AdaBoost, and can be readily applied in the presence of pairwise constraints. We present theoretical results, show possible further extensions, and validate the effectiveness via experiments. [Copyright &y& Elsevier]

Abstract: Classifying materials from their appearance is challenging. Impressive results have been obtained under varying illumination and pose conditions. Still, the effect of scale variations and the possibility to generalise across different material samples are still largely unexplored. This paper (A preliminary version of this work was presented in Hayman et al. [E. Hayman, B. Caputo, M.J. Fritz, J.-O. Eklundh, On the significance of real world conditions for material classification, in: Proceedings of the ECCV, Lecture Notes in Computer Science, vol. 4, Springer, Prague, 2004, pp. 253–266].) addresses these issues, proposing a pure learning approach based on support vector machines. We study the effect of scale variations first on the artificially scaled CUReT database, showing how performance depends on the amount of scale information available during training. Since the CUReT database contains little scale variation and only one sample per material, we introduce a new database containing 10 CUReT materials at different distances, pose and illumination. This database provides scale variations, while allowing to evaluate generalisation capabilities: does training on the CUReT database enable recognition of another piece of sandpaper? Our results demonstrate that this is not yet possible, and that material classification is far from being solved in scenarios of practical interest. [Copyright &y& Elsevier]

Abstract: The well-known problem of the longest common subsequence (LCS), of two strings of lengths and respectively, is -time solvable and is a classical distance measure for strings. Another well-studied string comparison measure is that of parameterized matching, where two equal-length strings are a parameterized match if there exists a bijection on the alphabets such that one string matches the other under the bijection. All works associated with parameterized pattern matching present polynomial time algorithms. There have been several attempts to accommodate parameterized matching along with other distance measures, as these turn out to be natural problems, e.g., Hamming distance, and a bounded version of edit-distance. Several algorithms have been proposed for these problems. In this paper we consider the longest common parameterized subsequence problem which combines the LCS measure with parameterized matching. We prove that the problem is -hard, and then show a couple of approximation algorithms for the problem. [Copyright &y& Elsevier]

Abstract: The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, and , with domain sizes and , respectively, and the same range, the goal of the problem is to find and such that . This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of functions for any constant integer , where the domain sizes of the functions may be different. [Copyright &y& Elsevier]

Abstract: This paper studies online scheduling of unit length jobs on a parallel batching machine with the help of lookahead. The objective is to maximize the number of early jobs. Denote by the size of each batch with in the unbounded batching and in the bounded batching. In the lookahead model, at a time instant , an online algorithm can foresee all jobs that will arrive in the time segment . When , we show that a simple greedy online algorithm (independent of the value of ) has a best possible competitive ratio of , where is the number of jobs. This means that lookahead is useless when . When , we establish the upper bounds (for ) and (for ) of competitive ratios, and provide an online algorithm of competitive ratios (for ) and (for ). [Copyright &y& Elsevier]

Abstract: The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. [Copyright &y& Elsevier]

Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [Copyright &y& Elsevier]

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]

Abstract: Optical interconnections attract many engineers and scientists’ attention due to their potential for gigahertz transfer rates and concurrent access to the bus in a pipelined fashion. These unique characteristics of optical interconnections give us the opportunity to reconsider traditional algorithms designed for ideal parallel computing models, such as PRAMs. Since the PRAM model is far from practice, not all algorithms designed on this model can be implemented on a realistic parallel computing system. From this point of view, we study Cole’s pipelined merge sort [Cole R. Parallel merge sort. SIAM J Comput 1988;14:770–85] on the CREW PRAM and extend it in an innovative way to an optical interconnection model, the LARPBS (Linear Array with Reconfigurable Pipelined Bus System) model [Pan Y, Li K. Linear array with a reconfigurable pipelined bus system—concepts and applications. J Inform Sci 1998;106;237–58]. Although Cole’s algorithm is optimal, communication details have not been provided due to the fact that it is designed for a PRAM. We close this gap in our sorting algorithm on the LARPBS model and obtain an O(log N)-time optimal sorting algorithm using O(N) processors. This is a substantial improvement over the previous best sorting algorithm on the LARPBS model that runs in O(log N loglog N) worst-case time using N processors [Datta A, Soundaralakshmi S, Owens R. Fast sorting algorithms on a linear array with a reconfigurable pipelined bus system. IEEE Trans Parallel Distribut Syst 2002;13(3):212–22]. Our solution allows efficiently assign and reuse processors. We also discover two new properties of Cole’s sorting algorithm that are presented as lemmas in this paper. [Copyright &y& Elsevier]

Abstract: This paper presents a novel hybrid GMDH-type algorithm which combines neural networks (NNs) with an approximation scheme (self-organizing polynomial neural network: SOPNN). This composite structure is developed to establish a new heuristic approximation method for identification of nonlinear static systems. NNs have been widely employed to process modeling and control because of their approximation capabilities. And SOPNN is an analysis technique for identifying nonlinear relationships between the inputs and outputs of such systems and builds hierarchical polynomial regressions of required complexity. Therefore, the combined model can harmonize NNs with SOPNN and find a workable synergistic environment. Simulation results of the nonlinear static system are provided to show that the proposed method is much more accurate than other modeling methods. Thus, it can be considered for efficient system identification methodology. [Copyright &y& Elsevier]

Abstract: In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages. [Copyright &y& Elsevier]

Abstract: Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that allow the representation of conflicting signals or alternative evolutionary histories in a single diagram. Recently the Quartet-Net or “QNet” method was introduced, a method for computing a special kind of phylogenetic network called a split network from a collection of weighted quartet trees (i.e. phylogenetic trees with 4 leaves). This can be viewed as a quartet analogue of the distance-based Neighbor-Net (NNet) method for constructing outer-labeled planar split networks. In this paper, we prove that QNet is a consistent method, that is, we prove that if QNet is applied to a collection of weighted quartets arising from a circular split weight function, then it will return precisely this function. This key property of QNet not only ensures that it is guaranteed to produce a tree if the input corresponds to a tree, and an outer-labeled planar split network if the input corresponds to such a network, but also provides the main guiding principle for the design of the method. [Copyright &y& Elsevier]

Online mining of path traversal patterns from Web click-streams is one of the most important problems of Web usage mining. In this paper, we propose a sliding window-based Web data mining algorithm, called Top-SW (Top-k path traversal patterns of Stream sliding Window), to discover the set of top-k path traversal patterns from streaming maximal forward references, where k is the desired number of path traversal patterns to be mined. A new summary data structure, called Top-list (a list of Top-k path traversal patterns) is developed to maintain the essential information about the top-k path traversal patterns from the current maximal forward references stream. Experimental studies show that the proposed Top-SW algorithm is an efficient, single-pass algorithm for mining the set of top-k path traversal patterns from a continuous stream of maximal forward references. [Copyright &y& Elsevier]

Abstract: This paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in time with space, and in time with space, respectively, where is the size of the input SLP-compressed strings. [Copyright &y& Elsevier]

Abstract: Given a set of elements, a family of subsets of , and a connected graph on vertex set ,a connected set cover (CSC) is a subfamily of such that every element in is covered by at least one set of , and the subgraph of induced by is connected. If furthermore is -connected and every element in is covered by at least sets in , then is a -CSC. In this paper, we present two approximation algorithms for the minimum CSC problem, and one approximation algorithm for the minimum -CSC problem. Performance ratios are analyzed. These are the first approximation algorithms for CSC problems in general graphs with guaranteed performance ratios. [Copyright &y& Elsevier]

Abstract: The least significant digit first decomposition of integer vectors into words of digit vectors provides a natural way for representing sets of integer vectors by automata. In this paper, the minimal automata representing Presburger sets are proved structurally Presburger: automata obtained by moving the initial state and replacing the accepting condition represent Presburger sets. [Copyright &y& Elsevier]

Abstract: In [R.J. Corin, J.I. den Hartog, A probabilistic hoare-style logic for game-based cryptographic proofs, in: M. Bugliesi, B. Preneel, V. Sassone (Eds.), ICALP 2006 Track C, Venice, Italy, in: Lecture Notes in Computer Science, vol. 4052, Springer-Verlag, Berlin, 2006, pp. 252–263] we build a formal verification technique for game-based correctness proofs of cryptographic algorithms based on a probabilistic Hoare style logic [J.I. den Hartog, E.P. de Vink, Verifying probabilistic programs using a Hoare like logic, International Journal of Foundations of Computer Science 13 (3) (2002) 315–340]. An important step towards enabling mechanized verification within this technique is an axiomatization of implication between predicates which is purely semantically defined in the latter reference cited above. In this paper we provide an axiomatization and illustrate its place in the formal verification technique given in the former. [Copyright &y& Elsevier]

Abstract: A data stream is a massive, open-ended sequence of data elements continuously generated at a rapid rate. Mining data streams is more difficult than mining static databases because the huge, high-speed and continuous characteristics of streaming data. In this paper, we propose a new one-pass algorithm called DSM-MFI (stands for Data Stream Mining for Maximal Frequent Itemsets), which mines the set of all maximal frequent itemsets in landmark windows over data streams. A new summary data structure called summary frequent itemset forest (abbreviated as SFI-forest) is developed for incremental maintaining the essential information about maximal frequent itemsets embedded in the stream so far. Theoretical analysis and experimental studies show that the proposed algorithm is efficient and scalable for mining the set of all maximal frequent itemsets over the entire history of the data streams. [Copyright &y& Elsevier]

In this paper, a (k , n , m) -intragroup and intergroup secret image sharing (I 2 SIS) scheme for the multi-group (i.e., m -group) environment is investigated. (2 m − 1) secret images are shared within groups (intragroups) and between groups (intergroups). Differing from existing SIS methods, any k or more qualified participants among different groups (i.e., intergroup) can collaboratively recover the respective secret image via the homomorphic Lagrange interpolation. The proposed scheme consists of three major procedures: preprocessing, sharing, and recovering. In the preprocessing procedure, an approach is designed to partition the coefficients in the m (k − 1) -degree polynomials for sharing the (2 m − 1) secret images. In addition, an optimal algorithm for the preprocessing is given to let all the percentages of recovering secret images be the same as possible. Shadows belonging to all participants in the m groups are generated in the sharing procedure. In the recovering procedure, the secret images can be reconstructed in intragroups and intergroups. Moreover, experiments and comparisons are demonstrated to show the merits of the proposed scheme. [ABSTRACT FROM AUTHOR]

Abstract: Phylogenetic networks are a restricted class of directed acyclic graphs that model evolutionary histories in the presence of reticulate evolutionary events, such as horizontal gene transfer, hybrid speciation, and recombination. Characterizing a phylogenetic network as a collection of trees and their branches has long been the basis for several methods of reconstructing and evaluating phylogenetic networks. Further, these characterizations have been used to understand molecular sequence evolution on phylogenetic networks. In this paper, we address theoretical questions with regard to phylogenetic networks, their characterizations, and sequence evolution on them. In particular, we prove that the problem of deciding whether a given tree is contained inside a network is NP-complete. Further, we prove that the problem of deciding whether a branch of a given tree is also a branch of a given network is polynomially equivalent to that of deciding whether the evolution of a molecular character (site) on a network is governed by the infinite site model. Exploiting this equivalence, we establish the NP-completeness of both problems, and provide a parameterized algorithm that runs in time , where is the total number of nodes and is the number of recombination nodes in the network, which significantly improves upon the trivial brute-force time algorithm for the problem. This reduction in time is significant, particularly when analyzing recombination hotspots. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the undirected version of the well known maximum edge-disjoint paths problem, restricted to complete graphs. We propose an off-line 3.75-approximation algorithm and an on-line 6.47-approximation algorithm, improving the earlier 9-approximation algorithm proposed by Carmi, Erlebach, and Okamoto [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143–155]. Moreover, we show that for the general case, no on-line algorithm is better than a -approximation, for all . For the special case when the number of paths is within a linear factor of the number of vertices of the graph, it is established that the problem can be optimally solved in polynomial time by an off-line algorithm, but that no on-line algorithm is better than a -approximation. Finally, the proposed techniques are used to obtain off-line and on-line algorithms with a constant approximation ratio for the related problems of edge congestion routing and wavelength routing in complete graphs. [Copyright &y& Elsevier]

Abstract: This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with nodes. All previous deterministic distributed algorithms, for constant stretch spanners of edges, have a running time for some constant depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of edges in time for any constant . More precisely, in Linial’s free model a.k.a model, we construct in time, for every graph, a -spanner of edges, i.e., a spanning subgraph in which the distance is at most 3 times the distance of the original graph plus 2. The result is extended to -spanners with edges for every integer parameter , where . If the minimum degree of the graph is , then, in the same time complexity, a -spanner with edges can be constructed. [Copyright &y& Elsevier]

Abstract: In “Can we elect if we cannot compare” (SPAA’03), Barrière, Flocchini, Fraigniaud and Santoro consider a qualitative model of distributed computing, where the labels of the entities are distinct but mutually incomparable. They study the leader election problem in a distributed mobile environment and they wonder whether there exists an algorithm such that for each distributed mobile environment, it either states that the problem cannot be solved in this environment, or it successfully elects a leader. In this paper, we give a positive answer to this question. We also give a characterization of the distributed mobile environments where election and rendezvous can be solved. [Copyright &y& Elsevier]

Abstract: The longest common subsequence (LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we introduce new variants of LCS problem and present efficient algorithms to solve them. In particular we introduce the notion of gap constraints in the LCS problems. For the LCS problem with fixed gap, we first present a naive algorithm runs in time, where is the total number of ordered pairs of positions at which the two strings match and is the fixed gap constraint. We then improve the running time to using some novel techniques. Furthermore, we present an algorithm that is independent of and runs in time. Using these techniques, we also present a new algorithm to solve the original LCS problem. Additionally, we modify our algorithms to handle elastic and rigid gaps. We also apply the notion of rigidness to the original LCS problem and modify the traditional dynamic programming solution to handle the rigidness presenting a algorithm to solve the problem. Finally, we also improve the solution to Rigid Fixed Gap LCS to . Notably, in all of the above cases, we assume that the two given strings are of equal length i.e. . But our results can be easily extended to handle two strings of different length. [Copyright &y& Elsevier]

Abstract: Many well-known problems in Artificial Intelligence can be formulated in terms of systems of constraints. The problem of testing the satisfiability of propositional formulae (SAT) is of special importance due to its numerous applications in theoretical computer science and Artificial Intelligence. A brute-force algorithm for SAT will have exponential time complexity , where is the number of Boolean variables of the formula. Unfortunately, more sophisticated approaches such as resolution result in similar performances in the worst case. In this paper, we present a simple and relatively efficient parallel divide-and-conquer method to solve various subclasses of SAT. The dissection stage of the parallel algorithm splits the original formula into smaller subformulae with only a bounded number of interacting variables. In particular, we derive a parallel algorithm for the class of formulae whose corresponding graph representation is planar. Our parallel algorithm for planar 3-SAT has the worst-case performance of on a PRAM (parallel random access model) computer. Applications of our method to constraint satisfaction problems are discussed. [Copyright &y& Elsevier]

Abstract: For a set of points (terminals) in the plane, a Manhattan network on is a network with the property that its edges are horizontal or vertical segments connecting points in and for every pair of terminals, the network contains a shortest -path between them. A minimum Manhattan network on is a Manhattan network of minimum possible length. The problem of finding minimum Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan [J. Gudmundsson, C. Levcopoulos, G. Narasimhan, Approximating a minimum Manhattan network, Nordic Journal of Computing 8 (2001) 219–232. Proc. APPROX’99, 1999, pp. 28–37] and its complexity status is unknown. Several approximation algorithms (with factors 8, 4, and 3) have been proposed; recently Kato, Imai, and Asano [R. Kato, K. Imai, T. Asano, An improved algorithm for the minimum Manhattan network problem, ISAAC’02, in: LNCS, vol. 2518, 2002, pp. 344–356] have given a factor 2-approximation algorithm, however their correctness proof is incomplete. In this paper, we propose a rounding 2-approximation algorithm based on an LP-formulation of the minimum Manhattan network problem. [Copyright &y& Elsevier]

Abstract: Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have proved to be very useful in constructing small universal (Turing complete) systems for several different classes of computational systems, including Turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. Although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both the shift number and the number of symbols . This paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. The main result is the reduction of the -problem to a surprisingly small tag system. It indicates that the present unsolvability line–defined in terms of and –for tag systems might be significantly decreased. [Copyright &y& Elsevier]

Abstract: Let be a connected graph such that each edge is weighted by nonnegative real . Let be a vertex designated as a source, be a positive integer, and be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition of and a set of trees of such that consists of at most terminals and each spans . The objective is to minimize , where denotes the sum of weights of all edges in . In this paper, we propose a -approximation algorithm to the CMTR, where is the best achievable approximation ratio for the Steiner tree problem. [Copyright &y& Elsevier]

Abstract: Efficient string-processing in large data sets like complete genomes is strongly connected to the suffix tree and similar index data structures. With respect to complex structural string analysis like the search for RNA secondary structure patterns, unidirectional suffix tree algorithms are inferior to bidirectional algorithms based on the affix tree data structure. The affix tree incorporates the suffix tree and the suffix tree of the reverse text in one tree structure but suffers from its large memory requirements. In this paper I present a new data structure, denoted affix array, which is equivalent to the affix tree with respect to its algorithmic functionality, but with smaller memory requirements and improved performance. I will show a linear time construction of the affix array without making use of the linear time construction of the affix tree. I will also show how bidirectional affix tree traversals can be transferred to the affix array and present the impressive results of large scale RNA secondary structure analysis based on the new data structure. [Copyright &y& Elsevier]

Abstract: In this paper, we study the problem of finding the shortest path between two points inside a simple polygon such that there is at least one point on the path from which a query point is visible. We provide an algorithm which preprocesses the input in time and space and provides logarithmic query time. The input polygon has vertices and is a parameter dependent on the input polygon which is in the worst case but is much smaller for most polygons. The preprocessing algorithm sweeps an angular interval around every reflex vertex of the polygon to store the optimal contact points between the shortest paths and the windows separating the visibility polygons of the query points from the source and the destination. [Copyright &y& Elsevier]

Abstract: Fuzzy adaptive equalizers (FAEs) are adaptive equalizers that apply the concepts of fuzzy logic. The main merit of applying FAEs in powerline channel equalization is that linguistic information (fuzzy IF–THEN rules) and numerical information (input–output pairs) can be combined into the equalizers. The adaptive algorithms adjust the parameters of the membership functions which characterize the fuzzy concepts in the IF–THEN rules, by minimizing some criterion function. In this paper, we propose a new FAE, using the extended Kalman filter (EKF) algorithm for powerline channel equalization. The simulation results show that the EKF-based FAE has lower steady state bit error rate (BER) and faster convergent speed compared to decision feedback recursive least-squares adaptive equalizer, recursive least squares (RLS) based FAE and least mean squares (LMS) based FAE. We also propose a robust improvement scheme for the new FAE. Simulation results show that the performance of the proposed robust FAE is improved in powerline channel equalization and outperforms all the equalizers considered above. The BER of the proposed scheme is very close to the optimum performance. [Copyright &y& Elsevier]

Abstract: In this paper, a neuro-fuzzy network with novel hybrid learning algorithm is proposed. The novel hybrid learning algorithm is based on the fuzzy entropy clustering (FEC), the modified particle swarm optimization (MPSO), and the recursive singular value decomposition (RSVD). The FEC is used to partition the input data for performing structure learning. Then, we adopt the MPSO to adjust the antecedent parameters of fuzzy rules. Two strategies in the MPSO, called the effective local approximation method (ELAM) and the multi-elites strategy (MES), are proposed to improve the performance of the traditional PSO. Moreover, we will apply RSVD to obtain the optimal consequent parameters of fuzzy rules. The proposed hybrid learning algorithm achieves superior performance in learning speed and learning accuracy than those of some traditional genetic methods. [Copyright &y& Elsevier]

The deep connection between the Burrows–Wheeler transform (BWT) and the so-called rank and select data structures for symbol sequences is the basis of most successful approaches to compressed text indexing. Rank of a symbol at a given position equals the number of times the symbol appears in the corresponding prefix of the sequence. Select is the inverse, retrieving the positions of the symbol occurrences. It has been shown that improvements to rank/select algorithms, in combination with the BWT, turn into improved compressed text indexes. This paper is devoted to alternative implementations and extensions of rank and select data structures. First, we show that one can use gap encoding techniques to obtain constant time rank and select queries in essentially the same space as what is achieved by the best current direct solution (and sometimes less). Second, we extend symbol rank and select to substring rank and select, giving several space/time trade-offs for the problem. An application of these queries is in position-restricted substring searching, where one can specify the range in the text where the search is restricted to, and only occurrences residing in that range are to be reported. In addition, arbitrary occurrences are reported in text position order. Several byproducts of our results display connections with searchable partial sums, Chazelle’s two-dimensional data structures, and Grossi et al.’s wavelet trees. [Copyright &y& Elsevier]

Abstract: In this paper, we consider one of the most fundamental results on the periodicity of words, namely the critical factorization theorem. Given a word and nonempty words satisfying , the minimal local period associated with the factorization is the length of the shortest square at position . The critical factorization theorem shows that for any word, there is always a factorization whose minimal local period is equal to the minimal period (or global period) of the word. Crochemore and Perrin presented a linear time algorithm (in the length of the word) that finds a critical factorization from the computation of the maximal suffixes of the word with respect to two total orderings on words: the lexicographic ordering related to a fixed total ordering on the alphabet, and the lexicographic ordering obtained by reversing the order of letters in the alphabet. Here, by refining Crochemore and Perrin’s algorithm, we give a version of the critical factorization theorem for partial words (such sequences may contain “do not know” symbols or “holes”). Our proof provides an efficient algorithm which computes a critical factorization when one exists. Our results extend those of Blanchet-Sadri and Duncan for partial words with one hole. A World Wide Web server interface at http://www.uncg.edu/mat/research/cft2/ has been established for automated use of the program. [Copyright &y& Elsevier]

Abstract: We consider semistructured data as multirooted edge-labelled directed graphs, and path inclusion constraints on these graphs. A path inclusion constraint is satisfied by a semistructured data if any node reached by the regular query is also reached by the regular query . In this paper, two problems are mainly studied: the implication problem and the problem of the existence of a finite exact model. [–] We give a new decision algorithm for the implication problem of a constraint by a set of bounded path constraints where , , and the ’s are regular path expressions and the ’s are words, improving in this particular case, the more general algorithms of S. Abiteboul and V. Vianu, and N. Alechina et al. In the case of a set of word equalities , we provide a more efficient decision algorithm for the implication of a word equality , improving the more general algorithm of P. Buneman et al. We prove that, in this case, implication for nondeterministic models is equivalent to implication for (complete) deterministic ones. [–] We introduce the notion of exact model: an exact model of a set of path constraints satisfies the constraint if and only if this constraint is implied by . We prove that any set of constraints has an exact model and we give a decidable characterization of data which are exact models of bounded path inclusion constraints sets. [Copyright &y& Elsevier]

Line flow or real-power contingency selection and ranking is performed to choose the contingencies that cause the worst overloading problems. In this paper, a cascade neural network-based approach is proposed for fast line flow contingency selection and ranking. The developed cascade neural network is a combination of a filter module and a ranking module. All the contingency cases are applied to the filter module, which is trained to classify them either in critical contingency class or in non-critical contingency class using a modified BP algorithm. The screened critical contingencies are passed to the ranking module (four-layered feed-forward artificial neural network (ANN)) for their further ranking. Effectiveness of the proposed ANN-based method is demonstrated by applying it for contingency screening and ranking at different loading conditions for IEEE 14-bus system. Once trained, the cascade neural network gives fast and accurate screening and ranking for unknown patterns and is found to be suitable for on-line applications at energy management centre. [Copyright &y& Elsevier]

We consider a two-edge connected, undirected graph , with nodes and non-negatively real weighted edges, and a single source shortest paths tree (SPT) of rooted at an arbitrary node . If an edge in is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge, instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an time and space algorithm to find a best swap edge for every edge of , thus improving for the previously known time and space complexity algorithm. [Copyright &y& Elsevier]

Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. We give a learning algorithm in the exact model with equivalence queries for such classes. This algorithm utilizes a novel encoding scheme, which we call a signature. [Copyright &y& Elsevier]

Abstract: A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time). [Copyright &y& Elsevier]

Abstract: One-way functions are a fundamental notion in cryptography, since they are the necessary condition for the existence of secure encryption schemes. Most examples of such functions, including Factoring, Discrete Logarithm or the RSA function, however, can be inverted with the help of a quantum computer. Hence, it is very important to study the possibility of quantum one-way functions, i.e. functions which are easily computable by a classical algorithm but are hard to invert even by a quantum adversary. In this paper, we provide a set of problems that are good candidates for quantum one-way functions. These problems include Graph Non-Isomorphism, Approximate Closest Lattice Vector and Group Non-Membership. More generally, we show that any hard instance of Circuit Quantum Sampling gives rise to a quantum one-way function. By the work of Aharonov and Ta-Shma [D. Aharonov, A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, in: Proceedings of STOC02 — Symposium on the Theory of Computing, 2001], this implies that any language in Statistical Zero Knowledge which is hard-on-average for quantum computers leads to a quantum one-way function. Moreover, extending the result of Impagliazzo and Luby [R. Impagliazzo, M. Luby, One-way functions are essential for complexity based cryptography, in: Proceedings of FOCS89 — Symposium on Foundations of Computer Science, 1989] to the quantum setting, we prove that quantum distributionally one-way functions are equivalent to quantum one-way functions. [Copyright &y& Elsevier]

Abstract: A partial function is called a simple function if is the output produced in the leftmost derivation of a word from a nonterminal of a simple context free grammar with output alphabet . In this paper we present an efficient algorithm for testing the equivalence of simple functions. Such functions correspond also to one-state deterministic pushdown transducers. Our algorithm works in time polynomial with respect to , where is the size of the textual description of , and is the maximum of the shortest lengths of words generated by nonterminals of . [Copyright &y& Elsevier]

Abstract: Given a graph , the problem is to determine an acyclic orientation of which minimizes the maximal number of changes of orientation along any shortest path in . The corresponding value is called the rank of the graph . The motivation for this graph theoretical problem comes from the design of deadlock-free packet routing protocols [G. Tel, Deadlock-free packet switching networks, in: Introduction to Distributed Algorithms, Cambridge University Press, Cambridge, UK, 1994 (Chapter 5)]. This acyclic orientation covering problem on the shortest path systems has been studied in [J.-C. Bermond, M. Di Ianni, M. Flammini, S. Perennes, Acyclic orientations for deadlock prevention in interconnection networks, in: 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), in: Lecture Notes in Computer Science, vol. 1335, Springer-Verlag, 1997, pp. 52–64] where it was shown that the general problem of determining the rank is NP-complete and some upper and lower bounds on the rank were presented for particular topologies, such as grids, tori and hypercubes. The main unresolved problem stated in [J.-C. Bermond, M. Di Ianni, M. Flammini, S. Perennes, Acyclic orientations for deadlock prevention in interconnection networks, in: 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), in: Lecture Notes in Computer Science, vol. 1335, Springer-Verlag, 1997, pp. 52–64] was to determine the rank values for other well-known interconnection networks and also for more general classes of graphs. In this paper we give a general lower bound argument for the rank problem and apply it to the class of involution-generated Cayley graphs which among others include hypercubes, star graphs, pancake graphs and transposition-tree based graphs [S.B. Akers, B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38 (4) (1989) 555–565]. We also present a large class of graphs with constant rank. This class of graphs is defined as the layered cross product [S. Even, A. Litman, Layered cross product—A technique to construct interconnection networks, Networks 29 (1997) 219–223] of layered trees and series–parallel graphs and includes among others butterflies, Beneš networks, fat-trees and meshes of trees. For some special topologies, improved lower bounds on the rank are also presented. We consider some of the modified versions of the rank problem as well. [Copyright &y& Elsevier]

Array P systems were introduced by Pǎun Gh. which is linking the two areas of membrane computing and picture grammars. Puzzle grammars were introduced by us for generating connected picture arrays in the two-dimensional plane, motivated by the problem of tiling the plane. On the other hand, incorporating into arrays the developmental type of generation used in the well-known biologically motivated L systems, Siromoney and Siromoney proposed a very general rectangular array generating model, called extended controlled tabled L array system (ECTLAS). In this paper we introduce two variations of the array P system, called BPG array P system and parallel array P system. The former has in the regions array objects and basic puzzle grammar rules (BPG), which are a specific kind of puzzle grammar rules. In the latter, the regions have rectangular array objects and tables of context-free rules. We examine these two types of P systems for their array generative power. [ABSTRACT FROM AUTHOR]

Abstract: Most approaches to time granularity proposed in the literature are based on algebraic and logical formalisms [J. Euzenat, A. Montanari, Time granularity, in: M. Fisher, D. Gabbay, L. Vila (Eds.), Handbook of Temporal Reasoning in Artificial Intelligence, Elsevier, 2005, pp. 59–118]. Here we follow an alternative automaton-based approach, originally outlined in [U. Dal Lago, A. Montanari, Calendars, time granularities, and automata, in: Proceedings of the 7th International Symposium on Spatial and Temporal Databases, SSTD, in: LNCS, vol. 2121, Springer, 2001, pp. 279–298], which makes it possible to deal with infinite time granularities in an effective and efficient way. Such an approach provides a neat solution to fundamental algorithmic problems, such as the granularity equivalence and granule conversion problems, which have been often neglected in the literature. In this paper, we focus our attention on two basic optimization problems for the automaton-based representation of time granularities, namely, the problem of computing the smallest representation of a time granularity and that of computing the most tractable representation of it, that is, the one on which crucial algorithms, such as granule conversion algorithms, run fastest. [Copyright &y& Elsevier]

Abstract: This paper proposes a new algorithm for a class of binary images thinning by using two PCNNs (pulse coupled neural networks). Once the travelling pulses of the two PCNNs meet, the thinning result is obtained. The criterion of pulses meeting is given, and the parameters of the PCNNs are also specified, which make the implementation of the proposed thinning algorithm easier. The algorithm is used to thin such a class of binary images, which separate the original images into two regions, as circularity-like images and ribbon-like shapes. Experimental results show that the proposed algorithm is efficient in extracting the skeleton of images (such as circularity-like images, ribbon-like shapes, handwriting ‘0’, etc.). [Copyright &y& Elsevier]

Abstract: Given a sequence of real numbers and an integer , , the maximum-sum segments problem is to locate the segments whose sums are the largest among all possible segment sums. Recently, Bengtsson and Chen gave an -time algorithm for this problem. Bae and Takaoka later proposed a more efficient algorithm for small . In this paper, we propose an -time algorithm for the same problem, which is superior to both of them when is . We also give the first optimal algorithm for delivering the maximum-sum segments in non-decreasing order if . Then we develop an -time algorithm for the -dimensional version of the problem, where and each dimension, without loss of generality, is of the same size . This improves the best previously known -time algorithm, also by Bengtsson and Chen, where . It should be pointed out that, given a two-dimensional array of size , our algorithm for finding the maximum-sum subarrays is the first one achieving cubic time provided that is . [Copyright &y& Elsevier]

Abstract: Usually, for bin packing problems, we try to minimize the number of bins used or in the case of the dual bin packing problem, maximize the number or total size of accepted items. This paper presents results for the opposite problems, where we would like to maximize the number of bins used or minimize the number or total size of accepted items. We consider off-line and on-line variants of the problems. For the off-line variant, we require that there be an ordering of the bins, so that no item in a later bin fits in an earlier bin. We find the approximation ratios of two natural approximation algorithms, First-Fit-Increasing and First-Fit-Decreasing for the maximum resource variant of classical bin packing. For the on-line variant, we define maximum resource variants of classical and dual bin packing. For dual bin packing, no on-line algorithm is competitive. For classical bin packing, we find the competitive ratio of various natural algorithms. We study the general versions of the problems as well as the parameterized versions where there is an upper bound of on the item sizes, for some integer k. [Copyright &y& Elsevier]

Abstract: It is necessary to remove the noise in EEG before further EEG analysis and processing. For EEG is deeply masked in the noise background, it is very difficult to denoise EEG effectively. Proposed in this paper is a novel realistic head model based sparse decomposition algorithm to denoise EEG, which is an iterative procedure combining the subject''s physiology of EEG generation into the denoising procedure. In this algorithm, the lead field overcomplete dictionary is numerically calculated according to the realistic head model firstly, and then the instantaneous EEG spatial potential is decomposed into one sparse combination of atoms in the lead field matrix by matching pursuit, and the sparse combination of atoms is to be regarded as the denoised EEG signal. The realistic head based sparse decomposition was tested by the simulated noisy potential and a real EEG recording collected in an oddball stimulus experiment, the results consistently confirmed the new method removed the uncorrelated noise in EEG effectively. [Copyright &y& Elsevier]