The computational complexity of rules for the character table of Sn

The Murnaghan–Nakayama rule is the classical formula for computing the character table of S_n. Y. Roichman (Adv. Math. 129 (1997) 25) has recently discovered a rule for the Kazhdan–Lusztig characters of q Hecke algebras of type A, which can also be used for the character table of S_n. For each of the two rules, we give an algorithm for computing entries in the character table of S_n. We then analyze the computational complexity of the two algorithms, and in the case of characters indexed by partitions in the (k,ℓ) hook, compare their complexities to each other. It turns out that the algorithm based on the Murnaghan–Nakayama rule requires far less operations than the other algorithm. We note the algorithms’ complexities’ relation to two enumeration problems of Young diagrams and Young tableaux.     

Optimizing fixed-size stochastic controllers for POMDPs and decentralized POMDPs

POMDPs and their decentralized multiagent counterparts, DEC-POMDPs, offer a rich framework for sequential decision making under uncertainty. Their high computational complexity, however, presents an important research challenge. One way to address the intractable memory requirements of current algorithms is based on representing agent policies as finite-state controllers. Using this representation, we propose a new approach that formulates the problem as a nonlinear program, which defines an optimal policy of a desired size for each agent. This new formulation allows a wide range of powerful nonlinear programming algorithms to be used to solve POMDPs and DEC-POMDPs. Although solving the NLP optimally is often intractable, the results we obtain using an off-the-shelf optimization method are competitive with state-of-the-art POMDP algorithms and outperform state-of-the-art DEC-POMDP algorithms. Our approach is easy to implement and it opens up promising research directions for solving POMDPs and DEC-POMDPs using nonlinear programming methods.     

Arc-length-based Lyapunov tests for convergence and stability with applications to systems having a continuum of equilibria

In this paper, fundamental relationships are established between convergence of solutions, stability of equilibria, and arc length of orbits. More specifically, it is shown that a system is convergent if all of its orbits have finite arc length, while an equilibrium is Lyapunov stable if the arc length (considered as a function of the initial condition) is continuous at the equilibrium, and semistable if the arc length is continuous in a neighborhood of the equilibrium. Next, arc-length-based Lyapunov tests are derived for convergence and stability. These tests do not require the Lyapunov function to be positive definite. Instead, these results involve an inequality relating the right-hand side of the differential equation and the Lyapunov function derivative. This inequality makes it possible to deduce properties of the arc length function and thus leads to sufficient conditions for convergence and stability. Finally, it is shown that the converses of all the main results hold under additional assumptions. Examples are included to illustrate how our results are particularly suited for analyzing stability of systems having a continuum of equilibria.     

Master's Degrees in Software Engineering: An Analysis of 28 University Programs

The Software Engineering Institute published the last reference curriculum for a master's in software engineering in 1991. In 2007, a coalition from academia, industry, and government began creating a new reference curriculum. An early step was to establish a baseline of graduate education by surveying 28 master's programs in software engineering. The survey was largely limited to US schools. Key findings showed that the universities viewed software engineering largely as a specialization of computer science, that faculty size is generally small with few dedicated professors, and that new master's programs continue to start despite the decrease in computer science majors over the past few years. We used the IEEE Computer Society's Software Engineering Body of Knowledge (SWEBOK) to structure our analysis of the 28 curricula, focusing primarily on courses and topics required or semirequired of all students. (A course is semirequired if there is at least a 50 percent chance a student must take it.) Major findings show wide variation in the depth and breadth of SWEBOK coverage in required and semirequired courses, less than 40 percent of all programs requiring an introductory course on software engineering, and many universities having required and semirequired courses that are peripheral to SWEBOK.     

Non-linear system identification using Hammerstein and non-linear feedback models with piecewise linear static maps

We consider the identification of Hammerstein/non-linear feedback models by approximating internal non-linearities using piecewise linear static maps. The resulting method utilizes a point-slope parameterization that leads to a computationally tractable optimization problem. The computational appeal of this technique is derived from the fact that the method only requires a matrix inverse and singular value decomposition. Furthermore, the identification method simultaneously identifies the linear dynamic and static non-linear blocks without requiring prior assumptions on the form of the static non-linearity.     

State estimation for linear and non-linear equality-constrained systems

This article addresses the state-estimation problem for linear and non-linear systems for the case in which prior knowledge is available in the form of an equality constraint. The equality-constrained Kalman filter (KF) is derived as the maximum-a-posteriori solution to the equality-constrained state-estimation problem for linear and Gaussian systems and is compared to alternative algorithms. Then, four novel algorithms for non-linear equality-constrained state estimation based on the unscented KF are presented, namely, the equality-constrained unscented KF, the projected unscented KF, the measurement-augmentation unscented KF, and the constrained unscented KF. Finally, these methods are compared on linear and non-linear examples.     

Combined L2/H∞ model reduction

A model-reduction problem is considered which involves both L ₂ (quadratic) and H _∞ (worst-case frequency-domain) aspects. Specifically, the goal of the problem is to minimize an L ₂ model-reduction criterion subject to a prespecified H _∞ constraint on the model-reduction error. The principal result is a sufficient condition for characterizing reduced-order models with bounded L ₂ and H _∞ approximation error. The sufficient condition involves a system of modified Riccati equations coupled by an oblique projection, i.e. idempotent matrix. When the H _∞ constraint is absent, the sufficient condition specializes to the L ₂ model-reduction result given by Hyland and Bernstein (1985).     

Characterization of Powdered Yacon (<Emphasis Type="Italic">Smallanthus sonchifolius</Emphasis>) Juice and Pulp

The present work aimed to study the drying behaviour of a 40oBrix concentrated yacon juice preparation using native corn starch as the encapsulating agent and also the drying of yacon pulp. The experimental trials were carried out in a forced air dryer at temperatures of 50, 60 and 70°C for 5 h. The values for the equilibrium moisture content were 0.0071, 0.0052 and 0.0050 g/g dry matter (d.m.) for the yacon pulp and 0.0075, 0.0030 and 0.0030 g/g d.m. for the encapsulated juice at 50, 60 and 70°C, respectively, resulting in values for water activity below 0.25. The dehydrated products were ground and then visualized using a scanning electronic microscope. Powdered yacon pulp showed a laminar-type structure, and good encapsulation of the yacon juice by starch was observed in the samples of concentrated juice powder. The glass transition temperatures of the encapsulated concentrated juice powder were 44.74, 45.14 and 49.72°C for water activity values of 0.15, 0.07 and 0.03, respectively, and for the yacon pulp powder, it was 48.78°C at a water activity of 0.13.     

Average-preserving symmetries and energy equipartition in linear Hamiltonian systems

This paper analyzes energy equipartition in linear Hamiltonian systems in a deterministic setting. We consider the group of phase space symmetries of a stable linear Hamiltonian system, and characterize the subgroup of symmetries whose elements preserve the time averages of quadratic functions along the trajectories of the system. As a corollary, we show that if the system has simple eigenvalues, then every symmetry preserves averages of quadratic functions. As an application of our results to linear undamped lumped-parameter systems, we provide a novel proof of the virial theorem, which states that the total energy is equipartitioned on the average between the kinetic energy and the potential energy. We also show that under the assumption of distinct natural frequencies, the time-averaged energies of two identical substructures of a linear undamped structure are equal. Examples are provided to illustrate the results.     

Dielectric breakdown strength correlation with time-to-failureduring wet aging of XLPE-insulated cables

This paper reviews two sets of failure information, the GMTF (a parameter obtained from time-to-failure results) and GMBD stress (a parameter that is calculated from AC breakdown test results), and suggests a correlation. The test results were obtained from accelerated aging experiments on full-sized medium voltage cables in carefully controlled and monitored water-filled tanks. Results show that the ambient temperature AC breakdown strength for equivalently aged cables is influenced primarily by voltage stress during aging-not by the aging temperature. The AC breakdown strength on equivalently aged cables was also shown to decrease with reductions in the aging voltage at all aging temperatures