Search

Dirty paper coding are relevant for wireless networks, multiuser channels, and digital watermarking. We show that the problem of dirty paper is essentially equivalent to some classes of constrained memories, and we explore the binary so-called nested codes, which are used for efficient coding and error-correction on such channels and memories. Keywords: dirty paper, constrained memory, nested codes, covering codes. [ABSTRACT FROM AUTHOR]

Image entropy thresholding approach has drawn the attentions in image segmentation. The endeavor of this paper is focused on multilevel thresholding using the minimum cross entropy criterion. In the literature, the particle swarm optimization (PSO) had been applied to conducting the threshold selection. The adopted algorithm used in this paper is the honey bee mating optimization (HBMO). In experiments, the two different methods are implemented for comparison with the results of segmentation. Compared to the results of PSO, the threshold selection of HBMO is more close to the optimal ones examined by the exhaustive search method. Furthermore, the segmentation result of HBMO is superior to PSO method, but it still slower than ones of PSO. [ABSTRACT FROM AUTHOR]

Seed is a type of a regularity of strings. A restricted approximate seed w of string T is a factor of T such that w covers a superstring of T under some distance rule. In this paper, the problem of all restricted seeds with the smallest Hamming distance is studied and a polynomial time and space algorithm for solving the problem is presented. It searches for all restricted approximate seeds of a string with given limited approximation using Hamming distance and it computes the smallest distance for each found seed. The solution is based on a finite (suffix) automata approach that provides a straightforward way to design algorithms to many problems in stringology. Therefore, it is shown that the set of problems solvable using finite automata includes the one studied in this paper. [ABSTRACT FROM AUTHOR]

This paper proposes a study on the use of mel-frequency cepstral coefficients (MFCC) and support vector machine (SVM) for text-dependent speaker verification. The MFCCs used in this paper are extracted from the voiced password spoken by the user. These MFCCs will be normalized and then can be used as the speaker features for training a claimed speaker model via SVM. Finally one could make use of the claimed speaker model to discriminate between the speaker and other impostors. Experiments were conducted on the Aurora-2 database with various orders of MFCCs. It follows from the experimental results that the proposed text-dependent speaker verification system based on the 22th-order MFCCs and SVM gives an equal error rate (EER) of 0.0% and average accuracy rate of 95.1%. [ABSTRACT FROM AUTHOR]

A new method which use adjacent similar block in broken areas of image to inpaint the broken patch is proposed in this paper. This method can realize non-ergodic search, reduce the search range sufficiently and find the best matching block very fast. It seem particularly good to inpainting for the damaged region which has strong relevance with its adjacent pixels or surrounding area. The proposed way is due to using the inpainting method [1] which is based on exemplar patch and based on grey cross-correlation algorithm of image match to search similar blocks proposed by Criminisi. As the searching strategy of conventional grey cross-correlation algorithm is ergodic, the speed of matching is slow. In most cases, there are more than one, several similar matching blocks (also called similar exemplar patch, which can fill-in the broken image areas) by the algorithm. One of them is selected randomly when repairing broken image, it will influence the final result of repairing if it isn't the best matching block. Experiment shows that the method of this paper not only improves the speed of image matching and search for matching block precisely, but also can improve efficiency of repairing and get a satisfied inpainting result. [ABSTRACT FROM AUTHOR]

An image compression algorithm using JPEG-LS and cubic spline interpolation (CSI) is presented in this paper. The CSI is developed in order to subsample image data with minimal distortion and to achieve image compression. It has been shown in literatures that the CSI can be combined with the transform-based image compression algorithm to develop a modified image compression codec. The compression ratio obtained from the modified codec is higher than which obtained from the standard transform-based codec at similar subjective quality of reconstructed image. This paper proposes a compression scheme which combines the CSI and JPEG-LS to form the modified JPEG-LS codec and further makes use of this modified codec to image compression. Experimental results show that the compression ratio of proposed scheme has been increased over 3 times higher than the compression ratio of original JPEG-LS image compression standard with similar visual quality. The proposed scheme reduces the loading of storing and transmission of image. [ABSTRACT FROM AUTHOR]

An array antenna system with innovative signal processing can enhance the resolution of a signal direction of arrival (DOA) estimation. Super resolution algorithms take advantage of array antenna structures to better process the incoming signals. They also have the ability to identify multiple targets. This paper explores the eigen-analysis category of super resolution algorithm. A class of Multiple Signal Classification (MUSIC) algorithms known as a root-MUSIC algorithm is presented in this paper. The root-MUSIC method is based on the eigenvectors of the sensor array correlation matrix. It obtains the signal estimation by examining the roots of the spectrum polynomial. The peaks in the spectrum space correspond to the roots of the polynomial lying close to the unit circle. Statistical analysis of the performance of the processing algorithm and processing resource requirements are discussed in this paper. Extensive computer simulations are used to show the performance of the algorithms. [ABSTRACT FROM AUTHOR]

Frequency domain adaptive filters are attractive in applications requiring a large number of coefficients such as acoustic echo cancellation (AEC). Our recent paper derived a not-so-restrictive fixed common step-size bound for the generalized multidelay adaptive filter (GMDF). Based on this bound, this paper introduces a new frequency-domain regularization for the GMDF algorithm. Extensive simulation results demonstrate the usefulness of our algorithm in the scenario of speech input signals. [ABSTRACT FROM AUTHOR]

An array antenna system with innovative signal processing can enhance the resolution of a signal direction of arrival (DOA) estimation. Super resolution algorithms take advantage of array antenna structures to better process the incoming signals. They also have the ability to identify multiple targets. This paper explores the Polynomial Roots Intersection for Multi-dimensional Estimation (PRIME) algorithms. The PRIME algorithm allows a polynomial rooting approach to estimate joint azimuth/elevation parameters of the signal detection for planer arrays. This method calculates a finite set of root intersections, which are the simultaneous solutions from multiple independent multivariate polynomials. The solutions for the source angle information are included in the simultaneous solutions. The PRIME algorithm does not require the use of a scan vector to scan all possible directions. The results demonstrate improvement in both resolution and computational efficiency with no loss of accuracy. Statistical analysis of the performance of the processing algorithm and processing resource requirements are discussed in this paper. Extensive computer simulations are used to show the performance of the algorithms. [ABSTRACT FROM AUTHOR]

Anomaly detection is automatic identification of the abnormal behaviors embedded in a large amount of normal data. This paper presents a method based on one class support vector machine (OCSVM) for detecting network anomalies. The telecommunication network performance data are used for the investigation. Firstly, the raw data are preprocessed in order to produce the vector sets required by the OCSVM algorithm. After preprocessing, the vector set of the training data is used to train the OCSVM detector, which is capable of learning the nominal behaviors of the data. The trained detector is then applied on the test data to detect the anomalies. The detected anomalies are finally categorized into major or minor level by comparing with a threshold. In this paper, experiments on three different types of performance data are presented and the results demonstrate the promising performance of the algorithm. [ABSTRACT FROM AUTHOR]

The Traveling Salesman Problem (TSP) is a well known Nondeterministic Polynomial (NP) problem. A number of sequential algorithms have been well defined to solve TSP. However in this paper the authors demonstrate an alternative way of solving TSP with parallelism by modifying Prim's algorithm and integrate the modified algorithm with a Random algorithm making the whole process more computational extensive in visiting all the nodes/cities. This paper discussed on converting the sequential algorithm into a parallel version to be computed in a High Performance Computer (HPC) using Message Passing Interface (MPI) libraries running on ROCKS open source systems. Outcome of load balancing and cluster performance is also discussed. [ABSTRACT FROM AUTHOR]

This paper reports on the development of a learning system for the prediction of dichotomous response variables by combining fuzzy concept with classical regression technique. The algorithm involves linear transformation followed by linear programming. In the algorithm presented it was assumed that the logarithm of the odds (logit) is linearly related to X's, the independent variables after undergoing the logit transformation. In this paper the research backgrounds and methodology are presented. [ABSTRACT FROM AUTHOR]

An algorithm for the calculation of the sequential parameters in the aircraft electrical system is designed in this paper. The original calculation model of the sequential component calculation is given as a complex formula which is inconvenient for the general digital programmable computation. The geometrical algorithm is presented in this paper in which the voltage vectors rotate and project to the coordinate axis to simplify the calculation. The projections on x and y coordinates may add up in algebra way, and only one projection is left on each axis. Then synthesize the two components to obtain the required sequential voltage vector. This algorithm may be used in the program design by ordinary programming languages in the fault diagnostics and protection to the electrical system. The asymmetry calculation by hand is also made possible. [ABSTRACT FROM AUTHOR]

In this paper a numerical algorithm is described for solving the boundary value problem associated with axisymmetric, inviscid, incompressible, rotational (and irrotational) flow in order to obtain duct wall shapes from prescribed wall velocity distributions. The velocity distribution is defined to be cubic in arclength s, with constant downstream and upstream values. The partial differential equation derived is given in terms of the stream function ψ(x,y) and the function Φ(x,y) as independent variables where for irrotational flow Φ(x,y) can be recognized as the velocity potential function, for rotational flow Φ(x,y) ceases being the velocity potential function but does remain orthogonal to the stream lines, the dependent variable is the radius y, of the duct. A numerical method based on finite differences on a uniform rectangular mesh is employed. The technique described is capable of tackling the so-called inverse problem where the velocity wall distributions are prescribed from which the duct geometry is calculated, as well as the direct problem where the radius distribution of the suction and pressure surfaces respectively are prescribed from which the velocity distribution is calculated. The two different cases as outlined in this paper are in fact boundary value problems with Neumann and Dirichlet boundary conditions respectively. Even though both approaches are discussed, only numerical results for the case of the Neumann boundary condition is given. A downstream condition is prescribed such that cylindrical flow, that is flow that is independent of the axial coordinate, exists. [ABSTRACT FROM AUTHOR]

This paper presents a query modification from user relevance feedback by multiple alignment for image retrieval. In this paper, we propose a novel idea of query modification by aligning multiple positive and negative feedbacks. A object-based image retrieval system is also implemented to verify the effectiveness of the proposed method. Although the initial estimate of user perception is learned from the user feedback, the proposed system automatically modifies the query in question such that the new query agrees (disagrees) with the optimal set of common characteristics of the positive (negative) feedbacks by dynamic programming. The goal of the proposed multiple alignment technique is to move a query from its original position to a meaningful position in the feature space according to user relevance feedback. Experimental results on a large collection of images have shown the effectiveness and robustness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

An algorithm for the calculation of the sequential parameters in the aircraft electrical system is designed in this paper. The original calculation model of the sequential component calculation is given as a complex formula which is inconvenient for the general digital programmable computation. The geometrical algorithm is presented in this paper in which the voltage vectors rotate and project to the coordinate axis to simplify the calculation. The projections on x and y coordinates may add up in algebra way, and only one projection is left on each axis. Then synthesize the two components to obtain the required sequential voltage vector. This algorithm may be used in the program design by ordinary programming languages in the fault diagnostics and protection to the electrical system. The asymmetry calculation by hand is also made possible. [ABSTRACT FROM AUTHOR]

Automatic tracking of eyes is a challenging task, with numerous applications in biometrics, security, intelligent human-computer interfaces, and driver's drowsiness detection systems. Eye localization and extraction is, therefore, the first step in approaching such problems. In this paper, a novel approach for high speed iris detection is introduced. The paper proposes to detect iris based on arc separation and circle detection. The new algorithm is more accurate and flexible in addition to its high speed. The key feature of this approach is a new circle detection algorithm. The circle detection is done by something similar to curve fitting or solving an over determined system. [ABSTRACT FROM AUTHOR]

Speed sign detection is an important component of the driver assistant system, which is expected to enhance the safety of the next generation automotive vehicles. This paper outlines the application of Difference of Gaussian (DoG) filter for vision-based speed sign detection systems in difficult lightning conditions, such as nighttime. This paper describes how DoG filter can be used with the popular radial symmetry algorithm and shows that applying DoG filter significantly improves the algorithm's detection performance in such condition. Our experiments compare the performance of radial symmetry algorithm with and without using DoG filter. The paper also discusses methods to reduce computation requirement of filtering an image with the DoG. [ABSTRACT FROM AUTHOR]

This paper presents a query modification from user relevance feedback by multiple alignment for image retrieval. In this paper, we propose a novel idea of query modification by aligning multiple positive and negative feedbacks. A object-based image retrieval system is also implemented to verify the effectiveness of the proposed method. Although the initial estimate of user perception is learned from the user feedback, the proposed system automatically modifies the query in question such that the new query agrees (disagrees) with the optimal set of common characteristics of the positive (negative) feedbacks by dynamic programming. The goal of the proposed multiple alignment technique is to move a query from its original position t o a meaningful position in the feature space according to user relevance feedback. Experimental results on a large collection of images have shown the effectiveness and robustness of t he proposed algorithm. [ABSTRACT FROM AUTHOR]

One of the most studied fields in data mining is association rules field and studied on this field more than database communications recently. In existed methods of association rules discovery, studying of objects as an only one category provides deficiency of algorithms which provide finding of categorical associations. Online text documents on internet provide adequate information sources. In this paper, meaningful and important information from text documents on internet have been tried to discover. Firstly, a preprocessing is applied to these data to reduce data with noisy and after that only adequate data are saved to database to use. In the study, relations are discovered based on person-place-event-date categories. In this paper, it is investigated to how the categorical association rules can be discovered using rough sets and presented as an application. [ABSTRACT FROM AUTHOR]

A standard genetic algorithm is asexual. To mimic nature more closely, this paper incorporates gender in a genetic algorithm. Two individuals from opposite sex are permitted for reproduction. Earlier researchers considered that the gender of the offspring depends on the gender of the individual removed from the population. Thus the number of males and females are kept constant. This assumption was relaxed by introducing randomness during gender assignment to the offspring after the crossover operation. However, due to the stochastic nature of the process, this may generate a population of single sex which leads to no regeneration being possible. This paper introduces adaptive gender assignment to the offspring so that the gender of the offspring is decided based on the gender density in the population. The proposed algorithm is applied to design a pressure vessel. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a generally applicable algorithm model named Macro-to-Micro Model (M 2M) which is derived from human thinking pattern. The data structure for the nearest neighbor problem based on M 2M can be built in O(1) time. It can also be finished in O(1) time by parallel technology. Moreover, the insertion, deletion and query operation can be completed in constant time without the problem of breaking the balance of tree. And the most noteworthy is that this data structure and preprocessing operation can be shared with most M2M algorithm, so that we can hugely improve the efficiency of the multi-operation problem like image processing and pattern recognition. We mainly focus on the nearest neighbour (NN) searching algorithm in this paper. The M2M approach can achieve the optimal expected time complexity. And the comparative experiment between M 2M and kd-tree shows the great advantage of the former. [ABSTRACT FROM AUTHOR]

This paper studies a gathering problem for a system of asynchronous autonomous mobile robots that can move freely in a two-dimensional plane. We consider robots equipped with inaccurate (incorrect) compasses which may point a different direction from other robots' compasses. A gathering problem is that the robots are required to eventually gather at a single point which is not given in advance from any initial configuration. In this paper, we propose several inaccurate compass models and give two algorithms which solve the gathering problem on these models. One algorithm is the first result dealing with the compasses whose indicated direction may change in every beginning of execution cycles of robots. It solves the problem when compasses point different at most π/8 from the (absolute) north. The other one solves the problem when the compasses never change its pointed direction and their difference is at most π/3 among robots. [ABSTRACT FROM AUTHOR]

Recently, quite a few papers studied methods for representing network properties by assigning informative labels to the vertices of a network. Consulting the labels given to any two vertices u and v for some function f (e.g. "distance(u,v)") one can compute the function (e.g. the graph distance between u and v). Some very involved lower bounds for the sizes of the labels were proven. In this paper, we demonstrate that such lower bounds are very sensitive to the number of vertices consulted. That is, we show several almost trivial constructions of such labeling schemes that beat the lower bounds by large margins. The catch is that one needs to consult the labels of three vertices instead of two. We term our generalized model labeling schemes with queries. Additional contributions are several extensions. In particular, we show that it is easy to extend our schemes for tree to work also in the dynamic scenario. We also demonstrate that the study of the queries model can help in designing a scheme for the traditional model too. Finally, we demonstrate extensions to the non-distributed environment. In particular, we show that one can preprocess a general weighted graph using almost linear space so that flow queries can be answered in almost constant time. [ABSTRACT FROM AUTHOR]

The M-renaming problem consists in providing the processes with a new name taken from a new name space of size M. A renaming algorithm is adaptive if the size M depends on the number of processes that want to acquire a new name (and not on the total number n of processes). Assuming each process proposes a value, the k-set agreement problem allows each process to decide a proposed value in such a way that at most k different values are decided. In an asynchronous system prone to up to t process crash failures, and where processes can cooperate by accessing atomic read/write registers only, the best that can be done is a renaming space of size M = p + t where p is the number of processes that participate in the renaming. In the same setting, the k-set agreement problem cannot be solved for t ≥ k. This paper focuses on the way a solution to the renaming problem can help solving the k-set agreement problem when k ≤ t. It has several contributions. The first is a t-resilient algorithm (1 ≤ t < n) that solves the k-set agreement problem from any adaptive (n + k − 1)-renaming algorithm, when k = t. The second contribution is a lower bound that shows that there is no wait-free k-set algorithm based on an (n + k − 1)-renaming algorithm that works for any value of n, when k < t. This bound shows that, while a solution to the (n + k − 1)-renaming problem allows solving the k-set agreement problem despite t = k failures, such an additional power is useless when k < t. In that sense, in an asynchronous system made up of atomic registers, (n + k − 1)-renaming allows progressing from k > t to k = t, but does not allow bypassing that frontier. The last contribution of the paper is a wait-free algorithm that constructs an adaptive (n + k − 1)-renaming algorithm, for any value of the pair (t,k), from a failure detector of the class $\Omega^k_*$ (this last algorithm is a simple adaptation of an existing renaming algorithm). [ABSTRACT FROM AUTHOR]

We consider the problem of periodic exploration of all nodes in undirected graphs by using a finite state automaton called later a robot. The robot, using a constant number of states (memory bits), must be able to explore any unknown anonymous graph. The nodes in the graph are neither labelled nor colored. However, while visiting a node v the robot can distinguish between edges incident to it. The edges are ordered and labelled by consecutive integers 1,...,d(v) called port numbers, where d(v) is the degree of v. Periodic graph exploration requires that the automaton has to visit every node infinitely many times in a periodic manner. Note that the problem is unsolvable if the local port numbers are set arbitrarily, see [8]. In this context, we are looking for the minimum function π(n), such that, there exists an efficient deterministic algorithm for setting the local port numbers allowing the robot to explore all graphs of size n along a traversal route with the period π(n). Dobrev et al. proved in [13] that for oblivious robots π(n) ≤ 10n. Recently Ilcinkas proposed another port labelling algorithm for robots equipped with two extra memory bits, see [20], where the exploration period π(n) ≤ 4n − 2. In the same paper, it is conjectured that the bound 4n − O(1) is tight even if the use of larger memory is allowed. In this paper, we disprove this conjecture presenting an efficient deterministic algorithm arranging the port numbers, such that, the robot equipped with a constant number of bits is able to complete the traversal period in π(n) ≤ 3.75n − 2 steps hence decreasing the existing upper bound. This reduces the gap with the lower bound of π(n) ≥ 2n − 2 holding for any robot. [ABSTRACT FROM AUTHOR]

We consider an extensional version, called qmTT, of the intensional Minimal Type Theory mTT, introduced in a previous paper with G. Sambin, enriched with proof-irrelevance of propositions and effective quotient sets. Then, by using the construction of total setoid à la Bishop we build a model of qmTT over mTT. The design of an extensional type theory with quotients and its interpretation in mTT is a key technical step in order to build a two level system to serve as a minimal foundation for constructive mathematics as advocated in the mentioned paper about mTT. [ABSTRACT FROM AUTHOR]

Inductive inference has always been a major concern in philosophy. This paper considers two different ways of thinking about induction: the classical way and the new, learning-theoretic way. After a brief introduction, I discuss the classical style of thinking about induction, which conceives of inductive inference as an extension of deductive argumentation. Then, I focus on the new, alternative learning-theoretic approach which sees induction as a type of computational process that converges to the truth. I conclude the paper by considering some of the important philosophical consequences of this fundamental shift in the metaphor through which philosophers conceive of inductive reasoning. [ABSTRACT FROM AUTHOR]

The crossing number of a graph G is the smallest number of edge crossings in any drawing of G into the plane. Recently, the first branch-and-cut approach for solving the crossing number problem has been presented in [3]. Its major drawback was the huge number of variables out of which only very few were actually used in the optimal solution. This restricted the algorithm to rather small graphs with low crossing number. In this paper we discuss two column generation schemes; the first is based on traditional algebraic pricing, and the second uses combinatorial arguments to decide whether and which variables need to be added. The main focus of this paper is the experimental comparison between the original approach, and these two schemes. We also compare these new results to the solutions of the best known crossing number heuristic. [ABSTRACT FROM AUTHOR]

In voting systems, game theory, switching functions, threshold logic, hypergraphs or coherent structures there is an important problem that consists in determining the weightedness of a voting system by means of trades among voters in sets of coalitions. The fundamental theorem by Taylor and Zwicker [8] establishes the equivalence between weighted voting games and k-trade robust games for each positive integer k. Moreover, they also construct, in [9], a succession of games Gk based on magic squares which are (k - 1)-trade robust but not k-trade robust, each one of these games Gk has k2 players. The goal of this paper is to provide improvements by means of different experiments to the problem described above. In particular, we will classify all complete games (a basic class of games) of less than eight players according to whether they are: a weighted voting game or a game which is (k - 1)-trade robust but not k-trade robust for all values of k. As a consequence it will we showed the existence of games with less than k2 players which are (k - 1)-trade robust but not k-trade robust. We want to point out that the classifications obtained in this paper by means of experiments are new in the mentioned fields. [ABSTRACT FROM AUTHOR]

We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in offline and online settings, can be significantly improved if we allow preemption: i.e., interrupt a job and later continue its execution. Preemption is inherent to make a scheduling algorithm efficient [7,8]. Minimizing the total flow time on parallel machines with preemption is known to be NP-hard on m ≥ 2 machines. Leonardi and Raz [8] showed that the well known heuristic shortest remaining processing time (SRPT) performs within a logarithmic factor of the optimal offline algorithm on parallel machines. It is not known if better approximation factors can be reached and thus SRPT, although it is an online algorithm, becomes the best known algorithm in the off-line setting. In fact, in the on-line setting, Leonardi and Raz showed that no algorithm can achieve a better bound. In this work we present a nicer and simpler proof of the approximation ratio of SRPT. The proof presented in this paper combines techniques from the original paper of Leonardi and Raz [8] with those presented in a later paper on approximating total flow time when job preemption but not job migration is allowed [2] and on approximating total flow time non-clairvoyantly [3], that is when the processing time of a job is only known at time of completion. [ABSTRACT FROM AUTHOR]

This paper is the first part of a sequence of two papers that present algebraic constructions of quasi-cyclic LDPC codes for AWGN, binary random and burst erasure channels. In this paper, a class of quasi-cyclic LDPC codes for both AWGN and binary random erasure channels is constructed based on finite fields and special vector representations of finite field elements. [ABSTRACT FROM AUTHOR]

This paper is the second part of a sequence of two papers that present several algebraic methods for constructing quasi-cyclic (QC) LDPC codes for AWGN, binary random and burst erasure channels. In the first paper, we presented a class of QC-LDPC codes for both the AWGN and binary random erasure channels. The construction of this class of QC-LDPC codes is based on finite fields and location vector representations of finite field elements. In this paper, we presented two other algebraic methods for constructing QC-LDPC codes for the AWGN, binary random and burst erasure channels. [ABSTRACT FROM AUTHOR]

Infinite Time Turing Machines (or Hamkins-Kidder machines) have been introduced in [HaLe00] and their computability theory has been investigated in comparison to the usual computability theory in a sequence of papers by Hamkins, Lewis, Welch and Seabold: [HaLe00], [We00a], [We00b], [HaSe01], [Hale02], [We04], [We05] (cf. also the survey papers [Ha02], [Ha04] and [Ha05]). Infinite Time Turing Machines have the same hardware as ordinary Turing Machines, and almost the same software. However, an Infinite Time Turing Machine can continue its computation if it still hasn't reached the Halt state after infinitely many steps (for details, see §, 1). [ABSTRACT FROM AUTHOR]

In this paper we study a class of hybrid systems defined by Pfaffian maps. It is a sub-class of o-minimal hybrid systems which capture rich continuous dynamics and yet can be studied using finite bisimulations. The existence of finite bisimulations for o-minimal dynamical and hybrid systems has been shown by several authors (see e.g. [3,4,13]). The next natural question to investigate is how the sizes of such bisimulations can be bounded. The first step in this direction was done in [10] where a double exponential upper bound was shown for Pfaffian dynamical and hybrid systems. In the present paper we improve this bound to a single exponential upper bound. Moreover we show that this bound is tight in general, by exhibiting a parameterized class of systems on which the exponential bound is attained. The bounds provide a basis for designing efficient algorithms for computing bisimulations, solving reachability and motion planning problems. [ABSTRACT FROM AUTHOR]

The Minimum Energy Broadcast Routing problem was extensively studied during the last years. Given a sample space where wireless devices are distributed, the aim is to perform the broadcast pattern of communication from a given source while minimizing the total energy consumption. While many papers deal with the 2-dimensional case where the sample space is given by a flat area, few results are known about the more interesting and practical 3-dimensional case. In this paper we study such a case and we present a tighter analysis of the minimum spanning tree heuristic in order to considerably decrease its approximation factor from the known 26 to roughly 18.8. This decreases the gap with the known lower bound of 12 given by the so called kissing number. [ABSTRACT FROM AUTHOR]

The k-set agreement problem is a generalization of the consensus problem: considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. It has recently be shown that, in the crash failure model, min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$ is a lower bound on the number of rounds for the non-faulty processes to decide (where t is an upper bound on the number of process crashes, and f, 0 ≤f ≤t, the actual number of crashes). This paper considers the k-set agreement problem in synchronous systems where up to t < n /2 processes can experience general omission failures (i.e., a process can crash or omit sending or receiving messages). It first introduces a new property, called strong termination. This property is on the processes that decide. It is satisfied if, not only every non-faulty process, but any process that neither crashes nor commits receive omission failures decides. The paper then presents a k-set agreement protocol that enjoys the following features. First, it is strongly terminating (to our knowledge, it is the first agreement protocol to satisfy this property, whatever the failure model considered). Then, it is early deciding and stopping in the sense that a process that either is non-faulty or commits only send omission failures decides and halts by round min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$. To our knowledge, this is the first early deciding k-set agreement protocol for the general omission failure model. Moreover, the protocol provides also the following additional early stopping property: a process that commits receive omission failures (and does not crash) executes at most min$(\lceil \frac{f}{k} \rceil +2,\lfloor \frac{t}{k} \rfloor +1)$ rounds. It is worth noticing that the protocol allows each property (strong termination vs early deciding/stopping vs early stopping) not to be obtained at the detriment of the two others. The combination of the fact that min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$ is lower bound on the number of rounds in the crash failure model, and the very existence of the proposed protocol has two very interesting consequences. First, it shows that, although general omission failure model is more severe than the crash failure model, both models have the same lower bound for the non-faulty processes to decide. Second, it shows that, in the general omission failure model, that bound applies also the processes that commit only send omission failures. Keywords: Agreement problem, Crash failure, Strong Termination, Early decision, Early stopping, Efficiency, k-set agreement, Message-passing system, Receive omission failure, Round-based computation, Send omission failure, Synchronous system. [ABSTRACT FROM AUTHOR]

This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on the spreading problem. It defines measures for the quality of spreading, presents a local algorithm for the one-dimensional spreading problem, prove its convergence to the equally spaced configuration and discusses its convergence rate in the synchronous and semi-synchronous settings. It then presents a local algorithm achieving the exact equally spaced configuration in finite time in the synchronous setting, and proves it is time optimal for local algorithms. Finally, the paper also proposes an algorithm for the two-dimensional case and presents simulation results of its effectiveness. [ABSTRACT FROM AUTHOR]

In this paper, the concept of statistical bandwidth of multi-access systems are studied and extended to the case of unknown statistical descriptors. The results can improve the statistical characterization of the tail distribution of aggregated load presented to a multi-access system which is traditionally based on the logarithmic moment generation function (LMGF)[1]. In the paper, an extended moment generating function is introduced for calculating the statistical bandwidth and as a result a novel admission algorithm is presented. To further maximize the admitted load into the multi-access system the free parameter of the extended statistical bandwidth is optimized based on the geometrical optimization of polygonal surfaces. In this way, the system utilization can be near-optimal. [ABSTRACT FROM AUTHOR]

In computational biology, gene order data is often modelled as signed permutations. A classical problem in genome comparison is to detect conserved segments in a permutation, that is, genes that are co-localised in several species, indicating that they remained grouped during evolution. A second largely studied problem related to gene order data is to compute a minimum scenario of reversals that transforms a signed permutation into another. Several studies began to mix the two problems, and it was observed that their results are not always compatible: often parsimonious scenarios of reversals break conserved segments. In a recent study, Bérard, Bergeron and Chauve stated as an open question whether it was possible to design a polynomial time algorithm to decide if there exists a minimum scenario of reversals that transforms a genome into another while keeping the clusters of co-localised genes together. In this paper, we give this polynomial algorithm, and thus generalise the theoretical result of the aforementioned paper. [ABSTRACT FROM AUTHOR]

This paper studies the problem of cutting out a given polygon, drawn on a convex piece of paper, in the cheapest possible way. For the problems of cutting out convex polygons with line cuts and ray cuts, we present a 7.9-approximation algorithm and a 6-approximation algorithm, respectively. For the problem of cutting out ray-cuttable polygons, an O(log n)-approximation algorithm is given. [ABSTRACT FROM AUTHOR]

Two models for the Capacitated Multicast Routing Problem are considered, which are the Multicast k-Path Routing and the Multicast k-Tree Routing. Under these models, two improved approximation algorithms are presented, which have worst case performance ratios of 3 and (2 + ρ), respectively. Here ρ denotes the best approximation ratio for the Steiner Minimum Tree problem, and it is about 1.55 at the writing of the paper. The two approximation algorithms improve upon the previous best ones having performance ratios of 4 and (2.4 + ρ), respectively. The designing techniques developed in the paper could be applicable to other similar networking problems. Keywords: Capacitated Multicast Routing, Approximation Algorithm, Steiner Minimum Tree, Tree Partitioning. [ABSTRACT FROM AUTHOR]

Using a seed to rapidly "hit" possible homologies for further examination is a common practice to speed up homology search in molecular sequences. It has been shown that a collection of higher weight seeds have better sensitivity than a single lower weight seed at the same speed. However, huge memory requirements diminish the advantages of high weight seeds. This paper describes a two-stage extension method, which simulates high weight seeds with modest memory requirements. The paper also proposes the use of so-called daughter seeds, which is an extension of the previously studied vector seed idea. Daughter seeds, especially when combined with the two-stage extension, provide the flexibility to maximize the independence between the seeds, which is a well-known criterion for maximizing sensitivity. Some other practical techniques to reduce memory usage are also discussed in the paper. [ABSTRACT FROM AUTHOR]

We study the problem of bounding a polynomial which is absolutely irreducible, away from polynomials which are not absolutely irreducible. These separation bounds are useful for testing whether an empirical polynomial is absolutely irreducible or not, for the given tolerance or error bound of its coefficients. In the former paper, we studied some improvements on Kaltofen and May's method which finds applicable separation bounds using an absolute irreducibility criterion due to Ruppert. In this paper, we study the similar improvements on the method using the criterion due to Gao and Rodrigues for sparse polynomials satisfying Newton polytope conditions, by which we are able to find more accurate separation bounds, for such bivariate polynomials. We also discuss a concept of separation bound continuations for both dense and sparse polynomialsThis research is partly helped by Grants-in-Aid of MEXT, JAPAN, #16700016.. [ABSTRACT FROM AUTHOR]

In this paper we define a model of randomly generated databases and show how one can compute the threshold functions for queries expressible in monotone non-recursive datalog≠. We also show that monotone non-recursive datalog≠ cannot express any property with a sharp threshold. Finally, we show that non-recursive datalog≠ has a 0-1 law for a large class of probability functions, defined in the paper. [ABSTRACT FROM AUTHOR]

In this paper we study the properties of undirected vertex-labeled graphs and the limitations on the languages that they represent. As a main result of this paper we define the necessary and sufficient conditions for the languages to be representable by a class of undirected vertex-labeled graphs and its subclasses. We assume that all obtained results and techniques are transferable to the case of undirected edge-labeled graphs and might give us similar results. The simplicity of necessary conditions emphasizes the naturalness of the result. The proof of their sufficiency is quite non-trivial and it is based on a new notion of quasi-equivalence, that is significantly different from Myhill-Nerode equivalence and might not be reduced to it. [ABSTRACT FROM AUTHOR]

This paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms SRPT and SJF for minimizing total stretch, where the stretch of a job is its flow time (response time) divided by its processing time. SRPT is perhaps the most well-studied algorithm for minimizing total flow time or stretch. This paper gives the first resource augmentation analysis of the total stretch of SRPT, showing that it is indeed O(1)-speed 1-competitive. This paper also gives a simple lower bound result that SRPT is not s-speed 1-competitive for any s < 1.5. This paper also makes contribution to the analysis of SJF. Extending the work of [4], we are able to show that SJF is O(1)-speed 1-competitive for minimizing total stretch. More interestingly, we find that the competitiveness of SJF can be reduced arbitrarily by increasing the processor speed (precisely, SJF is O(s)-speed (1/s)-competitive for any s ≥ 1). We conjecture that SRPT also admits a similar result. [ABSTRACT FROM AUTHOR]

In this paper we study the existence of a small set of spanning trees that collectively "1-span" an interval graph G. In particular, for any pair of vertices u,v we require a tree such that the distance between u and v in T is at most one more than their distance in G. We show that: - there is no constant size set of collective tree 1-spanners for interval graphs (even unit interval graphs), - interval graph G has a set of collective tree 1-spanners of size O(log D), where D is the diameter of G, - interval graphs have a 1-spanner with fewer than 2n - 2 edges. Furthermore, at the end of the paper we state other results on collective tree c-spanners for c > 1 and other more general graph classes. [ABSTRACT FROM AUTHOR]

This paper is motivated by the design of AES. We consider a broader question of cryptanalysis of block ciphers having very good non-linearity and diffusion. Can we expect anyway, to attacks such ciphers, clearly designed to render hopeless the main classical attacks ? Recently a lot of attention have been drawn to the existence of multivariate algebraic relations for AES (and other) S-boxes. Then, if the XSL-type algebraic attacks on block ciphers [10] are shown to work well, the answer would be positive. In this paper we show that the answer is certainly positive for many other constructions of ciphers. This is not due to an algebraic attack, but to new types of generalised linear cryptanalysis, highly-nonlinear in flavour. We present several constructions of somewhat special practical block ciphers, seemingly satisfying all the design criteria of AES and using similar S-boxes, and yet being extremely weak. They can be generalised, and evolve into general attacks that can be applied - potentially- to any block cipher. Keywords: Block ciphers, AES, Rijndael, interpolation attack on block ciphers, fractional transformations, homographic functions, multivariate equations, Feistel ciphers, generalised linear cryptanalysis, bi-linear cryptanalysis. [ABSTRACT FROM AUTHOR]

Rijndael is the new Advanced Encryption Standard designed by V. Rijmen and J. Daemen and chosen as AES by the NIST in October 2000. Surprisingly, the number of cryptanalyses against this algorithm is very low in depict of many efforts furnished to break it. This paper presents a stronger property than the one used in the Bottleneck Cryptanalysis [GM00]. Unfortunately, this property could not be used to mount a more efficient cryptanalysis than the Bottleneck Attack because it is not possible to improve the complexity of the four rounds distinguisher used in this attack. So, the complexity of the Bottleneck Attack (recalled in this paper) is always 2144 AES executions using 232 plaintexts. [ABSTRACT FROM AUTHOR]