Automata and logics over finitely varying functions

We extend some of the classical connections between automata and logic due to Büchi (1960) [5] and McNaughton and Papert (1971) [12] to languages of finitely varying functions or “signals”. In particular, we introduce a natural class of automata for generating finitely varying functions called View the MathML source’s, and show that it coincides in terms of language definability with a natural monadic second-order logic interpreted over finitely varying functions Rabinovich (2002) [15]. We also identify a “counter-free” subclass of View the MathML source’s which characterise the first-order definable languages of finitely varying functions. Our proofs mainly factor through the classical results for word languages. These results have applications in automata characterisations for continuously interpreted real-time logics like Metric Temporal Logic (MTL) Chevalier et al. (2006, 2007) [6] and [7].

The alpha method for solving differential algebraic inequality (DAI) systems

This paper describes an algorithm for ``direct numerical integration'' of the initial value Differential-Algebraic Inequalities (DAI) in a time stepping fashion using a sequential quadratic programming (SQP) method solver for detecting and satisfying active path constraints at each time step. The activation of a path constraint generally increases the condition number of the active discretized differential algebraic equation's (DAE) Jacobian and this difficulty is addressed by a regularization property of the alpha method. The algorithm is locally stable when index 1 and index 2 active path constraints and bounds are active. Subject to available regularization it is seen to be stable for active index 3 active path constraints in the numerical examples. For the high index active path constraints, the algorithm uses a user-selectable parameter to perturb the smaller singular values of the Jacobian with a view to reducing the condition number so that the simulation can proceed. The algorithm can be used as a relatively cheaper estimation tool for trajectory and control planning and in the context of model predictive control solutions. It can also be used to generate initial guess values of optimization variables used as input to inequality path constrained dynamic optimization problems. The method is illustrated with examples from space vehicle trajectory and robot path planning.

Algebraic Cryptanalysis of CTRU Cryptosystem

CTRU, a public key cryptosystem was proposed by Gaborit, Ohler and Sole. It is analogue of NTRU, the ring of integers replaced by the ring of polynomials $\mathbb{F}_2[T]$ . It attracted attention as the attacks based on either LLL algorithm or the Chinese Remainder Theorem are avoided on it, which is most common on NTRU. In this paper we presents a polynomial-time algorithm that breaks CTRU for all recommended parameter choices that were derived to make CTRU secure against popov normal form attack. The paper shows if we ascertain the constraints for perfect decryption then either plaintext or private key can be achieved by polynomial time linear algebra attack.

An algebraic formulation of static isotropy and design of statically isotropic 6-6 Stewart platform manipulators

In this paper, we present an algebraic method to study and design spatial parallel manipulators that demonstrate isotropy in the force and moment distributions. We use the force and moment transformation matrices separately, and derive conditions for their isotropy individually as well as in combination. The isotropy conditions are derived in closed-form in terms of the invariants of the quadratic forms associated with these matrices. The formulation is applied to a class of Stewart platform manipulator, and a multi-parameter family of isotropic manipulators is identified analytically. We show that it is impossible to obtain a spatially isotropic configuration within this family. We also compute the isotropic configurations of an existing manipulator and demonstrate a procedure for designing the manipulator for isotropy at a given configuration. (C) 2008 Elsevier Ltd. All rights reserved.

Algebraic distributed space-time codes with low ML decoding complexity

"Extended Clifford algebras" are introduced as a means to obtain low ML decoding complexity space-time block codes. Using left regular matrix representations of two specific classes of extended Clifford algebras, two systematic algebraic constructions of full diversity Distributed Space-Time Codes (DSTCs) are provided for any power of two number of relays. The left regular matrix representation has been shown to naturally result in space-time codes meeting the additional constraints required for DSTCs. The DSTCs so constructed have the salient feature of reduced Maximum Likelihood (ML) decoding complexity. In particular, the ML decoding of these codes can be performed by applying the lattice decoder algorithm on a lattice of four times lesser dimension than what is required in general. Moreover these codes have a uniform distribution of power among the relays and in time, thus leading to a low Peak to Average Power Ratio at the relays.

Guessing based on length functions

Close relationships between guessing functions and length functions are established. Good length functions lead to good guessing functions. In particular, guessing in the increasing order of Lempel-Ziv lengths has certain universality properties for finite-state sources. As an application, these results show that hiding the parameters of the key-stream generating source in a private key crypto-system may not enhance the privacy of the system, the privacy level being measured by the difficulty in brute-force guessing of the key stream.

New rational interpolation functions for finite element analysis of rotating beams

A rotating beam finite element in which the interpolating shape functions are obtained by satisfying the governing static homogenous differential equation of Euler–Bernoulli rotating beams is developed in this work. The shape functions turn out to be rational functions which also depend on rotation speed and element position along the beam and account for the centrifugal stiffening effect. These rational functions yield the Hermite cubic when rotation speed becomes zero. The new element is applied for static and dynamic analysis of rotating beams. In the static case, a cantilever beam having a tip load is considered, with a radially varying axial force. It is found that this new element gives a very good approximation of the tip deflection to the analytical series solution value, as compared to the classical finite element given by the Hermite cubic shape functions. In the dynamic analysis, the new element is applied for uniform, and tapered rotating beams with cantilever and hinged boundary conditions to determine the natural frequencies, and the results compare very well with the published results given in the literature.

Novel window functions for digital filters

Window technique is one of the simplest methods to design Finite Impulse Response (FIR) filters. It uses special functions to truncate an infinite sequence to a finite one. In this paper, we propose window techniques based on integer sequences. The striking feature of the proposed work is that it overcomes all the problems posed by floating point numbers and inaccuracy, as the sequences are made of only integers. Some of these integer window sequences, yield sharp transition, while some of them result in zero ripple in passband and stopband.

Stiff-String Basis Functions for Vibration Analysis of High Speed Rotating Beams

A new rotating beam finite element is developed in which the basis functions are obtained by the exact solution of the governing static homogenous differential equation of a stiff string, which results from an approximation in the rotating beam equation. These shape functions depend on rotation speed and element position along the beam and account for the centrifugal stiffening effect. Using this new element and the Hermite cubic finite element, a convergence study of natural frequencies is performed, and it is found that the new element converges much more rapidly than the conventional Hermite cubic element for the first two modes at higher rotation speeds. The new element is also applied for uniform and tapered rotating beams to determine the natural frequencies, and the results compare very well with the published results given in the literature.

Time and Energy Complexity of Distributed Computation of a Class of Functions in Wireless Sensor Networks

We consider a scenario in which a wireless sensor network is formed by randomly deploying n sensors to measure some spatial function over a field, with the objective of computing a function of the measurements and communicating it to an operator station. We restrict ourselves to the class of type-threshold functions (as defined in the work of Giridhar and Kumar, 2005), of which max, min, and indicator functions are important examples: our discussions are couched in terms of the max function. We view the problem as one of message-passing distributed computation over a geometric random graph. The network is assumed to be synchronous, and the sensors synchronously measure values and then collaborate to compute and deliver the function computed with these values to the operator station. Computation algorithms differ in (1) the communication topology assumed and (2) the messages that the nodes need to exchange in order to carry out the computation. The focus of our paper is to establish (in probability) scaling laws for the time and energy complexity of the distributed function computation over random wireless networks, under the assumption of centralized contention-free scheduling of packet transmissions. First, without any constraint on the computation algorithm, we establish scaling laws for the computation time and energy expenditure for one-time maximum computation. We show that for an optimal algorithm, the computation time and energy expenditure scale, respectively, as Theta(radicn/log n) and Theta(n) asymptotically as the number of sensors n rarr infin. Second, we analyze the performance of three specific computation algorithms that may be used in specific practical situations, namely, the tree algorithm, multihop transmission, and the Ripple algorithm (a type of gossip algorithm), and obtain scaling laws for the computation time and energy expenditure as n rarr infin. In particular, we show that the computation time for these algorithms scales as Theta(radicn/lo- g n), Theta(n), and Theta(radicn log n), respectively, whereas the energy expended scales as , Theta(n), Theta(radicn/log n), and Theta(radicn log n), respectively. Finally, simulation results are provided to show that our analysis indeed captures the correct scaling. The simulations also yield estimates of the constant multipliers in the scaling laws. Our analyses throughout assume a centralized optimal scheduler, and hence, our results can be viewed as providing bounds for the performance with practical distributed schedulers.

Force constants and thermodynamic functions of iodine heptafluoride

Normal coordinate analysis of a molecule of the type XY7 (point group D5h) has been carried out using Wilson's FG, matrix method and the results have been utilized to calculate the force constants of IF7 from the available Raman and infrared data. Some of the assignments made previously by Lord and others have been revised and with the revised assignments the thermodynamic quantities of IF7 have been computed from 300°K to 1000°K under rigid rotator and harmonic oscillator approximation.

Potential functions for hydrogen bond interactions - III. Empirical Potential Function for the Peptide N-H...O=C Hydrogen Bond

A careful comparison of the distribution in the (R, θ)-plane of all NH ... O hydrogen bonds with that for bonds between neutral NH and neutral C=O groups indicated that the latter has a larger mean R and a wider range of θ and that the distribution was also broader than for the average case. Therefore, the potential function developed earlier for an average NH ... O hydrogen bond was modified to suit the peptide case. A three-parameter expression of the form {Mathematical expression}, with △ = R - Rmin, was found to be satisfactory. By comparing the theoretically expected distribution in R and θ with observed data (although limited), the best values were found to be p1 = 25, p3 = - 2 and q1 = 1 × 10-3, with Rmin = 2·95 Å and Vmin = - 4·5 kcal/mole. The procedure for obtaining a smooth transition from Vhb to the non-bonded potential Vnb for large R and θ is described, along with a flow chart useful for programming the formulae. Calculated values of ΔH, the enthalpy of formation of the hydrogen bond, using this function are in reasonable agreement with observation. When the atoms involved in the hydrogen bond occur in a five-membered ring as in the sequence[Figure not available: see fulltext.] a different formula for the potential function is needed, which is of the form Vhb = Vmin +p1△2 +q1x2 where x = θ - 50° for θ ≥ 50°, with p1 = 15, q1 = 0·002, Rmin = 2· Å and Vmin = - 2·5 kcal/mole. © 1971 Indian Academy of Sciences.

Potential functions for hydrogen bond interactions - IV. Minimum Energy Conformation of the α-Helical Structure of PoIy-L-Alanine

Making use of the empirical potential functions for peptide NH .. O bonds, developed in this laboratory, the relative stabilities of the rightand left-handed α-helical structures of poly-L-alanine have been investigated, by calculating their conformational energies (V). The value of Vmin of the right-handed helix (αP) is about - 10.4 kcal/mole, and that of the left-handed helix (αM) is about - 9.6 kcal/mole, showing that the former is lower in energy by 0.8 kcal/mole. The helical parameters of the stable conformation of αP are n ∼ 3.6 and h ∼ 1.5 Å. The hydrogen bond of length 2.85 Å and nonlinearity of about 10° adds about 4.0 kcal/ mole to the stabilising energy of the helix in the minimum enregy region. The energy minimum is not sharply defined, but occurs over a long valley, suggesting that a distribution of conformations (φ{symbol}, ψ) of nearly the same energy may occur for the individual residues in a helix. The experimental data of a-helical fibres of poly-L-alanine are in good agreement with the theoretical results for αP. In the case of proteins, the mean values of (φ{symbol}, ψ) for different helices are distributed, but they invariably occur within the contour for V = Vmin + 2 kcal/mole for αP.

On some integral properties of hypergeometric functions

In this note certain integrals involving hypergeometric functions have been evaluated in convenient and elegant forms. © 1971 Indian Academy of Sciences.