(h,k)-Arbiters for h-out-of-k mutual exclusion problem

h-Out-of-k mutual exclusion is a generalization of the 1-mutual exclusion problem, where there are k units of shared resources and each process requests h (1hk) units at the same time. Though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for 1-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. This paper introduces the new notion that each request uses different quorums depending on the number of units of its request. Based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k+1)-cube (h,k)-arbiter. The quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. A uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. A (k+1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion.     

Timoshenko beam finite element with four dof and convergence of O(h)

In situations where transverse shear deformations and rotary inertia in beams are important, elements based on the Timoshenko beam theory are useful. Among the two-noded, four DOF elements derived from the minimum total potential energy principle, the HTK. element proposed by Hughes et al. using linear displacement functions for both w and θ and the T1CC4 element proposed by Tessler et al. using quadratic displacement function for w and linear displacement function for θ are well known in the literature. The convergence of the HTK element in the thin beam situation has been too poor due to shear locking but by using selective integration this element can be shown to be equivalent to the T1CC4 element which has a rate of convergence of O(h²). In this paper a five DOF element with w and θ at the end nodes and θ at the middle node and based on the cubic displacement function for w and the quadratic displacement function for θ is first developed. Statically condensing the middle rotational DOF, the well-known (4 × 4) stiffness matrix using the φ-factor defined as φ = 12EI/kGAL² and hitherto obtained only through a flexibility approach or closed-form solution of the governing equations of the Timoshenko beam theory is derived. This element based on cubic displacement function for w has rate of convergence of O(h⁴), is completely free of shear locking and performs equally well in thin as well as thick beam situations.     

Design and results of the 2nd annual satisfiability modulo theories competition (SMT-COMP 2006)

The Satisfiability Modulo Theories Competition (SMT-COMP) arose from the SMT-LIB initiative to spur adoption of common, community-designed formats, and to spark further advances in satisfiability modulo theories (SMT). The first SMT-COMP was held in 2005 as a satellite event of CAV 2005. SMT-COMP 2006 was held August 17–19, 2006, as a satellite event of CAV 2006. This paper describes the rules and competition format for SMT-COMP 2006, the benchmarks used, the participants, and the results.     

Necessary and sufficient conditions on Q ( = C( I + PC)) for stabilization of the linear feedback system S(P, C)

We find the following necessary and sufficient conditions for Q (:=C(I+PC)⁻¹) to -stabilize the standard linear time-invariant unity feedback system S(P, C) where P has the l.c.f. (D_pl, N_pl) and the r.c.f. (N_pr, D_pr); and is a principal ideal domain. (i) Q must have elements in (ii) (resp. (iii)) Q must factorize in with D_pr, (resp. D_pl) as a left (resp. right) factor and (iv) (I – QP) must factor in with D_pr, as a left factor.     

(p,q)-Logical completeness for output-coherent sets of (p,q)-Logical functions and an application of the set to image processing

We have previously proposed an idea of p-valued input, q-valued output threshold logic to synthesize many-valued, p-valued, logical networks, and derived the condition for (p, q)-logical completeness for the output-closed set of (p, q)-logical functions. In this paper, the condition for (p, q)-logical completeness for the output-coherent set F of (p, q)-logical functions is described, and the proof is given in almost the same way as for the output-closed set. The output-coherent set F is applied to image processing. That is, a restoration scheme is described for images to which normal random noise is added.     

d-正则(k,s)-SAT问题的NP完全性

研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.     

MAX(1)和MARG(1)中公式改名的复杂性

改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题"对于给定的CNF公式H和F是否存在一个变元(或文字)改名ψ使得ψ(H)=F?"的计算复杂性.MAX(1)和MARG(1)是极小不可满足公式的两个子类,这两个子类中的公式可以用树表示.树同构的判定问题在线性时间内是可解的.证明了对于MAX(1)和MARG(1)中的公式,文字改名问题在线性时间内可解,变元改名问题在平方次时间内可解.     

极小-极大-加系统(F,G,H)的能达能观性

在数字电路中,两个时间信号通过逻辑电路的"与"门相当于极大运算,"或"门相当于极小运算.因此,极小-极大-加系统可用于数字电路的时间分析.对于非线性极强的极小-极大-加系统(F,G,H),引入了分别能达和上限能观的概念.利用图论的方法给出了极小-极大-加系统(F,G,H)的状态变量xt为分别能达分量的充要条件,同时,还得到了xt为上限能观分量的充要条件.     

On the uniform finite generation of SO(n, )

A Lie group G, generated by two one-parameter subgroups is said to be uniformly finitely generated by them if there exists a positive integer N such that every element of G can be expressed as a product of at most N elements chosen alternately from the two one-parameter subgroups. In this paper we construct pairs of generators of so(n) whose one-parameter subgroups uniformly finitely generate SO(n) and as a consequence, we put an upper bound on the number of switches required to join any two points on a manifold M trajectories of two particular vector fields on M.     

Properties of the satisfiability threshold of the strictly d-regular random (3, 2s)-SAT problem

A k-CNF (conjunctive normal form) formula is a regular (k, s)-CNF one if every variable occurs s times in the formula, where k≥2 and s>0 are integers. Regular (3, s)- CNF formulas have some good structural properties, so carrying out a probability analysis of the structure for random formulas of this type is easier than conducting such an analysis for random 3-CNF formulas. Some subclasses of the regular (3, s)-CNF formula have also characteristics of intractability that differ from random 3-CNF formulas. For this purpose, we propose strictly d-regular (k, 2s)-CNF formula, which is a regular (k, 2s)-CNF formula for which d≥0 is an even number and each literal occurs s-\frac{d}{2} or s+\frac{d}{2} times (the literals from a variable x are x and \neg x, where x is positive and \neg x is negative). In this paper, we present a new model to generate strictly d-regular random (k, 2s)-CNF formulas, and focus on the strictly d-regular random (3, 2s)-CNF formulas. Let F be a strictly d-regular random (3, 2s)-CNF formula such that 2s>d. We show that there exists a real number s₀ such that the formula F is unsatisfiable with high probability when s>s₀, and present a numerical solution for the real number s₀. The result is supported by simulated experiments, and is consistent with the existing conclusion for the case of d= 0. Furthermore, we have a conjecture: for a given d, the strictly d-regular random (3, 2s)-SAT problem has an SAT-UNSAT (satisfiable-unsatisfiable) phase transition. Our experiments support this conjecture. Finally, our experiments also show that the parameter d is correlated with the intractability of the 3-SAT problem. Therefore, our research maybe helpful for generating random hard instances of the 3-CNF formula.     

(A, B)-invariant and stabilizability subspaces, a frequency domain description

In a paper of E. Emre and the author a polynomial characterization for (A, B)-invariant subspaces is given. The characterization is used to give a frequency domain criterion for the solvability of the disturbance decoupling problem. In this paper a more elementary and simpler treatment is given. Furthermore, stabilizability subspaces are introduced, are given a frequency domain characterization and are used to solve design problems.     

Integrability,soliton solutions and modulation instability analysis of a (2+1)-dimensional nonlinear Heisenberg ferromagnetic spin chain equation

We consider the Heisenberg ferromagnetic spin chain equation, which is governed by the (2+1)-dimensional nonlinear Schrödinger-type equation. Based on the Ablowitz–Kaup–Newell–Segur frame, we study the integrability of the equation by deriving its Lax pair and infinite conservation laws. By introducing a potential transformation, we obtain its Hirota bilinear form and soliton solutions. Based on the resulting lax pair, we construct Darboux transformation and multi-soliton solutions of the equation. Furthermore, we also find the other type of soliton solutions for the equation by considering its Bäcklund transformation. Finally, we discuss the linear stability analysis by considering its stability condition for the stationary solution of the equation, which can be used to analyze modulation instability. The technique presented in this work is analytical, which can be used to enrich the dynamical of the Heisenberg ferromagnetic spin chain equation.     

Security of Wang et al.''s group-oriented (t,n) threshold signature schemes with traceable signers

This paper describes a new forgery attack on the group-oriented (t,n) threshold signature schemes proposed by Wang et al. Our attack is more fundamental than Tseng–Jan's attack in the sense that it cannot be recognized or blocked at the designated clerk level of the signature schemes.     

随机正则(k,r)-SAT问题的可满足临界

研究k-SAT问题实例中每个变元恰好出现r=2s次,且每个变元对应的正、负文字都出现s次的严格随机正则（k,r）-SAT问题.通过构造一个特殊的独立随机实验,结合一阶矩方法,给出了严格随机正则（k,r）-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等,因此得到了随机正则（k,r）-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则（k,r）-SAT问题的可满足临界值上界,而且还小于一般的随机k-SAT问题的可满足临界值.因此,这也从理论上解释了在相变点处的随机正则（k,r）-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后,数值分析结果验证了所给上界的正确性.     

Quaternion representations of the O(3) group, and their applications in robotics

Abstract algebraic methods for solving different mathematical tasks have found widespread applications in theoretical physics and in several technical applications. Though group theory can be used to achieve the most simple and transparent formulation of different tasks, it is not very well known by engineers. The aim of this paper is to discuss quaternion representations of the O⁺(3) Lie group from the aspect of robotics. The main features of these representations, as well as their advantages over the pure 3 × 3 matrix (self-)representation, are discussed in the formulation and solution of the direct and inverse kinematic tasks for robots of general wrist-joint structure. To illustrate the convenience of quaternion formulations a particular solution of the inverse kinematic task has been developed on the basis of the concept of non-Euclidean (curved) spaces. A possible Hopfield-type neural-network application appropriate to the proposed solution is also considered.     

Rational solutions and their interaction solutions of the (2+1)-dimensional modified dispersive water wave equation

A bilinear form for the modified dispersive water wave (mDWW) equation is presented by the truncated Painlevé series, which does not lead to lump solutions. In order to get lump solutions, a pair of quartic–linear forms for the mDWW equation is constructed by selecting a suitable seed solution of the mDWW equation in the truncated Painlevé series. Rational solutions are then computed by searching for positive quadratic function solutions. A regular nonsingular rational solution can describe a lump in this model. By combining quadratic functions with exponential functions, some novel interaction solutions are founded, including interaction solutions between a lump and a one-kink soliton, a bi-lump and a one-stripe soliton, and a bi-lump and a two-stripe soliton. Concrete lumps and their interaction solutions are illustrated by 3d-plots and contour plots.