Analysis of space allocation in a generally fragmented linear store

Summary The space allocation process in a fragmented linear store with general fragmentation characteristics is analysed. For a given allocation requirement t, exact expression for the n-th moment of the allocation penalty for single block contiguous allocation is obtained, which for large t is shown to be O(¯F(t)^–n ), where ¯F(·) is the complementary distribution function of the free block sizes. For multiple block non-contiguous allocation, it is shown that the corresponding penalty can be approximated by an n-th degree polynomial and is O(t ⁿ) for large t. Compared with experimental values, the model results are able to achieve good agreement.     

Approximate Solutions of Polynomial Equations

In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x)  ∈ Q [ x ], with its constant term equal to 0, such that F(x, y)  = ∑_j = 0ⁿc_j(y − g(x))^jfor some rational numbers c_j, hence, F(x, g(x)  + a)  ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g₁(x),⋯ , g_t(x), t ≤ n, such that F(x, g_i(x))  ∈ Q for 1  ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g₁(x),⋯ , g_t(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y).     

Diagnosable evaluation of DCC linear congruential graphs under the PMC diagnostic model

A DCC (disjoint consecutive cycles) linear congruential graph G(F, n) consists of n nodes and is generated by a set of linear functions F with special properties. It was proved that G(F, n) is a 2t-regular graph and has connectivity 2t, where t=|F| and 1?t?p-1 (n=2^p for some integer p). For a multiprocessor system, its diagnosability is critical to measure the performance. In this paper, we study the diagnosability of G(F,2^p) under the precise and pessimistic diagnosis strategies based on the PMC (Preparata, Metze, and Chien) diagnostic model. It is proved that G(F,2^p) is 2t-diagnosable and (4t-5)/(4t-5)-diagnosable under the two diagnosis strategies, respectively, where p?3 and 2?t?p-1. In addition, the diagnosability of DCC linear congruential graphs is compared with that of BC (bijective connection) graphs.     

Efficient evaluation of specific queries in constraint databases

Let F₁,…,Fs∈R[X₁,…,Xn] be polynomials of degree at most d, and suppose that F₁,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F₁,…,Fs.For any point x∈Rn, we consider the task of determining the signs of the values F₁(x),…,Fs(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F₁,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)^O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F₁,…,Fs belong to Z[X₁,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F₁,…,Fs.     

Characterization of analytic phase signals

In many cases, a real-valued signal χ(t) may be associated with a complex-valued signal a(t)e^iθ(t), the analytic signal associated with χ(t) with the characteristic properties χ(t) = a(t) cosθ(t) and H(a(·)cosθ(·))(t) = a(t)sinθ(t). Using such obtained amplitude-frequency modulation the instantaneous frequency of χ(t) at the time t₀ may be defined to be θ′(t₀), provided θ′(t₀) ≥ 0. The purpose of this note is to characterize, in terms of analytic functions, the unimodular functions F(t) = C(t) + iS(t),C²(t) + S² (t) = 1, a.e., that satisfy HC(t) = S(t). This corresponds to the case a(t) ≡ 1 in the above formulation. We show that a unimodular function satisfies the required condition if and only if it is the boundary value of a so called inner function in the upper-half complex plane. We also give, through an explicit formula, a large class of functions of which the parametrization C(t) = cosθ(t) is available and the extra condition θ′(t) ≥ 0, a.e. is enjoyed. This class of functions contains Blaschke products in the upper-half complex plane as a proper subclass studied by Picinbono in [1].     

System Reduction and Solution Algorithms for Singular Linear Difference Systems under Rational Expectations

A first-order linear difference system under rational expectations is, AEy_t+1|I_t=By_t+C(F)Ex_t|I_t , where y_t is a vector of endogenous variables;x_t is a vector ofexogenous variables; Ey_t+1|I_t is the expectation ofy_t+1 givendate t information; and C(F)Ex_t|I_t =C₀x_t+C₁Ex_t+1|I_t+dot;s +C_nEx_t+n|I_t. If the model issolvable, then y_t can be decomposed into two sets of variables:dynamicvariables d_t that evolve according toEd_t+1|I_t = Wd_t + ¶si_d(F)Ex_t|I_t and other variables thatobey the dynamicidentities f_t =–Kd_t–¶si_f(F)Ex_t|I_t. We developan algorithm for carrying out this decomposition and for constructing theimplied dynamic system. We also provide algorithms for (i) computing perfectforesight solutions and Markov decision rules; and (ii) solutions to relatedmodels that involve informational subperiods.     

Partial synchrony based on set timeliness

We introduce a new model of partial synchrony for read-write shared memory systems. This model is based on the simple notion of set timeliness—a natural generalization of the seminal concept of timeliness in the partially synchrony model of Dwork et?al. (J. ACM 35(2):288–323, 1988). Despite its simplicity, the concept of set timeliness is powerful enough to define a family of partially synchronous systems that closely match individual instances of the t-resilient k-set agreement problem among n processes, henceforth denoted (t, k, n)-agreement. In particular, we use it to give a partially synchronous system that is synchronous enough for solving (t, k, n)-agreement, but not enough for solving two incrementally stronger problems, namely, (t + 1, k, n)-agreement, which has a slightly stronger resiliency requirement, and (t, k ? 1, n)-agreement, which has a slightly stronger agreement requirement. This is the first partially synchronous system that separates these sub-consensus problems. The above results show that set timeliness can be used to study and compare the partial synchrony requirements of problems that are strictly weaker than consensus.     

Calibration of remotely sensed, coarse resolution NDVI to CO2 fluxes in a sagebrush-steppe ecosystem

The net ecosystem exchange (NEE) of carbon flux can be partitioned into gross primary productivity (GPP) and respiration (R). The contribution of remote sensing and modeling holds the potential to predict these components and map them spatially and temporally. This has obvious utility to quantify carbon sink and source relationships and to identify improved land management strategies for optimizing carbon sequestration. The objective of our study was to evaluate prediction of 14-day average daytime CO₂ fluxes (F_day) and nighttime CO₂ fluxes (R_n) using remote sensing and other data. F_day and R_n were measured with a Bowen ratio-energy balance (BREB) technique in a sagebrush (Artemisia spp.)-steppe ecosystem in northeast Idaho, USA, during 1996-1999. Micrometeorological variables aggregated across 14-day periods and time-integrated Advanced Very High Resolution Radiometer (AVHRR) Normalized Difference Vegetation Index (iNDVI) were determined during four growing seasons (1996-1999) and used to predict F_day and R_n. We found that iNDVI was a strong predictor of F_day (R²=0.79, n=66, P<0.0001). Inclusion of evapotranspiration in the predictive equation led to improved predictions of F_day (R²=0.82, n=66, P<0.0001). Crossvalidation indicated that regression tree predictions of F_day were prone to overfitting and that linear regression models were more robust. Multiple regression and regression tree models predicted R_n quite well (R²=0.75-0.77, n=66) with the regression tree model being slightly more robust in crossvalidation. Temporal mapping of F_day and R_n is possible with these techniques and would allow the assessment of NEE in sagebrush-steppe ecosystems. Simulations of periodic F_day measurements, as might be provided by a mobile flux tower, indicated that such measurements could be used in combination with iNDVI to accurately predict F_day. These periodic measurements could maximize the utility of expensive flux towers for evaluating various carbon management strategies, carbon certification, and validation and calibration of carbon flux models.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

Graded tableaux for Rational Pavelka Logic

In this article, a sound and complete tableau system for Rational Pavelka Logic (RPL) is introduced. Extended formulas are used as the counterpart of the graded formulas. In this calculus, if we want to show that the graded formula (x, r) is tableau provable (in the finite fuzzy theory F, respectively), we develop a tableau for the extended formula [r, x] (for the set of extended formulas {[r, x], [x₁, a₁],…, [x_n, a_n] }, respectively). If this tableau closes we claim that (x, r) is tableau provable (in the fuzzy theory F, respectively). We claim also that x is valid at the degree equal to the l.u.b. that allows the closure of the tableaux. Our tableaux are a first step toward efficient procedures of automated deduction in narrow fuzzy logic with truth constants. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 1273–1285, 2005.     

Exact learning of DNF formulas using DNF hypotheses

We show the following: (a) For any ε>0, log^(3+ε)n-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries. (b) For sufficiently large t, t-term DNF formulas cannot be polynomial-query learned with membership and equivalence queries that use t^1+ε-term DNF formulas as hypotheses, for some ε<1 (c) Read-thrice DNF formulas are not polynomial-query learnable with membership and proper equivalence queries. (d) logn-term DNF formulas can be polynomial-query learned with membership and proper equivalence queries. (This complements a result of Bshouty, Goldman, Hancock, and Matar that -term DNF can be so learned in polynomial time.)Versions of (a)-(c) were known previously, but the previous versions applied to polynomial-time learning and used complexity theoretic assumptions. In contrast, (a)-(c) apply to polynomial-query learning, imply the results for polynomial-time learning, and do not use any complexity-theoretic assumptions.     

Ring embedding in faulty pancake graphs

In this paper, we consider the fault hamiltonicity and the fault hamiltonian connectivity of the pancake graph P_n. Assume that F⊆V(P_n)∪E(P_n). For n?4, we prove that P_n−F is hamiltonian if |F|?(n−3) and P_n−F is hamiltonian connected if |F|?(n−4). Moreover, all the bounds are optimal.     

A Distributed Critical Section Protocol for General Topology

We present a new critical section protocol designed for distributed systems with general topologies, where the physical layer is implemented as point-to-point physical links in contrast to shared access physical media. The protocol operates correctly for any topology; however, its time performance is topology dependent. The distributed system can be modeled by a graph G(V, E), where V denotes the set of processors and E is the set of bidirectional communication links. We use n to denote |V|; D(G) is the diameter of G, T(G) is the spanning tree of G, and D(T) is the diameter of T(G). An important measure of the performance of the protocol is the amount of traffic caused by its operation. Let message-hop be the amount of traffic generated by a single message between two adjacent nodes. The proposed protocol generates network traffic of only 3*(n − 1) ∈ Θ(n) [message-hops] per critical section access for any topology which is less than other existing fully distributed protocols. A lower bound on traffic for a single critical section access for a fully distributed protocol is shown to be 2*(n − 1) [message-hops]. Some previously published algorithms generate Θ(n²) [message-hops] of network traffic for some topologies. Another important measure of the performance of the protocol is the cs-access time. It is the time required to access the critical section in the absence of other requests; and it depends on the topology. The high cs-access time performance is achieved by taking a novel approach of distributing the communication and parts of computation functions of the protocol and exploiting the physical topology. For a constant size message, the time to traverse an edge, including the message communication software processing in the source and destination nodes, is called message-hop-time and it is denoted by t_h. For a general graph G (with spanning tree T) the new protocol has the cs-access time performance Θ(max(D(T), max(deg (v_i)))) [t_h], where deg(v_i) is computed in T. For the graphs where G has D(G) ∈ Θ(log₂n) and max(deg(v_i)) in G is O(log₂n), the cs-access time performance is Θ(log₂n) [t_h]. For the class of graphs where G has D(G) ∈ Θ(n), the cs-access time performance is Θ(n) [t_h]. For the Star graphs the cs-access time performance is Θ(n) [t_h]. The worst case time performance occurs for linear and Star graphs. The proposed protocol has a better network traffic performance and (depending on the topology) a better or equal cs-access time performance than previously published fully distributed protocols. The protocol keeps the clock bounded in well-designed systems using a distributed predictive "clock squashing" mechanism.     

On the form equivalence of L-forms

In [5] the notion of an L form F defining a family $\text{L}$_d(F) of languages by means of X-interpretations has been introduced. Here X is one of a number of possible variations of the notion of interpretation originally used in [1] for grammar forms. In this paper it is shown that the questions whether $\text{L}{}_{\mathrm{d}}\text{(F) =}\text{L}{}_{\mathrm{d}}\text{(F}{}_1\text{)}$ for L forms F and F₁ is decidable, if deterministic interpretations of PDOL systems are considered, where L(F) and L(F₁) contain at most one word of length n for any n ? 0, and it is shown that same question is undecidable, if full or uniform interpretations are chosen. In contrast to this, no such results are known for grammar forms at this point.     

A theoretical limit for safety verification techniques with regular fix-point computations

In computer aided verification, the reachability problem is particularly relevant for safety analyses. Given a regular tree language L, a term t and a relation R, the reachability problem consists in deciding whether there exist a positive integer n and terms t₀,t₁,…,tn such that t₀∈L, tn=t and for every 0?i<n, (ti,ti+1)∈R. In this case, the term t is said to be reachable, otherwise it is said unreachable. This problem is decidable for particular kinds of relations, but it is known to be undecidable in general, even if L is finite. Several approaches to tackle the unreachability problem are based on the computation of an R-closed regular language containing L. In this paper we show a theoretical limit to this kind of approaches for this problem.     

Edge-bipancyclicity of star graphs with faulty elements

In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph S_n. Given a set F comprised of faulty vertices and/or edges in S_n with |F|≤n−3 and any fault-free edge e in S_n−F, we show that there exist cycles of every even length from 6 to n!−2|F_v| in S_n−F containing e, where n≥3. Our result is optimal because the star graph is both bipartite and regular with the common degree n−1. The length of the longest fault-free cycle in the bipartite S_n is n!−2|F_v| in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n!−2|F_v|+2 to n!−2|F_v| can be embedded.     

Fault diagnosis in loop-connected systems

The paper considers fault diagnosis in a large system comprising a collection of small subsystems or units which can test one another for the existence of a faulty condition. If subsystem α is not faulty and tests subsystem β, a correct indication of the status of β is obtained; if α is faulty, the test outcome contains meaningless information. A particular form of interconnection is examined. For a system with n units u_o,u₁,…,u_{n ? 1}, for each i unit u_i tests u_{i + 1},u_{i + 2},…,u_{i + A} (modulo n arithmetic being understood), where A is a preselected integer. If t is the maximum number of faulty units, we show that when t ? A, all faults are immediately diagnosable if n ? 2t + 1; we also show that when t ? A, at least A faults can be diagnosed if and only if n ? s(t ? As) + t + A + 1, where s is the integer which maximizes the quadratic function f(x) = x(t ? Ax) of the integer variable x.     

Hamiltonian connectivity of the WK-recursive network with faulty nodes

A graph G is said to be Hamiltonian-connected if there is a Hamiltonian path between every two distinct nodes of G. Let F denote the set of faulty nodes of G. Then, G is |F|-node Hamiltonian-connected if G-F is Hamiltonian-connected. We use K(d,t) to denote a WK-recursive network of level t, each of whose basic modules is a d-node complete graph. Compared with other networks, it is rather difficult to construct a Hamiltonian path between two arbitrary nodes in a faulty WK-recursive network. In this paper, we show that K(d,t) is (d-4)-node Hamiltonian-connected. Since the connectivity of K(d,t) is d-1, the result is optimal in the worst case.     

Asymptotic relation of M- and P-estimators of location

Let T_n and M_n be the P-estimator (Pitman-like estimator) and M_n the M-estimator of the location parameter θ, respectively, both generated by function ρ with the derivative ψ=ρ: It is demonstrated that, under some assumptions on the underlying distribution function F, the difference M_n-T_n is of the order o_p(n^-1/2) in the case of Huber's function ψ. It is further shown that M_n-T_n=o_p(n^-1) if ψ is sufficiently smooth.     

The existence of circular Florentine arrays

A κ × n circular Florentine array is an array of n distinct symbols in gk circular rows such that

• 1.(1) each row contains every symbol exactly once, and
• 2.(2) for any pair of distinct symbols (a, b) and for any integer m from 1 to n − 1 there is at most one row in which b occurs m steps to the right of a.

For each positive integer n = 2, 3, 4,…, define F_c(n) to be the maximum number such that an F_c(n) × n circular Florentine array exists.From the main construction of this paper for a set of mutually orthogonal Latin squares (MOLS) having an additional property, and from the known results on the existence/nonexistence of such MOLS obtained by others, it is now possible to reduce the gap between the upper and lower bounds on F_c(n) for infinitely many additional values of n not previously covered. This is summarized in the table for all odd n up to 81.