The complete inclusion structure of leaf power classes

Let k≥2 be an integer and G=(V,E) be a finite simple graph. A tree T is a k-leaf root of G, if V is the set of leaves of T and, for any two distinct x,yV, the distance between x and y in T is at most k if and only if xyE. We say that G is a k-leaf power if there is a k-leaf root of G. The main result of this paper is that, for all 2≤k<k^′, the classes of k- and k^′-leaf powers are inclusion-incomparable, if and only if k^′≤2k−3 and k^′−k is an odd number. With this result, an open problem from the literature about the inclusion structure of these graph classes is solved completely. In addition, the intersection of the smallest pair of inclusion-incomparable classes is studied.     

A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees

Let G be a graph. Then T ⊆ V(G) is called an R^k-vertex-cut if G − T is disconnected and each vertex in V(G) − T has at least k neighbors in G − T. The size of a smallest R^k-vertex-cut is the R^k-vertex-connectivity of G and is denoted by κ^k(G). In this paper, we determine the numbers κ¹ and κ² for Cayley graphs generated by 2-trees, including the popular alternating group graphs.     

LR(0) grammars generated by LR(0) parsers

Summary Let be an LR(0) parser of a given LR(0) grammar G. Generally, does not only parse the words generated by G but also the words of some other LR(0) grammars different from G. In this paper we shall define a class of LR(0) parsers and shall present a characterization and a method for the construction of all LR(0) grammars which can be parsed by a given LR(0) parser.     

Homogeneity tests for several Poisson populations

In this paper we compare the size distortions and powers for Pearson’s χ²-statistic, likelihood ratio statistic LR, score statistic SC and two statistics, which we call UT and VT here, proposed by [Potthoff, R.F., Whittinghill, M., 1966. Testing for homogeneity: II. The Poisson distribution. Biometrika 53, 183–190] for testing the equality of the rates of K Poisson processes. Asymptotic tests and parametric bootstrap tests are considered. It is found that the asymptotic UT test is too conservative to be recommended, while the other four asymptotic tests perform similarly and their powers are close to those of their parametric bootstrap counterparts when the observed counts are large enough. When the observed counts are not large, Monte Carlo simulation suggested that the asymptotic test using SC, LR and UT statistics are discouraged; none of the parametric bootstrap tests with the five statistics considered here is uniformly best or worst, and the asymptotic tests using Pearson’s χ² and VT always have similar powers to their bootstrap counterparts. Thus, the asymptotic Pearson’s χ² and VT tests have an advantage over all five parametric bootstrap tests in terms of their computational simplicity and convenience, and over the other four asymptotic tests in terms of their powers and size distortions.     

Inapproximability of the Tutte polynomial

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (FPRAS) for T(G;x,y). Under the assumption RP≠NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1,y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP≠NP, there is no FPRAS at the point (x,y)=(0,1-λ) when λ>2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T(G;x,y) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points (x,y) at which even approximating T(G;x,y) is as hard as #P.     

A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree

The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R ^′ ⊊ R⊆V with |R−R ^′|≥2, selected-internal Steiner minimum tree problem is to find a minimum subtree T of G interconnecting R such that any leaf of T does not belong to R ^′. In this paper, suppose c is metric, we obtain a (1+ρ)-approximation algorithm for this problem, where ρ is the best-known approximation ratio for the Steiner minimum tree problem.     

An alternative approach to the improvement of LR(k) parsers

Summary The methods of improving LR(k) parsers proposed by DeRemer and Korenjak are shown to be based on a single concept — that of modifying the contextual information on which parsing decisions are made. This concept is then used to derive a straightforward algorithm for eliminating unit productions from an LR parser.     

Toward the three-dimensional structure and lysophosphatidic acid binding characteristics of the LPA4/p2y9/GPR23 receptor: A homology modeling study

Lysophosphatidic acid (LPA) is a naturally occurring phospholipid that initiates a broad array of biological processes, including those involved in cell proliferation, survival and migration via activation of specific G protein-coupled receptors located on the cell surface. To date, at least five receptor subtypes (LPA_1–5) have been identified. The LPA_1–3 receptors are members of the endothelial cell differentiation gene (Edg) family. LPA₄, a member of the purinergic receptor family, and the recently identified LPA₅ are structurally distant from the canonical Edg LPA_1–3 receptors. LPA₄ and LPA₅ are linked to G_q, G_12/13 and G_s but not G_i, while LPA_1–3 all couple to G_i in addition to G_q and G_12/13. There is also evidence that LPA₄ and LPA₅ are functionally different from the Edg LPA receptors. Computational modeling has provided useful information on the structure–activity relationship (SAR) of the Edg LPA receptors. In this work, we focus on the initial analysis of the structural and ligand-binding properties of LPA₄, a prototype non-Edg LPA receptor. Three homology models of the LPA₄ receptor were developed based on the X-ray crystal structures of the ground state and photoactivated bovine rhodopsin and the recently determined human β₂-adrenergic receptor. Docking studies of LPA in the homology models were then conducted, and plausible LPA binding loci were explored. Based on these analyses, LPA is predicted to bind to LPA₄ in an orientation similar to that reported for LPA_1–3, but through a different network of hydrogen bonds. In LPA_1–3, the ligand polar head group is reported to interact with residues at positions 3.28, 3.29 and 7.36, whereas three non-conserved amino acid residues, S114(3.28), T187(EL2) and Y265(6.51), are predicted to interact with the polar head group in the LPA₄ receptor models.     

Radiocoloring in planar graphs: Complexity and approximations

The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters, by exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function such that |Φ(u)-Φ(v)|2, when u,v are neighbors in G, and |Φ(u)-Φ(v)|1 when the distance of u,v in G is two. The number of discrete frequencies and the range of frequencies used are called order and span, respectively. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span or the order. In this paper we prove that the radiocoloring problem for general graphs is hard to approximate (unless NP=ZPP) within a factor of n^1/2-ε (for any ), where n is the number of vertices of the graph. However, when restricted to some special cases of graphs, the problem becomes easier. We prove that the min span RCP is NP-complete for planar graphs. Next, we provide an O(nΔ) time algorithm (|V|=n) which obtains a radiocoloring of a planar graph G that approximates the minimum order within a ratio which tends to 2 (where Δ the maximum degree of G). Finally, we provide a fully polynomial randomized approximation scheme (fpras) for the number of valid radiocolorings of a planar graph G with λ colors, in the case where λ4Δ+50.     

Spatial strategies in a generalized spatial prisoner’s dilemma

Many strategies, such as tit-for-tat, have been proposed in the iterated prisoner’s dilemma (IPD) in which the prisoner’s dilemma (PD) is carried out repeatedly with two players. A spatial version of the iterated prisoner’s dilemma (SPD) has been studied, where a player at each site plays the IPD game with all the players in the neighborhood. However, the strategies studied in the SPD consider the past actions of a single opponent only. We studied spatial strategies that depend on the configuration of actions taken by all neighbors (as opposed to conventional temporal strategies). Since generosity can be considered as a spatial strategy, we first investigate the generosity required when an action error is involved. We also propose several spatial strategies that outperform many others.This work was presented, in part, at the 9th International Symposium on Artificial Life and Robotics, Oita, Japan, January 28–30, 2004     

On measuring μ-T-inconditionality of fuzzy relations

In this paper two methods are proposed to measure the μ-T-inconditionality character of any fuzzy relation for any continuous t-norm T, and it is studied when both methods result to be equivalent.     

Factorization and feedback stabilization for nonlinear systems

We establish the equivalence of internal input-out stability for two feedback configurations of a nonlinear, time-varying plant P for which a related plant G is assumed to have a factorization G = R with both R and R⁻¹ incrementally stable; this extends a factorization principle for stabilizability previously given only for the linear, time-invariant case. As an application of a special case we recover a version of the Youla parametrization of stabilizing compensators for the nonlinear case previously presented in the literature. We use degree theory to parametrize a collection of solutions of the H_∞-control problem for the case of a 1-gain stable or lossless plant. In the case of a plant G having a J-inner-outer factorization, this last result combined with the above-mentioned factorization principle leads to results on the H_∞-control problem for P.     

Using the artificial neural network model for modeling the performance of the counter flow vortex tube

In this study, the effect of the nozzle number and the inlet pressure on the heating and cooling performance of the counter flow type vortex tube has been modeled with artificial neural networks (ANN) by using the experimentally obtained data. ANN has been designed by Pithiya software. In the developed system output parameter temperature gradient between the cold and hot outlets (ΔT) has been determined using inlet parameters such as the inlet pressure (P_inlet), nozzle number (N), and cold mass fraction (μ_c). The back-propagation learning algorithm with variant which is Levenberg–Marquardt (LM) and Fermi transfer function have been used in the network. In addition, the statistical validity of the developed model has been determined by using the coefficient of determination (R²), the root means square error (RMSE) and the mean absolute percentage error (MAPE). R², RMSE and MAPE have been determined for ΔT as 0.9947, 0.188224, and 0.0460, respectively.     

一种快速空间聚类算法 *

提出了一种基于空间单元单维运算的快速聚类算法SUSDC。该算法首先将被聚类的数据逐维划分成 若干个不相交的空间单元;然后基于空间距离阈值判定相邻的空间单元是否合并,直到全部维处理完毕。实验 结果验证了SUSDC算法运算速度快,能够处理不规则形状数据和高维数据,且具有对噪声数据不敏感的特点。     

A practical general method for constructing LR(k) parsers

Summary The paper presents in detail the case for k=1 of a practical general method for constructing LR(k) parsers. For k=1 this method is of rival efficiency to the previous general algorithm described by the author in [21]. The method involves combining the states of an LR(k) parser as they are generated, reducing to a fraction, in the process, the number of configurations that need actually be evaluated, or for which space must be assigned — compared to such general methods as those of [1, 11, 12, 17]. The criteria of compatibility introduced for this purpose are such that the parser obtained is in practice identical in size to, or negligibly larger than, that obtained by resolving the inadequacies of an LR(o) parser (as is done for various subsets of the LR(k) grammars in [5, 8, 14, 20]).This paper is a development of one of the ideas proposed in Pager [16]. The work was supported by the National Science Foundation under Grant GJ-43362.     

Curvature properties of the algebraic Riccati equation

We prove that the solution to the algebraic Ricatti equation (ARE) is concave with respect to a nonnegative-definite symmetric state weighting matrix Q when the input weighting matrix R = R^T > 0. We also prove that the solution to the ARE is concave with respect to a positive-definite diagonal input weighting matrix R when Q = Q^T ≥ 0.     

基于粒子群优化的带障碍约束空间聚类分析

聚类分析是空间数据挖掘的主要方法之一.传统聚类算法忽略了真实世界中许多约束条件的存在,而约束条件的存在会影响聚类结果的合理性.在分析K中心聚类方法易陷入局部极小值和对初始值敏感的基础上,提出了一种新的聚类方法--基于粒子群优化的带障碍约束空间聚类方法.实验结果表明,该聚类方法不仅使得聚类结果更具实际意义,而且在全局寻优能力方面明显优于K中心聚类方法,且有较快的收敛速度.     

Optical humidity sensor using porphyrin immobilized Nafion composite films

A Nafion–TMPyP composite film was used in an optical humidity sensor. The composites were prepared with various molar ratios between the sulfonic groups and TMPyP molecules, R = [–SO₃H]/[TMPyP]. The UV–vis measurement of the composite films suggested that the TMPyP molecules were well dispersed at in the range of R = 60–100, but formed aggregates at R ≤ 20. Furthermore, the FTIR indicated that sulfonic group interacted with TMPyP. The reflectance change with relative humidity (%RH) occurred at 426.4 and 465.4 nm with the isosbestic point at 437.5 nm, and also in the Q-band region. The sensors of R = 30 and 40 sensitively responded to humidity in the lower humidity region (10–20%RH), but saturated or even decreased with further increase in humidity. At R = 60, the sensitivity slightly decreased but a measurable range was extended to around 70%RH. Remarkable deterioration in sensitivity occurred at R = 100. The TMPyP molecules were stably immobilized on a Nafion matrix, even in liquid water, without solving out.     

Characterization of the spatial variability of surface topography and moisture content and its influence on potato crop yield

ABSTRACT

Addressing the cause of the spatial variability of crop (Solanum tuberosum L.) yield is of a great importance to farmers who plan to apply precision agriculture techniques. Therefore, a study on two centre pivot irrigated potato fields in Saudi Arabia was conducted to detect and assess the spatial dependencies among three variables (surface topography, moisture content, and potato yield) and to examine the influence of surface topography and moisture on the potato yield. In addition to surface elevation data in the form of digital elevation model, cloud-free satellite images of Landsat-8 with a spatial resolution of 30 m were acquired throughout the study period. Samples of potato yield were collected 2 days prior to the harvest time and upscaled into yield maps using the interpolation technique in ArcGIS software program. Soil field capacity (F_C) and permanent wilting point (PWP) were determined for the study area and utilized to generate moisture content maps using thermal inertia method. The study employed the bivariate Moran’s Index (Moran’s I) and the Bivariate Local Indicator of Spatial Autocorrelation in order to measure the strength of the spatial autocorrelation and to quantify the spatial dependency between each two of the acquired variables. The interpretation of the mapped topography, cumulative moisture, and yield revealed a substantial agreement along the spatial distribution of the high moisture and yield values with the adverse value of the surface elevation. Results of the spatial autocorrelation indicated that the spatial patterns of moisture-yield over the two study fields were strongly associated with high-high clustering level covering an area of 42% of field 68-S and 39% of field 44-S, while topography-yield patterns over field 68-S and 44-S covered only 25% and 22% of the areas, respectively, with a confidence level of 0.01 for all patterns at both fields.