Deterministic learning of completely resonant nonlinear wave systems with Dirichlet boundary conditions

In this paper, we investigate the approximation of completely resonant nonlinear wave systems via deterministic learning. The plants are distributed parameter systems (DPS) describing homogeneous and isotropic elastic vibrating strings with fixed endpoints. The purpose of the paper is to approximate the infinite-dimensional dynamics, rather than the parameters of the wave systems. To solve the problem, the wave systems are first transformed into finite-dimensional dynamical systems described by ordinary differential equation (ODE). The properties of the finite-dimensional systems, including the convergence of the solution, as well as the dominance of partial system dynamics according to point-wise measurements, are analyzed. Based on the properties, second, by using the deterministic learning algorithm, an approximately accurate neural network (NN) approximation of the the finite-dimensional system dynamics is achieved in a local region along the recurrent trajectories. Simulation studies are included to demonstrate the effectiveness of the proposed approach.     

Robust state estimation for uncertain linear systems with deterministic input signals

In this paper, we investigate state estimations of a dynamical system in which not only process and measurement noise, but also parameter uncertainties and deterministic input signals are involved. The sensitivity penalization based robust state estimation is extended to uncertain linear systems with deterministic input signals and parametric uncertainties which may nonlinearly affect a state-space plant model. The form of the derived robust estimator is similar to that of the well-known Kalman filter with a comparable computational complexity. Under a few weak assumptions, it is proved that though the derived state estimator is biased, the bound of estimation errors is finite and the covariance matrix of estimation errors is bounded. Numerical simulations show that the obtained robust filter has relatively nice estimation performances.     

Interference automata

We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis, J. Watrous, Two-way finite automata with quantum and classical states, Theoret. Comput. Sci. 287 (1) (2002) 299–311] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Having a DFA as a component, it trivially recognizes regular languages. We show that our model can recognize all languages recognized by 1-way deterministic blind counter automata. Finally we show the existence of a language that cannot be recognized by a 2OIA but which can be recognized by an O(n³)$O\left(n^3\right)$ space Turing machine.     

Motion Planning for Haptic Guidance

Haptic devices allow a user to feel either reaction forces from virtual interactions or reaction forces reflected from a remote site during a bilateral teleoperation task. Also, guiding forces can be exerted to train the user in the performance of a virtual task or to assist him/her to safely teleoperate a robot. The generation of guiding forces relies on the existence of a motion plan that provides the direction to be followed to reach the goal from any free configuration of the configuration space (-space). This paper proposes a method to obtain such a plan that interleaves a sampling-based exploration of -space with an efficient computation of harmonic functions. A deterministic sampling sequence (with a bias based on harmonic function values) is used to obtain a hierarchical cell decomposition model of -space. A harmonic function is iteratively computed over the partially known model using a novel approach. The harmonic function is the navigation function used as motion plan. The approach has been implemented in a planner (called the Kautham planner) that, given an initial and a goal configuration, provides: (a) a channel of cells connecting the cell that contains the initial configuration with the cell that contains the goal configuration; (b) two harmonic functions over the whole -space, one that guides motions towards the channel and another that guides motions within the channel towards the goal; and (c) a path computed over a roadmap built with the free samples of the channel. The harmonic functions and the solution path are then used to generate the guiding forces for the haptic device. The planning approach is illustrated with examples on 2D and 3D workspaces. This work was partially supported by the CICYT projects DPI2005-00112 and DPI2007-63665.     

A neural networks learning algorithm for minor component analysis and its convergence analysis

The eigenvector associated with the smallest eigenvalue of the autocorrelation matrix of input signals is called minor component. Minor component analysis (MCA) is a statistical approach for extracting minor component from input signals and has been applied in many fields of signal processing and data analysis. In this letter, we propose a neural networks learning algorithm for estimating adaptively minor component from input signals. Dynamics of the proposed algorithm are analyzed via a deterministic discrete time (DDT) method. Some sufficient conditions are obtained to guarantee convergence of the proposed algorithm.     

On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.     

The efficiency of identifying timed automata and the power of clocks

We develop theory on the efficiency of identifying (learning) timed automata. In particular, we show that: (i) deterministic timed automata cannot be identified efficiently in the limit from labeled data and (ii) that one-clock deterministic timed automata can be identified efficiently in the limit from labeled data. We prove these results based on the distinguishability of these classes of timed automata. More specifically, we prove that the languages of deterministic timed automata cannot, and that one-clock deterministic timed automata can be distinguished from each other using strings in length bounded by a polynomial. In addition, we provide an algorithm that identifies one-clock deterministic timed automata efficiently from labeled data.Our results have interesting consequences for the power of clocks that are interesting also out of the scope of the identification problem.     

A discontinuous Galerkin solver for Boltzmann–Poisson systems in nano devices

In this paper, we present results of a discontinuous Galerkin (DG) scheme applied to deterministic computations of the transients for the Boltzmann–Poisson system describing electron transport in semiconductor devices. The collisional term models optical-phonon interactions which become dominant under strong energetic conditions corresponding to nano-scale active regions under applied bias. The proposed numerical technique is a finite element method using discontinuous piecewise polynomials as basis functions on unstructured meshes. It is applied to simulate hot electron transport in bulk silicon, in a silicon n⁺–n–n⁺ diode and in a double gated 12 nm MOSFET. Additionally, the obtained results are compared to those of a high order WENO scheme simulation and DSMC (Discrete Simulation Monte Carlo) solvers.     

基于动态默认转移的深度包检测算法

由于基于确定性有限自动机（DFA）的多模式匹配算法对内存的需求比较大,因此需要对DFA进行优化,以减少其对内存的需求量。算法通过用动态默认转移来替代DFA的failto转移,将DFA中大量的failto转移删掉,从而达到优化DFA的目的。实验结果证明,该算法能有效地优化DFA对内存的需求。