Efficient Observer-Dependent Simplification in?Polygonal Domains

In this paper, we consider a special version of the well-known line-simplification problem for simplifying the boundary of a region illuminated by a point light source q, or its visibility polygon VP(q). In this simplification approach, we should take the position of q as an essential factor into account to determine the quality of the resulting simplification. For this purpose, we redefine the known distance- and area-distortion error criteria as the main simplification criteria to take into account the distance between the observer q and the boundary of VP(q). Based on this, we propose algorithms for simplifying VP(q). More precisely, we propose simplification algorithms of O(n ²) and O(n ^4/3+δ ) running time for observer-dependent distance-distortion simplification criterion and an O(n ³) simplification algorithm for observer-dependent area-distortion criterion where n is the number of vertices in VP(q). Moreover, we consider the observer-dependent distance-distortion simplification problem in the data streaming model where the vertices of VP(q) are given as a stream and only a constant amount of memory is available.     

On Metric Dimension of Nonbinary Hamming Spaces

For q-ary Hamming spaces we address the problem of the minimum number of points such that any point of the space is uniquely determined by its (Hamming) distances to them. It is conjectured that for a fixed q and growing dimension n of the Hamming space this number asymptotically behaves as 2n/ log _q n. We prove this conjecture for q = 3 and q = 4; for q = 2 its validity has been known for half a century.     

A new view of fuzzy hypernear-rings

In this survey article, we first introduce the concept of quasi-coincidence of a fuzzy interval value with an interval valued fuzzy set. This concept is a generalized concept of quasi-coincidence of a fuzzy point within a fuzzy set. By using this new idea, we consider the interval valued (∈,∈∨q)-fuzzy sub-hypernear-rings (hyperideals) of a hypernear-ring, and hence, a generalization of a fuzzy sub-near-ring (ideal) is given. Some related properties of fuzzy hypernear-rings are described. Finally, we consider the concept of implication-based interval valued fuzzy sub-hypernear-rings (hyperideals) in a hypernear-ring, in particular, the implication operators in Lukasiewicz system of continuous-valued logic are discussed.     

Computing the velocity of a rotating flow

To compute the time-dependent flow of a rotating incompressible fluid we consider the velocity–vorticity formulation of the Navier–Stokes equations in cylindrical coordinates. In the numerical method employed the velocity field at each time-step is found as the least squares solution of an overdetermined system of linear equations, Ax=b. We consider how to compute x using the preconditioned conjugate gradient algorithm for least squares (PCGLS) on a distributed parallel computer. The various aspects of using a parallel computer are discussed, and results for a wide range of parallel computers are presented. The parallel speed-up depends on the architecture but is typically about 80% of the number of processors used.     

On the user capacity for a multiple-access system in a vector disjunctive channel with errors

We consider a multiple-access system in which each user is given q out of Q available subchannels (q ? Q). We investigate capacities of two channels emerging in the system under consideration in the case of single-user reception. These channels can be considered as modifications of the A-channel. In the first case we assume that a signal transmitted by a certain user is always registered by the receiver. Thus, activity of other users is the only obstacle to correct reception of information transmitted by a certain user in the multiple-access system. In the second case we assume that the output of each subchannel is inverted with probability p. Analytical expressions (both asymptotic and nonasymptotic) are derived and investigated.     

Message Passing Algorithms for MLS-3LIN Problem

MLS-3LIN problem is a problem of finding a most likely solution for a given system of perturbed 3LIN-equations under a certain planted solution model. This problem is essentially the same as MAX-3LIN problem. We consider simple and efficient message passing algorithms for this problem, and investigate their success probability, where input instances are generated under the planted solution model with equation probability p and perturbation probability q. For some variant of a typical message passing algorithm, we prove that p=Θ(1/(nlnn)) is the threshold for the algorithm to work w.h.p. for any fixed constant q<1/2.     

Unified approach to coefficient-based regularized regression

In this paper, we consider the coefficient-based regularized least-squares regression problem with the l^q-regularizer (1≤q≤2) and data dependent hypothesis spaces. Algorithms in data dependent hypothesis spaces perform well with the property of flexibility. We conduct a unified error analysis by a stepping stone technique. An empirical covering number technique is also employed in our study to improve sample error. Comparing with existing results, we make a few improvements: First, we obtain a significantly sharper learning rate that can be arbitrarily close to O(m⁻¹) under reasonable conditions, which is regarded as the best learning rate in learning theory. Second, our results cover the case q=1, which is novel. Finally, our results hold under very general conditions.     

A numerical method for solving systems of linear and nonlinear integral equations of the second kind by hat basis functions

In this paper, we use hat basis functions to solve the system of Fredholm integral equations (SFIEs) and the system of Volterra integral equations (SVIEs) of the second kind. This method converts the system of integral equations into a linear or nonlinear system of algebraic equations. Also, we consider the order of convergence of the method and show that it is O(h²). Application of the method on some examples show its accuracy and efficiency.     

Cryptanalysis of RSA with two decryption exponents

In this paper, we consider RSA with N=pq, where p,q are of same bit size, i.e., q<p<2q. We study the weaknesses of RSA when multiple encryption and decryption exponents are considered with same RSA modulus N. A decade back, Howgrave-Graham and Seifert (CQRE 1999) studied this problem in detail and presented the bounds on the decryption exponents for which RSA is weak. For the case of two decryption exponents, the bound was N^0.357. We have exploited a different lattice based technique to show that RSA is weak beyond this bound. Our analysis provides improved results and it shows that for two exponents, RSA is weak when the RSA decryption exponents are less than N^0.416. Moreover, we get further improvement in the bound when some of the most significant bits (MSBs) of the decryption exponents are same (but unknown).     

Capacity analysis of dual-hop wireless communication systems over α–μ fading channels

In this paper, we consider a dual hop wireless communication system with a non-regenerative relay and study its performance over the α–μ fading channel. Specifically, we derive closed-form expressions for the moment generating function (MGF), the cumulative distribution function (CDF), and the probability density function (PDF) of the harmonic mean of the end-to-end signal-to-noise ratio (SNR) assuming the α–μ fading model. We also derive closed-form expressions for the end-to-end capacity and outage capacity of the system herein. The obtained expressions can be reduced to study the performance of dual hop communication systems over other fading channel models by using the proper values for the α and μ parameters, such as Rayleigh, Nakagami-m, and Weibull fading models. Numerical results are provided for the obtained expressions and conclusion remarks are drawn.     

Continuous reverse k nearest neighbor monitoring on moving objects in road networks

Continuous reverse k nearest neighbor (CRkNN) monitoring in road networks has recently received increasing attentions. However, there is still a lack of efficient CRkNN algorithms in road networks up to now. In road networks, moving query objects and data objects are restricted by the connectivity of the road network and both the object–query distance and object–object distance updates affect the result of CRkNN queries. In this paper, we present a novel algorithm for continuous and incremental evaluation of CRkNN queries in road networks. Our method is based on a novel data structure called dual layer multiway tree (DLM tree) we proposed to represent the whole monitoring region of a CRkNN query q. We propose several lemmas to reduce the monitoring region of q and the number of candidate objects as much as possible. Moreover, by associating a variable NN_count with each candidate object, we can simplify the monitoring of candidate objects. There are a large number of objects roaming in a road network and many of them are irrelevant to a specific CRkNN query of a query object q. To minimize the processing extension, for a road in the network, we give an IQL list and an IQCL list to specify the set of query objects and data objects whose location updates should be maintained for CRkNN processing of query objects. Our CRkNN method consists of two phase: the initial result generating phase and incremental maintenance phase. In each phase, algorithms with high performance are proposed to make our CRkNN method more efficient. Extensive simulation experiments are conducted and the result shows that our proposed approach is efficient and scalable in processing CRkNN queries in road networks.     

Metric completeness of C(p,q) in a globally hyperbolic spacetime

We consider a Lorentzian manifold M which is globally hyperbolic. We define a metric on C(p, q), the set of all equivalence classes of causal curves connecting two causally related points p and q. We show that C(p, q) is a complete metric space with the metric thus defined. Here, by completeness we mean that every Cauchy sequence (a sequence with a tendency to converge) in C(p, q) finds a point in it to converge. We also give an example to show that the result does not hold in general when the spacetime is not globally hyperbolic. The work is in line with research on causality in relativistic spacetimes.     

Fuzzy n-ary hypergroups related to fuzzy points

In this paper, we introduce and study a new sort of fuzzy n-ary sub-hypergroups of an n-ary hypergroup, called $(\in,\in \vee q)In this paper, we introduce and study a new sort of fuzzy n-ary sub-hypergroups of an n-ary hypergroup, called ( ? , ? úq)(\in,\in \vee q)-fuzzy n-ary sub-hypergroup. By using this new idea, we consider the ( ? , ? úq)(\in,\in\vee q)-fuzzy n-ary sub-hypergroup of a n-ary hypergroup. This newly defined ( ? , ? úq)(\in,\in \vee q)-fuzzy n-ary sub-hypergroup is a generalization of the usual fuzzy n-ary sub-hypergroup. Finally, we consider the concept of implication-based fuzzy n-ary sub-hypergroup in an n-ary hypergroup and discuss the relations between them, in particular, the implication operators in £\poundsukasiewicz system of continuous-valued logic are discussed.     

Large parallel machines can be extremely slow for small problems

We consider concurrent-write PRAMs with a large number of processors of unlimited computational power and an infinite shared memory. Our adversary chooses a small number of our processors and gives them a 0–1 input sequence (each chosen processor gets a bit, and each bit is given to one processor). The chosen processors are required to compute thePARITY of their input, while the others do not take part in the computation. Ifat most q processors are chosen andq ≤1/2 log logn, then we show that computing PARITY needsq steps in the worst case. On the other hand, there exists an algorithm which computes PARITY inq steps (for anyq <n) in this model, thus our result is sharp. Surprisingly, if our adversary choosesexactly q of our processors, then they can compute PARITY in [q/2] + 2 steps, and in this case we show that it needs at least [q2] steps. Our result implies that large parallel machines which are efficient when only a small number of their processors are active cannot be constructed. On the other hand, a result of Ajtai and Ben-Or [1] shows that if we haven input bits which contain at most polylogn 1's and polynomially many processors which are all allowed to work, then thePARITY can be solved inconstant time.     

Optimal number of minimal repairs before replacement based on a cumulative repair-cost limit policy

In this paper, we consider a replacement model with minimal repair based on a cumulative repair-cost limit policy, where the information of all repair costs is used to decide whether the system is repaired or replaced. As a failure occurs, the system experiences one of the two types of failures: a type-I failure (repairable) with probability q, rectified by a minimal repair; or a type-II failure (non-repairable) with probability p (=1 − q) that calls for a replacement. Under such a policy, the system is replaced anticipatively at the nth type-I failure, or at the kth type-I failure (k < n) at which the accumulated repair cost exceeds the pre-determined threshold, or any type-II failure, whichever occurs first. The object of this paper is to find the optimal number of minimal repairs before replacement that minimizes the long-run expected cost per unit time of this polish. Our model is a generalization of several classical models in maintenance literature, and a numerical example is presented for illustration.     

Optimal number of minimal repairs before replacement based on a cumulative repair-cost limit policy

In this paper, we consider a replacement model with minimal repair based on a cumulative repair-cost limit policy, where the information of all repair costs is used to decide whether the system is repaired or replaced. As a failure occurs, the system experiences one of the two types of failures: a type-I failure (repairable) with probability q, rectified by a minimal repair; or a type-II failure (non-repairable) with probability p (=1 − q) that calls for a replacement. Under such a policy, the system is replaced anticipatively at the nth type-I failure, or at the kth type-I failure (k < n) at which the accumulated repair cost exceeds the pre-determined threshold, or any type-II failure, whichever occurs first. The object of this paper is to find the optimal number of minimal repairs before replacement that minimizes the long-run expected cost per unit time of this polish. Our model is a generalization of several classical models in maintenance literature, and a numerical example is presented for illustration.     

A preference ordered classification for a multi-objective max–min redundancy allocation problem

In this study, we consider a bi-objective redundancy allocation problem on a series–parallel system with component level redundancy strategy. Our aim is to maximize the minimum subsystem reliability, while minimizing the overall system cost. The Pareto solutions of this problem are found by the augmented ε-constraint approach for small and moderate sized instances. After finding the Pareto solutions, we apply a well known sorting procedure, UTADIS, to categorize the solutions into preference ordered classes, such as A, B, and C. In this procedure, consecutive classes are separated by thresholds determined according to the utility function constructed from reference sets of classes. In redundancy allocation problems, reference sets may contain a small number of solutions (even a single solution). We propose the τ-neighborhood approach to increase the number of references. We perform experiments on some reliability optimization test problems and general test problems.     

Improved conditions for bounded tardiness under EPDF Pfair multiprocessor scheduling

The earliest-pseudo-deadline-first (EPDF) Pfair algorithm is more efficient than other known Pfair scheduling algorithms, but is not optimal for scheduling recurrent real-time task systems on more than two identical processors. Although not optimal, EPDF may be preferable for real-time systems instantiated on less-powerful platforms, those with soft timing constraints, or those whose task composition can change at run-time. In prior work, Srinivasan and Anderson established a sufficient per-task utilization restriction for ensuring a tardiness of at most q quanta, where $q?1$, under EPDF. They also conjectured that under this algorithm, a tardiness bound of one quantum applies to task systems that are not subject to any restriction other than the obvious restrictions, namely, that the total system utilization not exceed the available processing capacity and per-task utilizations not exceed 1.0. In this paper, we present counterexamples that show that their conjecture is false and present sufficient per-task utilization restrictions that are more liberal than theirs. For ensuring a tardiness bound of one quantum, our restriction presents an improvement of 50% over the previous one.     

Some generalizations of comparison results for fractional differential equations

In this paper, by using the technique of upper and lower solutions together with the theory of strict and nonstrict fractional differential inequalities involving Riemann–Liouville differential operator of order q, 0<q<1, some necessary comparison results for further generalizations of several dynamical concepts are obtained. Furthermore, these results are extended to the finite systems of fractional differential equations.     

The Ehrenfeucht conjecture: a compactness claim for finitely generated free monoids

We survey recent results on the so-called Ehrenfeucht Conjecture which states: For each language L over a finite alphabet Σ there exists a finite subset F of L such that for each pair (g, h) of morphisms on Σ¹ the equation g(x)=h(x) holds for all x in L if and only if holds for all x in F.We point out that the conjecture is closely related to the theory of equations in free monoids. We also state a suprising consequence of the conjecture: If it holds (even noneffectively) for all DOL languages, then the HDOL sequence equivalence problem is decidable. Furthermore, we give examples of when the conjecture is known to hold. In particular, we establish it for all binary languages, as well as for all languages when attention is restricted to bounded delay morphisms of some fixed delay.