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)的研究有助于在更强正则约束条件下构造难解实例.     

Autoregressive modeling of speech trajectory transformed to the reconstructed phase space for ASR purposes

Investigating new effective feature extraction methods applied to the speech signal is an important approach to improve the performance of automatic speech recognition (ASR) systems. Owing to the fact that the reconstructed phase space (RPS) is a proper field for true detection of signal dynamics, in this paper we propose a new method for feature extraction from the trajectory of the speech signal in the RPS. This method is based upon modeling the speech trajectory using the multivariate autoregressive (MVAR) method. Moreover, in the following, we benefit from linear discriminant analysis (LDA) for dimension reduction. The LDA technique is utilized to simultaneously decorrelate and reduce the dimension of the final feature set. Experimental results show that the MVAR of order 6 is appropriate for modeling the trajectory of speech signals in the RPS. In this study recognition experiments are conducted with an HMM-based continuous speech recognition system and a naive Bayes isolated phoneme classifier on the Persian FARSDAT and American English TIMIT corpora to compare the proposed features to some older RPS-based and traditional spectral-based MFCC features.     

一种基于彩色编码技术的基序发现算法

从DNA序列中发现基序是生物计算中的一个重要问题,序列条数K=20包含基序用例的序列条数k=16的(l,d)-(K-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的SDA(sample-driven algorithm)搜索算法--彩色编码基序搜索算法(color coding motif finding algorithm,简称CCMF算法).它利用彩色编码技术将该问题转化为(l,d)-(16-16)问题,再采用分治算法和分支定界法来求解.在解决将(l,d)-(20-16)问题转化为(l,d)-(16-16)问题时,CCMF算法利用彩色编码技术将4 845个组合降低到403个着色,这将极大地提高算法的整体运行效率.使用模拟数据和生物数据进行测试的结果表明,CCMF算法能够快速发现所有(l,d)-(20-16)问题的基序模型和基序用例,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题.同时,通过修改着色方案,CCMF算法可以用于求解一般的(l,d)-(K-k)问题,其中,k＜K.     

Analysis and synthesis of speech using least <Emphasis Type="Italic">P</Emphasis>th norm filter design

In this paper we analyze the combination of speech and FIR filter design aspect to achieve good results in speech quality. A new approach in the time domain based on the least Pth norm is presented to extract maximum information that represents speech. The aim of this paper is to improve the perceived quality of speech through the introduction of least Pth norm algorithm that attenuates speech contaminated with noise. This approach relates to a filter bank structure and a method for filtering and separating an information signal into different bands, particularly for filtering and separation of speech signals. Then the desired signal is reconstructed from the independent components representing every band. This approach differs from the traditional approaches since no priori knowledge of the noise statistics is required, instead the noise signals are only assumed to have finite energy. Since the estimation criterion for the filter design is to minimize the worst possible amplification of the estimation error signal in terms of modeling errors and additive noise, this approach is highly robust and appropriate in practical speech analysis and synthesis. This paper presents a least Pth approach to the optimal design of FIR digital filter banks in the minimax sense for speech analysis and synthesis. The signal to noise ratio (SNR) of around 50–60 dB is achieved with various speech samples.     

Optimal time-weighted H 2 model reduction for Markovian jump systems

This article addresses the optimal time-weighted H ₂ model reduction problem for Markovian jump linear systems. That is, for a given mean square stable Markovian jump system, our aim is to find a mean square stable jump system of lower order such that the time-weighted H ₂ norm of the corresponding error system is minimised. The time-weighted H ₂ norm of the system is first defined, and then a computational method is constructed. The computation requires the solution of two sets of recursive Lyapunov-type linear matrix equations associated with the Markovian jump system. To solve the optimal time-weighted H ₂ model reduction problem, we propose a gradient flow method for its solution. A necessary condition for minimality is derived, and a computational procedure is provided to obtain the minimising reduced-order model. The necessary condition generalises the standard result for systems when Markov jumps and the time-weighting term do not appear. Finally, two numerical examples are given to demonstrate the effectiveness of the proposed approach.     

Time series clustering and classification by the autoregressive metric

The statistical properties of the autoregressive (AR) distance between ARIMA processes are investigated. In particular, the asymptotic distribution of the squared AR distance and an approximation which is computationally efficient are derived. Moreover, the problem of time series clustering and classification is discussed and the performance of the AR distance is illustrated by means of some empirical applications.     

A General Approach to L（h,k）-Label Interconnection Networks

Given two non-negative integers h and k, an L（h, k）-labeling of a graph G = （V, E） is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L（h, k）-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Beneg, CCC, Trivalent Cayley networks, are all characterized by a similar structure： they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called （l × n）-multistage graphs, containing the most common interconnection topologies, on which we study the L（h, k）-labeling. A general algorithm for L（h, k）-labeling these graphs is presented, and from this method an efficient L（2, 1）-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.     

A method for transforming grammars into LL(k) form

Summary A new method for transforming grammars into equivalent LL(k) grammars is studied. The applicability of the transformation is characterized by defining a subclass of LR(k) grammars, called predictive LR(k) grammars, with the property that a grammar is predictive LR(k) if and only if the corresponding transformed grammar is LL(k). Furthermore, it is shown that deterministic bottom-up parsing of a predictive LR(k) grammar can be done by the LL(k) parser of the transformed grammar. This parsing method is possible since the transformed grammar always left-to-right covers the original grammar. The class of predictive LR(k) grammars strictly includes the class of LC(k) grammars (the grammars that can be parsed deterministically in the left-corner manner). Thus our transformation is more powerful than the one previously available, which transforms LC(k) grammars into LL(k) form.     

GH 2 control for uncertain discrete-time-delay fuzzy systems based on a switching fuzzy model and piecewise Lyapunov function

Generalized H2 （GH2） stability analysis and controller design of the uncertain discrete-time Takagi-Sugeno （T-S） fuzzy systems with state delay are studied based on a switching fuzzy model and piecewise Lyapunov function. GH2 stability sufficient conditions are derived in terms of linear matrix inequalities （LMIs）. The interactions among the fuzzy subsystems are considered. Therefore, the proposed conditions are less conservative than the previous results. Since only a set of LMIs is involved, the controller design is quite simple and numerically tractable. To illustrate the validity of the proposed method, a design example is provided.     

Mixed <Emphasis Type="Italic">H</Emphasis><Subscript>2</Subscript>/<Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript> filtering for a class of high-speed sampling uncertain systems

The problem of mixed H2/H∞ filtering for polytopic Delta operator systems is investigated. The aim is to design a linear asymptotically stable filter which guarantees that the filtering error system has different performances in different filtering channels. Based on a parameter-dependent Lyapunov function, a new mixed H2/H∞ performance criterion is presented. Upon this performance criterion, a sufficient condition for the full-order mixed H2/H∞ filter is derived in terms of linear matrix inequalities. The filter can be obtained from the solution of a convex optimization problem. The proposed filter design procedure is less conservative than the strategy based on the quadratic stability notion. A numerical example is given to illustrate the feasibility of the proposed approach.     

A geometric approach for shared secrets, a refinement

A refinement to the (k,n) threshold scheme proposed by Wu and He [1] is presented. It has been found that usable primes p need not be confined to the form p ≡ ±3 (mod 8) as suggested originally. Our constructive proof also lead to a different algorithm for implementation. This implementation dispenses with the directory file suggested in [1] which can be prohibitively large when the scheme is implemented with large p using the original proposal.     

Anisotropic <Emphasis Type="Italic">ε</Emphasis>-optimal model reduction for linear discrete time-invariant system

We consider an ε-optimal model reduction problem for a linear discrete time-invariant system, where the anisotropic norm of reduction error transfer function is used as a performance criterion. For solving the main problem, we state and solve an auxiliary problem of H ₂ ε-optimal reduction of a weighted linear discrete time system. A sufficient optimality condition defining a solution to the anisotropic ε-optimal model reduction problem has the form of a system of cross-coupled nonlinear matrix algebraic equations including a Riccati equation, four Lyapunov equations, and five special-type nonlinear equations. The proposed approach to solving the problem ensures stability of the reduced model without any additional technical assumptions. The reduced-order model approximates the steady-state behavior of the full-order system.     

取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则（k,2s）-CNF公式.受严格正则（k,2s）-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k,2s）-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机（k,2s）-CNF公式.取定整数5<s<11,模拟实验显示,严格d-正则随机（3,2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机（3,2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机（3,2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.     

Intuitionistic (<Emphasis Type="Italic">S</Emphasis>, <Emphasis Type="Italic">T</Emphasis>)-fuzzy hyperquasigroups

The concept of intuitionistic fuzzy subhyperquasigroups in a hyperquasigroup with respect to an s-norm and a t-norm on intuitionistic fuzzy sets is introduced and their properties of such hyperquasigroups are studied. Intuitionistic (S, T)-fuzzy relations on a hyperquasigroup G are discussed. In particular, we investigate connections hyperquasigroups with binary quasigroups.     

Robust H∞ control for uncertain discrete-time systems with time-varying delays via exponential output feedback controllers

This paper considers the problem of robust H_∞ control for uncertain discrete systems with time-varying delays. The system under consideration is subject to time-varying norm-bounded parameter uncertainties in both the state and measured output matrices. Attention is focused on the design of a full-order exponential stable dynamic output feedback controller which guarantees the exponential stability of the closed-loop system and reduces the effect of the disturbance input on the controlled output to a prescribed level for all admissible uncertainties. In terms of a linear matrix inequality (LMI), a sufficient condition for the solvability of this problem is presented, which is dependent on the size of the delay. When this LMI is feasible, the explicit expression of the desired output feedback controller is also given. Finally, an example is provided to demonstrate the effectiveness of the proposed approach.     

Linear Algebra Considerations for the Multi-Threaded Simulation of Mechanical Systems

A solution method suitable for the multi-threaded simulation ofmechanical systems represented in Cartesian coordinates isproposed and analyzed. In a state-space framework for thesolution of the Differential Algebraic Equations (DAE) ofMultibody Dynamics, the position/velocity stabilization and theacceleration computation are based on iterative solvers applied toequivalent reduced problems. The most in-depth computationalaspect analyzed is the preconditioning, i.e., the direct solutionof the reduced systems. Provided a topology index reduction is first applied to the model, the effort for the direct solution of the reduced systems is shown to be of order O(N _J ), where N _J is the number of joints in the model. The recurring theme of thepaper is the central role that the topology of the mechanicalsystem plays in the overall performance of the numericalsimulation. Based on the topology of the model, parallelcomputational threads can be established to start in the equationformulation and continue through the iterative numericalalgorithms employed for the numerical solution. Task schedulingthese parallel threads is expected to redeem real-time performancefor certain classes of complex applications.     

Speech Detection in Non-Stationary Noise Based on the 1/f Process

In this paper,an effective and robust active speech detection method is proposed based on the 1/f process technique for signals under non-stationary noisy environments.The Gaussian 1/f process ,a mathematical model for statistically self-similar radom processes based on fractals,is selected to model the speech and the background noise.An optimal Bayesian two-class classifier is developed to discriminate them by their 1/f wavelet coefficients with Karhunen-Loeve-type properties.Multiple templates are trained for the speech signal,and the parameters of the background noise can be dynamically adapted in runtime to model the variation of both the speech and the noise.In our experiments,a 10-minute long speech with different types of noises ranging from 20dB to 5dB is tested using this new detection method.A high performance with over 90% detection accuracy is achieved when average SNR is about 10dB.     

Quad‐Rotor Modeling and Attitude Control Using State‐Dependent ARX Type Model

A state‐dependent autoregressive with exogenous variables (SD‐ARX) model whose functional coefficients are approximated by sets of radial basis function (RBF) networks is proposed to describe the dynamic behavior of a quad‐rotor in this paper. This model is identified offline and used as an internal predictor of a receding horizon predictive controller to address the quad‐rotor's attitude control issue. In addition, the physical constraints of the system have been also taken into account during the controller design process. The results of real‐time control on a quad‐rotor aircraft illustrate satisfactory modeling accuracy in a large operating range and good performance of control approach proposed in this paper.     

Optimal (N,T)-policy for M/G/1 system with cost structures

In this paper, the optimal (N,T)-policy for M/G/1 system with cost structure is studied. The system operates only intermittently. It is shut down when no customers are present. A fixed set-up cost of K>0 is incurred each time the system is reopened. Also, a holding cost of h>0 per unit time is incurred for each customer present. The (N,T)-policy studied for this system is as follows: the system reactivates as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T (see A.S. Alfa, I. Frigui, Eur. J. Oper. Res. 88 (1996) 599-613; Y.N. Doganata, in: E. Arikan (Ed.), Communication, Control, and Signal Processing, 1990, pp. 1663–1669). Later on, as a comparison, the start of the timer count is relaxed as follows: the system reactivates as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. For both cases, the explicit optimal policy (N^*,T^*) for minimizing the long-run average cost per unit time are obtained. As extreme cases, we include the simple optimal policies for N-and T-polices. Several counter-intuitive results are obtained about the optimal T-policies for both types of models.