Search

Abstract: In this paper we have addressed the problem of finding a path through a maze of a given size. The traditional ways of finding a path through a maze employ recursive algorithms in which unwanted or non-paths are eliminated in a recursive manner. Neural networks with their parallel and distributed nature of processing seem to provide a natural solution to this problem. We present a biologically inspired solution using a two level hierarchical neural network for the mapping of the maze as also the generation of the path if it exists. For a maze of size S the amount of time it takes would be a function of S (O(S)) and a shortest path (if more than one path exists) could be found in around S cycles where each cycle involves all the neurons doing their processing in a parallel manner. The solution presented in this paper finds all valid paths and a simple technique for finding the shortest path amongst them is also given. The results are very encouraging and more applications of the network setup used in this report are currently being investigated. These include synthetic modeling of biological neural mechanisms, traversal of decision trees, modeling of associative neural networks (as in relating visual and auditory stimuli of a given phenomenon) and surgical micro-robot trajectory planning and execution. [Copyright &y& Elsevier]

Wearable computing has recently gained much popularity as an ambitious vision for future personalized mobile systems. Its aim is intelligent, environment aware systems unobtrusively embedded into the mobile environments of their users. With the combination of complex processing requirements, the necessity of placing sensors and input/output modules at different locations on the user's body, and stringent limits on size, weight, and battery capacity, the design of such systems is an inherently challenging problem. This paper demonstrates how systematic design and quantitative analysis can be applied to wearable architectures. We first present a model that allows various factors influencing the design of a wearable system to be incorporated into formal cost metrics. In particular, we show how to consistently incorporate specific wearable factors such as device placement requirements, ergonomics, and dynamic workload profiles into the model. We then discuss how efficient estimation algorithms can be extended and applied to the evaluation of different architectures with respect to our cost metrics. Finally, we discuss quantitative results from a proof-of-concept case study showing the trade offs between different architectures for a given wearable scenario. Summarized, this paper demonstrates how the description and the design of wearable systems can be put on a systematic, formal basis allowing us to treat them similar as conventional embedded systems. [ABSTRACT FROM AUTHOR]

The paper presents the pheromone-Q-learning (Phe-Q) algorithm, a variation of Q-learning. The technique was developed to allow agents to communicate and jointly learn to solve a problem. Phe-Q learning combines the standard Q-learning technique with a synthetic pheromone that acts as a communication medium speeding up the learning process of cooperating agents. The Phe-Q update equation includes a belief factor that reflects the confidence an agent has in the pheromone (the communication medium) deposited in the environment by other agents. With the Phe-Q update equation, the speed of convergence towards an optimal solution depends on a number of parameters including the number of agents solving a problem, the amount of pheromone deposit, the diffusion into neighbouring cells and the evaporation rate. The main objective of this paper is to describe and evaluate the performance of the Phe-Q algorithm. The paper demonstrates the improved performance of cooperating Phe-Q agents over non-cooperating agents. The paper also shows how Phe-Q learning can be improved by optimizing all the parameters that control the use of the synthetic pheromone. [ABSTRACT FROM AUTHOR]

This paper focuses on image filtering using weighted median (WM) filters, a nonlinear filter class taking advantages of the robust order-statistic theory and capability to adapt a filter behavior for a variety of statistics related to the desired signals and the noise distributions. The main contribution of the paper is the analysis of the four WM optimization schemes, namely genetic WM optimization, non-adaptive WM optimization algorithm and adaptive WM filtering utilizing the linear and the sigmoidal approximation of the sign function. The analysis is done by extensive simulations, in which several features such as noise reduction, edge preservation, error estimation and dependence of error criteria on the degree of the impulse noise corruption, are examined. [ABSTRACT FROM AUTHOR]

This paper discusses the multicast routing problem with QoS constraints, and describes a network model that is suitable to research such routing problem. The paper mainly presents a distributed QoS-aware multicast routing protocol (QMRP). The QMRP can operate on top of the unicast routing protocol. It only requires the local state information of the link (or the node), but does not require any global network state to be maintained. The QMRP can significantly reduce the overhead for constructing a multicast tree with QoS constraints. In QMRP, a multicast group member can join or leave the multicast session dynamically, which can support dynamic membership. The protocol can search multiple feasible tree branches, and select the optimal or near-optimal branch for connecting the new receiver to the multicast tree if it exists. In this paper, the proof of correctness and complexity analysis of the QMRP are given, and the performance measures of the protocol are evaluated using simulation. The study shows that QMRP provides an available approach to multicast routing with QoS constraints and dynamic membership support. [ABSTRACT FROM AUTHOR]

The session problem is an abstraction of fundamental synchronization problems in distributed systems. It has previously been used as a test case to demonstrate the differences in the time needed to solve problems in several timing models. The goal of this paper is to compare the computational power of a family of partially synchronous models by studying the time needed to solve the session problem. Four timing parameters are considered: the maximum and minimum process step times and message delays. Timing models are obtained by considering independently whether each parameter is known (i.e., is hard-wired into the processes' code) or unknown, giving rise to four shared memory models and 16 message passing models. The models are compared based on the time complexity, measured in real time, of the session problem. This paper presents a modular proof technique for obtaining asymptotically tight bounds on the time complexity of the session problem for the four shared memory models and the 16 message passing models. Timing information known in each particular model can be exploited by algorithms to count sessions in different ways. This paper reports five different counting algorithms. The matching lower bound for each model suggests that they are the optimal ways to count sessions. Based on these bounds, a lattice among unknown parameter models is constructed, which confirms the common belief that as more timing information is known in a model, the model behaves more like a synchronous system. [ABSTRACT FROM AUTHOR]

Overlapping communication with computation is a well-known approach to improving performance. Previous research has focused on optimizations performed by the programmer. This paper presents a compiler algorithm that automatically determines the appropriate loop indices of a given nested loop and applies loop interchange and tiling in order to overlap communication with computation. The algorithm avoids generating redundant communication by providing a framework for combining information on data dependence, communication, and reuse. It also describes a method of generating messages to exchange data between processors for tiled loops on distributed memory machines. The algorithm has been implemented in our High Performance Fortran (HPF) compiler, and experimental results have shown its effectiveness on distributed memory machines, such as the RISC System/6000 Scalable POWERparallel System. This paper also discusses the architectural problems of efficient optimization. [ABSTRACT FROM AUTHOR]

One of the popular metaheuristic search algorithms is Harmony Search (HS). It has been verified that HS can find solutions to optimization problems due to its balanced exploratory and convergence behavior and its simple and flexible structure. This capability makes the algorithm preferable to be applied in several real-world applications in various fields, including healthcare systems, different engineering fields, and computer science. The popularity of HS urges us to provide a comprehensive survey of the literature on HS and its variants on health systems, analyze its strengths and weaknesses, and suggest future research directions. In this review paper, the current studies and uses of harmony search are studied in four main domains. (i) The variants of HS, including its modifications and hybridization. (ii) Summary of the previous review works. (iii) Applications of HS in healthcare systems. (iv) And finally, an operational framework is proposed for the applications of HS in healthcare systems. The main contribution of this review is intended to provide a thorough examination of HS in healthcare systems while also serving as a valuable resource for prospective scholars who want to investigate or implement this method. [ABSTRACT FROM AUTHOR]

This paper introduces m -inductiveness over a set of nodes S in sequential circuits. The m -inductive property can be used for equivalence-checking or improved sequential optimization. It allows the behavior of many next state functions (not in S ) to be changed while maintaining correctness at the primary outputs of a circuit. As such, it creates flexibility that can be used for sequential optimization. It is shown that the number of nodes in S is reduced as m, the parameter for the inductiveness, increases. We provide an algorithm for finding a minimal set S , as well as one for using m -inductiveness in optimization. We give examples of such optimized circuits and show that m -inductive-based optimization can result in significant area reduction when applied to industrial designs. [ABSTRACT FROM AUTHOR]

A slap fingerprint based verification system generally is highly secure. But it cannot handle the problems of temporal deformation and pose variation. In this paper, a template update algorithm has been proposed to ensure better performance of the system. During verification, each single fingerprint is matched and matching scores of all fingerprints are fused using an adaptive score level fusion. The performance of the proposed system has been evaluated on a challenging database containing 1800 slap-images acquired from 150 subjects. Experimental results show that the accuracy is increased by more than 3.5%. [ABSTRACT FROM AUTHOR]

Traditional optimization algorithms for blind signal separation (BSS) are mainly based on the gradient, which requires the objective function to be continuous and differentiable, so the applications of these algorithms are very limited. Moreover, these algorithms have problems with the convergence speed and accuracy. To overcome these drawbacks, this paper presents a modified glowworm swarm optimization (MGSO) algorithm based on a novel step adjustment rule and then applies MGSO to BSS. Taking kurtosis of the mixed signals as the objective function of BSS, MGSO-BSS succeeds in separating the mixed signals in Matlab environment. The simulation results prove that MGSO is more effective in capturing the global optimum of the objective function of the BSS algorithm and has faster convergence speed and higher accuracy, compared with particle swarm optimization (PSO) and GSO. [ABSTRACT FROM AUTHOR]

The motif discovery problem (MDP) is an important biological optimization problem that has been addressed in numerous ways. However, it is important to note that when we address real complex optimization problems, we should adequately formulate them in order to provide real applicability to the developed techniques. In the particular case of MDP, as we do not know the size of the motifs and the number of repetitions that can be found in the sequences, we must not make any length or pattern-repetition assumptions. In addition, if we consider that it is practically impossible to adequately formulate an optimization problem with a single-objective function formulation, multiobjective optimization can be a good methodology to be considered. In this paper, we propose a novel hybrid multiobjective algorithm for tackling the MDP. Our main objective is to study the results achieved by our algorithm, analysing its performance when different motif occurrence models are considered. As we will see, experimental results on different sets of real instances will point out the advantages and disadvantages of each model, also checking how a more realistic definition of the optimized problem provides better quality biological results. [ABSTRACT FROM AUTHOR]

Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schönhage in 1982. The main drawbacks of Pan's method are that it is quite involved 2 2 In Victor Pan's own words: “Our algorithms are quite involved, and their implementation would require a non-trivial work, incorporating numerous known implementation techniques and tricks”. In fact, we are not aware of any implementation of Pan's method. and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted A New Dsc , which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. A New Dsc can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task. [ABSTRACT FROM AUTHOR]

The presence of noise in real data sets can harm the predictive performance of machine learning algorithms. There are several noise filtering techniques whose goal is to improve the quality of the data in classification tasks. These techniques usually scan the data for noise identification in a preprocessing step. Nonetheless, this is a non-trivial task and some noisy data can remain unidentified, while safe data can also be removed. The bias of each filtering technique influences its performance on a particular data set. Therefore, there is no single technique that can be considered the best for all domains or data distribution and choosing a particular filter is not straightforward. Meta-learning has been largely used in the last years to support the recommendation of the most suitable machine learning algorithm(s) for a new data set. This paper presents a meta-learning recommendation system able to predict the expected performance of noise filters in noisy data identification tasks. For such, a meta-base is created, containing meta-features extracted from several corrupted data sets along with the performance of some noise filters when applied to these data sets. Next, regression models are induced from this meta-base to predict the expected performance of the investigated filters in the identification of noisy data. The experimental results show that meta-learning can provide a good recommendation of the most promising filters to be applied to new classification data sets. [ABSTRACT FROM AUTHOR]

Anchorgraph based learning methods have met with success in modeling the large data for scalable semi-supervised learning. However, like most graph based learning algorithms, they are usually built with a randomly selected labeled set classified in advance. Although many pool-based active learning methods have been proposed, they often require a relatively large computational and storage consumption, which tends to impose extra burden on the learning system. Thus in this paper, we propose a novel active learning method named anchor-based transductive experimental design (ATED). By fully utilizing the representing power of anchors, the improved method efficiently enhances the performance of the original anchorgraph based learning while introduces much less extra cost on computation and storage. Extensive experimental results on real-world datasets have validated our approach in terms of classifying accuracy and computational efficiency. [ABSTRACT FROM AUTHOR]

In classification, noise may deteriorate the system performance and increase the complexity of the models built. In order to mitigate its consequences, several approaches have been proposed in the literature. Among them, noise filtering, which removes noisy examples from the training data, is one of the most used techniques. This paper proposes a new noise filtering method that combines several filtering strategies in order to increase the accuracy of the classification algorithms used after the filtering process. The filtering is based on the fusion of the predictions of several classifiers used to detect the presence of noise. We translate the idea behind multiple classifier systems, where the information gathered from different models is combined, to noise filtering. In this way, we consider the combination of classifiers instead of using only one to detect noise. Additionally, the proposed method follows an iterative noise filtering scheme that allows us to avoid the usage of detected noisy examples in each new iteration of the filtering process. Finally, we introduce a noisy score to control the filtering sensitivity, in such a way that the amount of noisy examples removed in each iteration can be adapted to the necessities of the practitioner. The first two strategies (use of multiple classifiers and iterative filtering) are used to improve the filtering accuracy, whereas the last one (the noisy score) controls the level of conservation of the filter removing potentially noisy examples. The validity of the proposed method is studied in an exhaustive experimental study. We compare the new filtering method against several state-of-the-art methods to deal with datasets with class noise and study their efficacy in three classifiers with different sensitivity to noise. [ABSTRACT FROM AUTHOR]

Community detection in a social network is a well-known problem that has been studied in computer science since early 2000. The algorithms available in the literature mainly follow two strategies, one, which allows a node to be a part of multiple communities with equal membership, and the second considers a disjoint partition of the whole network where a node belongs to only one community. In this paper, we proposed a novel community detection algorithm which identifies fuzzy-rough communities where a node can be a part of many groups with different memberships of their association. The algorithm runs on a new framework of social network representation based on fuzzy granular theory. A new index viz. normalized fuzzy mutual information, to quantify the goodness of detected communities is used. Experimental results on benchmark data show the superiority of the proposed algorithm compared to other well known methods, particularly when the network contains overlapping communities. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of characterizing and exploiting the complete flexibility of a special logic architecture, called P-circuits, which realize a Boolean function by projecting it onto overlapping subsets given by a generalized Shannon decomposition. P-circuits are used to restructure logic by pushing some signals towards the outputs. The algorithms proposed so far for exploiting the structural flexibility of P-circuits do not guarantee to find the best implementation, because they cast the problem as the minimization of an incompletely specified function. Instead, here we show that to explore all solutions we must set up the problem as the minimization of a Boolean relation, because there are don’t care conditions that cannot be expressed by single cubes. Finally we report the results obtained using a minimizer of Boolean relations, which improve in a major way with respect to the previous literature. [ABSTRACT FROM AUTHOR]

In this paper an efficient algorithm is proposed which optimizes periodic message scheduling in a real-time multiprocessor system. The system is based on a many-core single-chip computer architecture and uses a multistage baseline network for inter-core communication. Due to its basic architecture, internal blockings can occur during data transfers, i.e. the baseline network is not real-time capable by itself. Therefore, we propose a scheduling algorithm that may be performed before the execution of an application in order to compute a non-blocking schedule of periodic message transfers. Additionally, we optimize the clock rate of the network subject to the constraint that all data transfers can be performed in a non-blocking way. Our solution algorithm is based on a generalized graph coloring model and a randomized greedy approach. The algorithm was tested on some realistic communication scenarios as they appear in modern electronic car units. Computational results show the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Recommender systems are highly vulnerable to shilling attacks, both by individuals and groups. Attackers who introduce biased ratings in order to affect recommendations, have been shown to negatively affect collaborative filtering (CF) algorithms. Previous research focuses only on the differences between genuine profiles and attack profiles, ignoring the group characteristics in attack profiles. In this paper, we study the use of statistical metrics to detect rating patterns of attackers and group characteristics in attack profiles. Another question is that most existing detecting methods are model specific. Two metrics, Rating Deviation from Mean Agreement (RDMA) and Degree of Similarity with Top Neighbors (DegSim), are used for analyzing rating patterns between malicious profiles and genuine profiles in attack models. Building upon this, we also propose and evaluate a detection structure called RD-TIA for detecting shilling attacks in recommender systems using a statistical approach. In order to detect more complicated attack models, we propose a novel metric called DegSim’ based on DegSim. The experimental results show that our detection model based on target item analysis is an effective approach for detecting shilling attacks. [ABSTRACT FROM AUTHOR]

We consider algorithmic design, enhancement, and improvement of evolutionary computation as a mechanism design problem. All individuals or several groups of individuals can be considered as self-interested agents. The individuals in evolutionary computation can manipulate parameter settings and operations by satisfying their own preferences, which are defined by an evolutionary computation algorithm designer, rather than by following a fixed algorithm rule. Evolutionary computation algorithm designers or self-adaptive methods should construct proper rules and mechanisms for all agents (individuals) to conduct their evolution behaviour correctly in order to definitely achieve the desired and preset objective(s). As a case study, we propose a formal framework on parameter setting, strategy selection, and algorithmic design of evolutionary computation by considering the Nash strategy equilibrium of a mechanism design in the search process. The evaluation results present the efficiency of the framework. This primary principle can be implemented in any evolutionary computation algorithm that needs to consider strategy selection issues in its optimization process. The final objective of our work is to solve evolutionary computation design as an algorithmic mechanism design problem and establish its fundamental aspect by taking this perspective. This paper is the first step towards achieving this objective by implementing a strategy equilibrium solution (such as Nash equilibrium) in evolutionary computation algorithm. [ABSTRACT FROM AUTHOR]

In this paper we find a connection between constructive number fields and computable reals. This connection is applied to prove the computability in the rigorous sense of computable analysis) of solutions of some important systems of partial differential equations, by means of algorithms which are really used in numerical analysis. [ABSTRACT FROM AUTHOR]

In this paper, a self-stabilizing algorithm is presented for finding the articulation points of a connected undirected graph on a distributed or network model of computation after O(n[SUP2]|E|) moves. The algorithm is resilient to transient faults and does not require initialization. A correctness proof of the algorithm is also presented. The paper concludes with remarks on issues such as the time complexity of the algorithm and open problems. [ABSTRACT FROM AUTHOR]

Clustering is an essential tool in data mining research and applications. It is the subject of active research in many fields of study, such as computer science, data science, statistics, pattern recognition, artificial intelligence, and machine learning. Several clustering techniques have been proposed and implemented, and most of them successfully find excellent quality or optimal clustering results in the domains mentioned earlier. However, there has been a gradual shift in the choice of clustering methods among domain experts and practitioners alike, which is precipitated by the fact that most traditional clustering algorithms still depend on the number of clusters provided a priori. These conventional clustering algorithms cannot effectively handle real-world data clustering analysis problems where the number of clusters in data objects cannot be easily identified. Also, they cannot effectively manage problems where the optimal number of clusters for a high-dimensional dataset cannot be easily determined. Therefore, there is a need for improved, flexible, and efficient clustering techniques. Recently, a variety of efficient clustering algorithms have been proposed in the literature, and these algorithms produced good results when evaluated on real-world clustering problems. This study presents an up-to-date systematic and comprehensive review of traditional and state-of-the-art clustering techniques for different domains. This survey considers clustering from a more practical perspective. It shows the outstanding role of clustering in various disciplines, such as education, marketing, medicine, biology, and bioinformatics. It also discusses the application of clustering to different fields attracting intensive efforts among the scientific community, such as big data, artificial intelligence, and robotics. This survey paper will be beneficial for both practitioners and researchers. It will serve as a good reference point for researchers and practitioners to design improved and efficient state-of-the-art clustering algorithms. • Provide an up-to-date comprehensive review of the different clustering techniques. • Highlight novel and most recent practical applications areas of clustering. • Provide a convenient research path for new researchers. • Help experts develop new algorithms for emerging challenges in the research area. [ABSTRACT FROM AUTHOR]

This paper describes a proof system suitable for the mechanical verification of concurrent programs. Mechanical verification, which uses a computer program to validate a formal proof, increases one's confidence in the correctness of the validated proof. This proof system is based on Unity [12], and may be used to specify and verify both safety and liveness properties. However, it is defined with respect to an operational semantics of the transition system model of concurrency. Proof rules are simply theorems of this operational semantics. This methodology makes a clear distinction between the theorems in the proof system and the logical inference rules and syntax which define the underlying logic. Since this proof system essentially encodes Unity in another sound logic, and this encoding has been mechanically verified, this encoding proves the soundness of this formalization of Unity. This proof system has been mechanically verified by the Boyer-Moore prover, a computer program mechanizing the Boyer-Moore logic [7]. This proof system has been used to mechanically verify the correctness of a distributed algorithm that computes the minimum node value in a tree. This paper also describes this algorithm and its correctness theorems, and presents the key lemmas that aided the mechanical verification. The mechanized proof closely resembles a hand proof, but is longer, since all concepts are defined from first principles. This proof system is suitable for the mechanical verification of a wide class of programs, since the underlying prover, though automatic, is guided by the user. [ABSTRACT FROM AUTHOR]

It is desirable for the load in a distributed system to be balanced evenly. A dynamic process migration protocol is needed in order to achieve load balancing in a user transparent manner. A distributed algorithm for load balancing which is network topology independent is proposed in this paper. Different network topologies and low-level communications protocols affect the choice of only some system design parameters. The "drafting" algorithm attempts to compromise two contradictory goals: maximize the processor utilization and minimize the communication overhead. The main objective of this paper is to describe the dynamic process migration protocol based on the proposed drafting algorithm. A sample distributed system is used to further illustrate the drafting algorithm and to show how to define system design parameters. The system performance is measured by simulation experiments based on the sample system. [ABSTRACT FROM AUTHOR]

This paper presents an overview of the problem of testing semiconductor random access memories (RAMs). An important aspect of this test procedure is the detection of permanent faults that cause the memory to function incorrectly. Functional-level fault models are very useful for describing a wide variety of RAM faults. Several fault models are discussed throughout the paper, including the stuck-at-0/1 faults, coupled-cell faults, and single-cell pattern-algorithms. Test procedures for these fault models are presented and their fault coverage and execution times are discussed. The paper is intended for the general computer science audience and presupposes no background in the hardware testing area. [ABSTRACT FROM AUTHOR]

This paper proposes a fast learning algorithm of neural networks and evaluates the performances of adaptive equalizers using neural networks trained by the proposed algorithm in a frequency-selective fading channel. The backpropagation (BP) algorithm which is used widely to train neural networks has a slow convergence rate because it is based on the gradient descent method. This paper presents a fast learning algorithm using the recursive least squares (RLS) algorithm which has a fast convergence rate as an adaptive algorithm for adaptive linear filters. In the proposed algorithm, the sum of the squared error between the actual total input and the desired total input is used as the cost function to apply the RLS algorithm. A simulation result on the exclusive-OR problem indicates that the proposed algorithm is about 8.8 times faster than the BP for the number of iterations required to converge. Recently, there has been interest in adaptive equalizers as an application field of neural networks. However, the performance of an adaptive equalizer using a neural network in a frequency-selective fading channel which is observed in land mobile communications has never been evaluated. Therefore, in this paper, the performances of adaptive equalizers using neural networks trained by the proposed algorithm in a frequency-selective fading channel are evaluated. Especially, an adaptive equalizer using the selectively unsupervised learning neural network proposed by the authors is considered. The adaptive equalizer can reject the false learning by carrying out learning selectively. It is shown that the adaptive equalizer is superior to the conventional one and the one using the conventional neural network. [ABSTRACT FROM AUTHOR]

Particle Swarm Optimization (PSO) is a meta-heuristic algorithm that has been shown to be successful in solving a wide variety of real and complicated optimization problems in engineering and computer science. This paper introduces a projection based PSO technique, named ProjPSO, to efficiently find different types of optimal designs, or nearly optimal designs, for mixture models with and without constraints on the components, and also for related models, like the log contrast models. We also compare the modified PSO performance with Fedorov's algorithm, a popular algorithm used to generate optimal designs, Cocktail algorithm, and the recent algorithm proposed by []. [ABSTRACT FROM AUTHOR]

The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2 nodes under the unit-cost RAM model with a fixed word size w. It is based on the idea of partitioning T into a set of linked small tries, each of which can be maintained efficiently. Our method is not only space-efficient, but also allows the longest common prefix between any query pattern P and the strings currently stored in T to be computed in o(| P|) time for small alphabets, and allows any leaf to be inserted into or deleted from T in o(log| T|) time. To demonstrate the usefulness of our new data structure, we apply it to LZ-compression. Significantly, we obtain the first algorithm for generating the lz78 encoding of a given string of length n over an alphabet of size σ in sublinear ( o( n)) time and sublinear ( o( nlog σ) bits) working space for small alphabets ( $\sigma= 2^{o(\log n \frac{\log\log\log n}{(\log\log n)^{2}})}$). Moreover, the working space for our new algorithm is asymptotically less than or equal to the space for storing the output compressed text, regardless of the alphabet size. [ABSTRACT FROM AUTHOR]

In this paper, we present two structure-preserving-doubling like algorithms for obtaining the positive definite solution of the nonlinear matrix equation X + A H X ¯ − 1 A = Q , where X ∈ C n × n is an unknown matrix and Q ∈ C n × n is a Hermitian positive definite matrix. We prove that the sequences generated by the algorithms converge to the positive definite solution of the considered matrix equation R-quadratically. In addition, we also present some numerical results to illustrate the behavior of the considered algorithm. [ABSTRACT FROM AUTHOR]

The application-specific instruction set processors (ASIPs) have received more and more attention in recent years. ASIPs make trade-offs between flexibility and performance by extending the base instruction set of a general-purpose processor with custom functional units (CFUs). Custom instructions, executed on CFUs, make it possible to improve performance and achieve flexibility for extensible processors. The custom instruction synthesis flow involves two essential issues: custom instruction enumeration (subgraph enumeration) and custom instruction selection (subgraph selection). However, both enumerating all possible custom instructions of a given data-flow graph and selecting the most profitable custom instructions from the enumerated custom instructions are computationally difficult problems. In this paper, we propose efficient algorithms for custom instruction enumeration and custom instruction selection. Compared with previously proposed well-known enumeration algorithms, our approach can achieve a significant speedup while generating the identical set of all possible custom instructions or only connected custom instructions. Experimental results also show that a code size reduction rate up to 76% can be achieved for a set of computational intensive programs, and the speed-up achieved is up to 8.2×. [ABSTRACT FROM AUTHOR]

Recent research shows that significant energy saving can be achieved in wireless sensor networks (WSNs) with a mobile base station that collects data from sensor nodes via short-range communications. However, a major performance bottleneck of such WSNs is the significantly increased latency in data collection due to the low movement speed of mobile base stations. In this paper we study the problem of finding a data collection path for a mobile base station moving along a fixed track in a wireless sensor network to minimize the latency of data collection. The main contribution is an O ( m n log ⁡ n ) expected time algorithm, where n is the number of sensors in the networks and m is the complexity of the fixed track. [ABSTRACT FROM AUTHOR]

In this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items) arrive one by one, each item must be packed into a square bin of unit size on its arrival without any information about future items. When packing items, 90°-rotation is allowed. 1-space bounded means there is only one “active” bin. If the “active” bin cannot accommodate the coming item, it will be closed and a new bin will be opened. The objective is to minimize the total number of bins used for packing all items in the sequence. Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing algorithm with a tight competitive ratio of 5.06. A lower bound of 3.17 on the competitive ratio is proven. Moreover, we study 1-space bounded square packing, where each item is a square with side length no more than 1. A 4.3-competitive algorithm is achieved, and a lower bound of 2.94 on the competitive ratio is given. All these bounds surpass the previously best known results. [ABSTRACT FROM AUTHOR]

With the fast development of social network services, network marketing of products with externalities has been attracting more and more attention from both academia and business. The extensive study on network marketing mainly concerns with positive externalities. The focus of this paper is on the much less understood counterpart for negative externalities, where a consumer has lower incentive to buy a product as the product is possessed by more social network neighbors. For a seller who markets these products, it is desirable to have a good schedule which specifies an order of consumers he approaches. We design polynomial time algorithms that find marketing schedules for products with negative externalities. The goals are two-fold: maximizing the product sale and ensuring consumer regret-free decisions. We show that the maximization is NP-hard. Our algorithms achieve satisfactory performance guarantees, approximating the maximum within constant factors in most of the cases. Two of these algorithms provide regret-proof schedules, reaching an equilibrium state where no consumers regret their previous decisions. Our work is the first attempt to address these marketing problems from an algorithmic point of view. [ABSTRACT FROM AUTHOR]

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an advice bit string that is accessed sequentially by the algorithm. The number of advice bits that are read to achieve some specific solution quality can then serve as a fine-grained complexity measure. The main contribution of this paper is to study a powerful method for proving lower bounds on the number of advice bits necessary. To this end, we consider the string guessing problem as a generic online problem and show a lower bound on the number of advice bits needed to obtain a good solution. We use special reductions from string guessing to improve the best known lower bound for the online set cover problem and to give a lower bound on the advice complexity of the online maximum clique problem. [ABSTRACT FROM AUTHOR]

This paper presents a practical decision procedure for Propositional Projection Temporal Logic with infinite models. First, a set Prop l of labels l i , 0 ⩽ i ⩽ n ∈ N 0 , is used to mark nodes of an LNFG of a formula, and a node with l i is treated as an accepting state as in an automaton. Further, the generalized Büchi accepting condition for automata is employed to identify a path (resulting a word) in an LNFG as a model of the formula. In addition, the implementation details of the decision procedure and relevant algorithms including pre-processing, LNFG, circle finding algorithms are presented; as a matter of fact, all algorithms are implemented by C++ programs. [ABSTRACT FROM AUTHOR]

The Maximum Agreement Forest problem ( MAF ) asks for a largest common subforest of a collection of phylogenetic trees. The MAF problem on two binary phylogenetic trees has been studied extensively in the literature. In this paper, we present a group of fixed-parameter tractable algorithms for the MAF problem on multiple (i.e., two or more) binary phylogenetic trees. Our techniques work fine for the problem for both rooted trees and unrooted trees. The computational complexity of our algorithms is comparable with that of the known algorithms for two trees, and is independent of the number of phylogenetic trees for which a maximum agreement forest is constructed. [ABSTRACT FROM AUTHOR]

Given a connected outerplanar graph G of pathwidth p , we give an algorithm to add edges to G to get a supergraph of G , which is 2-vertex-connected, outerplanar and of pathwidth O ( p ) . This settles an open problem raised by Biedl [1] , in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl [1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs. [ABSTRACT FROM AUTHOR]

This paper presents an approach for verifying the correctness of the feasibility theorem on the deadline driven scheduler (DDS) with the axiom system of Propositional Projection Temporal Logic (PPTL). To do so, the deadline driven scheduling algorithm is modeled by an MSVL (Modeling, Simulation and Verification Language) program and the feasibility theorem is formulated by PPTL formulas with two parts: a necessary part and a sufficient part. Then, several lemmas are abstracted and proved by means of the axiom system of PPTL. With the help of the lemmas, two parts of the theorem are deduced respectively. This case study convinces us that some real-time properties of systems can be formally verified by theorem proving using the axiom system of PPTL. [ABSTRACT FROM AUTHOR]

Pushdown systems (PDS) are well adapted to model sequential programs with (possibly recursive) procedure calls. Therefore, it is important to have efficient model checking algorithms for PDSs. We consider in this paper CTL model checking for PDSs. We consider the “standard” CTL model checking problem where whether a configuration of a PDS satisfies an atomic proposition or not depends only on the control state of the configuration. We consider also CTL model checking with regular valuations, where the set of configurations in which an atomic proposition holds is a regular language. We reduce these problems to the emptiness problem in Alternating Büchi Pushdown Systems, and we give an algorithm to solve this emptiness problem. Our algorithms are more efficient than the other existing algorithms for CTL model checking for PDSs in the literature. We implemented our techniques in a tool, and we applied it to different case studies. Our results are encouraging. In particular, we were able to confirm the existence of known bugs in Linux source code. [ABSTRACT FROM AUTHOR]

A commonly used strategy to improve search accuracy is through feedback techniques. Most existing work on feedback relies on positive information, and has been extensively studied in information retrieval. However, when a query topic is difficult and the results from the first-pass retrieval are very poor, it is impossible to extract enough useful terms from a few positive documents. Therefore, the positive feedback strategy is incapable to improve retrieval in this situation. Contrarily, there is a relatively large number of negative documents in the top of the result list, and it has been confirmed that negative feedback strategy is an important and useful way for adapting this scenario by several recent studies. In this paper, we consider a scenario when the search results are so poor that there are at most three relevant documents in the top twenty documents. Then, we conduct a novel study of multiple strategies for relevance feedback using both positive and negative examples from the first-pass retrieval to improve retrieval accuracy for such difficult queries. Experimental results on these TREC collections show that the proposed language model based multiple model feedback method which is generally more effective than both the baseline method and the methods using only positive or negative model. [ABSTRACT FROM AUTHOR]

In the temporal database literature, every fact stored in a database may be equipped with two temporal dimensions: the valid time, which describes the time when the fact is true in the modeled reality, and the transaction time, which describes the time when the fact is current in the database and can be retrieved. Temporal functional dependencies (TFDs) add valid time to classical functional dependencies (FDs) in order to express database integrity constraints over the flow of time. Currently, proposals dealing with TFDs adopt a point-based approach, where tuples hold at specific time points, to express integrity constraints such as ' for each month, the salary of an employee depends only on his role'. To the best of our knowledge, there are no proposals dealing with interval-based temporal functional dependencies (ITFDs), where the associated valid time is represented by an interval and there is the need of representing both point-based and interval-based data dependencies. In this paper, we propose ITFDs based on Allen's interval relations and discuss their expressive power with respect to other TFDs proposed in the literature: ITFDs allow us to express interval-based data dependencies, which cannot be expressed through the existing point-based TFDs. ITFDs allow one to express constraints such as ' employees starting to work the same day with the same role get the same salary' or ' employees with a given role working on a project cannot start to work with the same role on another project that will end before the first one'. Furthermore, we propose new algorithms based on B-trees to efficiently verify the satisfaction of ITFDs in a temporal database. These algorithms guarantee that, starting from a relation satisfying a set of ITFDs, the updated relation still satisfies the given ITFDs. [ABSTRACT FROM AUTHOR]