From time series to linear system—Part I. Finite dimensional linear time invariant systems

In the first part of this paper the definition of a dynamical system as simply consisting of a family of time series will be developed. In this context the notions of linearity, time invariance, and finite dimensionality will be introduced. It will be shown that a given family of time series may be represented by a system of (AR) equations: R_iw(t + l) + R_{l − 1}w(t + l − 1) + … + R₀w(t) = 0, or, equivalently, by a finite dimensional linear time invariant system: x(t + 1) = Ax(t) + Bu(t); y(t) = Cx(t) + Du(t); w = (u, y), if and only if this family is linear, shift invariant and complete (or, as is equivalent, closed in the topology of pointwise convergence). This yields a very high level and elegant set of axioms which characterize these familiar objects. It is emphasized, however, that no a priori choice is made as to which components of w are inputs and which are outputs. Such a separation always exists in any specific linear time invariant model. Starting from these definitions, the structural indices of such systems are introduced and it is shown how an (AR) representation of a system having a given behaviour can be constructed. These results will be used in a modelling context in Part II of the paper.     

A Turing machine time hierarchy

The time separation results concerning classes of languages over a single-letter alphabet accepted by multi-tape nondeterministic Turing machines, well-known from Seiferas, Fischer and Meyer (1978), are supplemented. Moreover, via a universal machine a modified time complexity measure UTIME of Turing machines computations which is sensitive to multiplication by constants (i.e., UTIME(t) ? UTIME(kt), where UTIME(t) is the class of languages of complexity not larger than t) is introduced. On the level of this measure, the results concerning languages over one- and two-letter alphabets are refined. The proof tools are versions of a translational diagonalization and of an unpadding technique.     

Parameter-reduction of higher level grammars

A higher level (OI-) grammar is called terminating if for every accessible term t there is at least one terminal term which can be derived from t. A grammar is called parameter-reduced if it is terminating and has no superfluous parameters. For every grammar G of level n0 which generates at least one term we construct grammars R(G) and P(G) such that R(G) and P(G) generate the same language as G but are terminating and parameter-reduced respectively. We introduce a hierarchy of restrictions to the delection capability of the grammars which allow a gradual decrease in the complexity of the algorithms from n-iterated exponential time to polynomial time.     

A Modified Spiking Neuron that Involves Derivative of the State Function at Firing Time

In usual spiking neural networks, the real world information is interpreted as spike time. A spiking neuron of the spiking neural network receives input vector of spike times, and activates a state function x(t) by increasing the time t until the value of x(t) reaches certain threshold value at a firing time t ^a . And t ^a is the output of the spiking neuron. In this paper we propose, and investigate the performance of, a modified spiking neuron, of which the output is a linear combination of the firing time t ^a and the derivative x??(t ^a ). The merit of the modified spiking neuron is shown by numerical experiments for solving some benchmark problems: The computational time of a modified spiking neuron is a little greater than that of a usual spiking neuron, but the accuracy of a modified spiking neuron is almost as good as a usual spiking neural network with a hidden layer.     

Precision preview-based stable-inversion for nonlinear nonminimum-phase systems: The VTOL example

This article quantifies the importance of the future desired trajectory in determining the exact-output-tracking input for nonlinear, nonminimum-phase systems by using system inversion techniques. It is intuitive that the effect of the desired output's distant-future values, on the output-tracking input at the current time instant, should be small. Therefore, at a current time instant (t_c), preview information of the desired output in a finite-time window [t_c,t_c+T_p] should be sufficient to compute the output-tracking input with an arbitrarily small prescribed error, if the preview time T_p is sufficiently large. The contribution of this article is the quantification of the needed preview time T_p by using the benchmark VTOL aircraft model as an example. Additionally, simulation results are presented to evaluate the efficacy of the finite-preview-based stable-inversion approach.     

Time-space trade-offs for compressed suffix arrays

Given a binary string of length n, we give a representation of its suffix array that takes O(nt(lgn)^1/t) bits of space such that given i,1?i?n, the ith entry in the suffix array of the string can be retrieved in O(t) time, for any parameter 1?t?lglgn. For t=lglgn, this gives a compressed suffix array representation of Grossi and Vitter [Proc. Symp. on Theory Comput., 2000, pp. 397-406]. For t=O(1/ε), this gives the best known (in terms of space) compressed suffix array representation with constant query time. From this representation one can construct a suffix tree structure for a text of length n, that uses o(nlgn) bits of space which can be used to find all the k occurrences of a given pattern of length m in O(m/lgn+k) time. No such structure was known earlier.     

Stability of Galerkin multistep procedures in time-homogeneous hyperbolic problems

Linear and time-homogeneous hyperbolic initial boundary value problems are approximated using Galerkin procedures for the space directions and linear multistep methods for the time direction. At first error bounds are proved for multistep methods having a stability interval [?ω, 0], 0<ω, and systemsY″=AY+C(t) under the condition that \(\Delta t^2 \left\| A \right\| \leqslant \omega \) Δt time step. Then these error bounds are applied to derive bounds for the error in hyperbolic problems. The result shows that the initial error and the discretization error grow liket andt ² respectively. But the initial error is multiplied with a factor which becomes large if the mesh width of the space discretization is small.     

Strong diagnosability of regular networks under the comparison model

Diagnosability has played an important role in the reliability of multiprocessor systems. The strongly t-diagnosable system is (t+1) diagnosable except when all of the neighbors of a node are simultaneously faulty. In this paper, we discuss the in-depth properties of diagnosability for t-regular and t-connected networks under the comparison model. We show that a t-regular and t-connected multiprocessor system with at least 2t+6 nodes, for t?4, is strongly t-diagnosable under the comparison model if the following two conditions hold: (1) the system is triangle free, and (2) there are at most t−2 common neighbors for each pair of distinct nodes in the system.     

基于支持向量机的思维脑电信号特征分类研究

探索一种实用的基于想象运动思维脑电的脑-机接口(BCI)方式,为实现BCI应用奠定比较坚实的理论和实验基础。对6名受试者进行三种不同时段(箭头出现2s、1s和0s后提示按键)情况下想象左右手运动思维作业的信号采集实验,利用小波变换和支持向量机对实验数据进行离线处理。对三种情况下的延缓时间△t0、△t1和△t2分析发现:△t0与△t1和△t2之间都有显著性差别(p<0.05),而△t1与△t2之间没有显著差别(p>0.05);平均分类正确率分别达到68.00%、80.00%和56.67%(p<0.05);实际按键前0.5~1s左右,想象左右手运动的思维脑电特征信号都发生了明显改变。通过合理的实验设计获取的信号有助于识别正确率的提高,为BCI系统中思维任务的特征提取与识别分类提供了新思路和方法。     

Three tokens in Herman’s algorithm

Herman’s algorithm is a synchronous randomized protocol for achieving self-stabilization in a token ring consisting of N processes. The interaction of tokens makes the dynamics of the protocol very difficult to analyze. In this paper we study the distribution of the time to stabilization, assuming that there are three tokens in the initial configuration. We show for arbitrary N and for an arbitrary timeout t that the probability of stabilization within time t is minimized by choosing as the initial three-token configuration the configuration in which the tokens are placed equidistantly on the ring. Our result strengthens a corollary of a theorem of McIver and Morgan (Inf. Process Lett. 94(2): 79–84, 2005), which states that the expected stabilization time is minimized by the equidistant configuration.     

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].     

Determining the specificity of terms using inside-outside information: a necessary condition of term hierarchy mining

This paper introduces new specificity measuring methods of terms using inside and outside information. Specificity of a term is the quantity of domain specific information contained in the term. Specific terms have a larger quantity of domain information than general terms. Specificity is an important necessary condition for building hierarchical relations among terms. If t₁ is a hyponym of t₂ in a domain term hierarchy, then the specificity of t₁ is greater than that of t₂. As domain specific terms are commonly compounds of the generic level term and some modifiers, inside information is important to represent the meaning of terms. Outside contextual information is also used to complement the shortcomings of inside information. We propose an information theoretic method to measure the quantity of terms. Experiments showed promising results with a precision of 73.9% when applied to terms in the MeSH thesaurus.     

Sharing and hiding secret images with size constraint

This paper presents a method for sharing and hiding secret images. The method is modified from the (t,n) threshold scheme. (Comput.Graph. 26(5)(2002)765) The given secret image is shared and n shadow images are thus generated. Each shadow image is hidden in an ordinary image so as not to attract an attacker's attention. Any t of the n hidden shadows can be used to recover the secret image. The size of each stego image (in which a shadow image is hidden) is about 1/t of that of the secret image, avoiding the need for much storage space and transmission time (in the sense that the total size of t stego images is about the size of the secret image). Experimental results indicate that the qualities of both the recovered secret image and the stego images that contain the hidden shadows are acceptable. The photographers who work in enemy areas can use this system to transmit photographs.     

Efficient parameterized string matching

In parameterized string matching the pattern P matches a substring t of the text T if there exist a bijective mapping from the symbols of P to the symbols of t. We give simple and practical algorithms for finding all such pattern occurrences in sublinear time on average. The algorithms work for a single and multiple patterns.     

An empirical evaluation of fat-tailed distributions in modeling financial time series

There is substantial evidence that many financial time series exhibit leptokurtosis and volatility clustering. We compare the two most commonly used statistical distributions in empirical analysis to capture these features: the t distribution and the generalized error distribution (GED). A Bayesian approach using a reversible-jump Markov chain Monte Carlo method and a forecasting evaluation method are adopted for the comparison. In the Bayesian evaluation of eight daily market returns, we find that the fitted t error distribution outperforms the GED. In terms of volatility forecasting, models with t innovations also demonstrate superior out-of-sample performance.     

Optimal output-transitions for linear systems

This article addresses the optimal (minimum-input-energy) output-transition problem for linear systems. The goal is to transfer the output from an initial value (for all time t?t_i) to a final output value (for all time t?t_f). Previous methods solve this output-transition problem by transforming it into a state-transition problem; the initial and final states (x(t_i),x(t_f), respectively) are chosen and a minimum-energy state-to-state transition problem is solved. However, the choice of the initial and final states can be ad hoc and the resulting output-transition cost (input energy) may not be minimal. The contribution of this article is the solution of the optimal output-transition problem. An example system with elastic dynamics is studied to illustrate the proposed method. Simulation results are presented that show substantial reduction of transition costs with the use of the proposed method when compared to the use of minimum-energy state-to-state transitions.     

Recursive evaluation of time convolution integrals in the spectral boundary integral method for mode III dynamic fracture problems

The shear crack, propagating spontaneously on a frictional interface, is a useful idealization of a natural earthquake. However, the corresponding boundary value problems are quite challenging in terms of required memory and processor power. While the huge computation amount is reduced by the spectral boundary integral method, the computation effort is still huge. In this paper, a recursive method for the evaluation of convolution integrals was tested in the spectral formulation of the boundary integral method applied to 2D anti-plane crack propagation problems. It is shown that analysis of a 2D anti-plane crack propagation problem involving N_t time steps, based on the recursive evaluation of convolution integrals, requires O(αN_t) computational resources for each Fourier mode (as opposed to O(N_t²) for a classical algorithm), where α is a constant depending on the implementation of the method with typical values much less than N_t. Therefore, this recursive scheme renders feasible investigation of long deformational processes involving large surfaces and long periods of time, while preserving accuracy. The computation methodology implemented here can be extended easily to 3D cases where it can be employed for the simulation of complex spontaneously fault rupture problems which carry a high computational cost.     

Scalable processing of continuous K-nearest neighbor queries with uncertain velocity

Continuous K-nearest neighbor (CKNN) query is an important type of spatio-temporal queries. Given a time interval [t_s, t_e] and a moving query object q, a CKNN query is to find the K-nearest neighbors (KNNs) of q at each time instant within [t_s, t_e]. In this paper, we focus on the issue of scalable processing of CKNN queries over moving objects with uncertain velocity. Due to the large amount of CKNN queries that need to be evaluated concurrently, efficiently processing such queries inevitably becomes more complicated. We propose an index structure, namely the CI-tree, to predetermine and organize the candidates for each query issued by the user from anywhere and anytime. When the CKNN queries are evaluated, their corresponding candidates can be rapidly retrieved by traversing the CI-tree so that the processing time is greatly reduced. A comprehensive set of experiments is performed to demonstrate the effectiveness and the efficiency of the CI-tree.     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

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.