On the Hopcroft’s minimization technique for DFA and DFCA

We show that the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires $O(nlogn)$ steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu.     

Simulations of Shor’s algorithm using matrix product states

We show that under the matrix product state formalism the states produced in Shor’s algorithm can be represented using \(O(\max (4lr^2, 2^{2l}))\) space, where l is the number of bits in the number to factorise and r is the order and the solution to the related order-finding problem. The reduction in space compared to an amplitude formalism approach is significant, allowing simulations as large as 42 qubits to be run on a single processor with 32 GB RAM. This approach is readily adapted to a distributed memory environment, and we have simulated a 45-qubit case using 8 cores with 16 GB RAM in approximately 1 h.     

Multiclass classification of Parkinson’s disease using different classifiers and LLBFS feature selection algorithm

Since approximately 90% of the people with PD (Parkinson’s disease) suffer from speech disorders including disorders of laryngeal, respiratory and articulatory function, using voice analysis disease can be diagnosed remotely at an early stage with more reliability and in an economic way. All previous works are done to distinguish healthy people from people with Parkinson’s disease (PWP). In this paper, we propose to go further by multiclass classification with three classes of Parkinson stages and healthy control. So we have used 40 features dataset, all the features are analyzed and 9 features are selected to classify PWP subjects in four classes, based on unified Parkinson’s disease Rating Scale (UPDRS). Various classifiers are used and their comparison is done to find out which one gives the best results. Results show that the subspace discriminant reach more than 93% overall classification accuracy.     

Three-qubit Grover’s algorithm using superconducting quantum interference devices in cavity-QED

We present a scheme for the implementation of three-qubit Grover’s algorithm using four-level superconducting quantum interference devices (SQUIDs) coupled to a superconducting resonator. The scheme is based on resonant, off-resonant interaction of the cavity field with SQUIDs and application of classical microwave pulses. We show that adjustment of SQUID level spacings during the gate operations, adiabatic passage, and second-order detuning are not required that leads to faster implementation. We also show that the marked state can be searched with high fidelity even in the presence of unwanted off-resonant interactions, level decay, and cavity dissipation.     

Enhanced Tilley’s bundling algorithm using memory reduction Monte Carlo method

Abstract When pricing American-style options by Tilleys bundling algorithm, one has to store the simulated asset prices at all time steps on all paths in order to determine when to exercise the options. If N time steps and M paths are used, then the storage requirement is M N. In this paper, we improve Tilleys bundling algorithm [6] by applying our backward-path method, which requires only O(M) storage. The only additional computational cost is that we have to generate each random number twice instead of once. For machines with limited memory, we can now use larger values of M and N to improve the accuracy in pricing options.     

Solving a class of nonlinear optimal control problems via he’s variational iteration method

This paper presents an analytical approximate solution for a class of nonlinear quadratic optimal control problems. The proposed method consists of a Variational Iteration Method (VIM) together with a shooting method like procedure, for solving the extreme conditions obtained from the Pontryagin’s Maximum Principle (PMP). This method is applicable for a large class of nonlinear quadratic optimal control problems. In order to use the proposed method, a control design algorithm with low computational complexity is presented. Through the finite iterations of algorithm, a suboptimal control law is obtained for the nonlinear optimal control problem. Two illustrative examples are given to demonstrate the simplicity and efficiency of the proposed method.     

Modeling and Solving Human Arm’s Posture in Reachablity Analysis

Reachability is a key criterion in maintenance design, and human arm is the main object in reachability analysis. The human arm’s DOF is reduced, and applying military standards and human physiological constraints, the simplified arm model of 7-DOF using D-H method is built up. Particle Swarm Optimization (PSO) is used to acquire the shoulder, arm and hand posture with adaptive fitness function. A detailed reachability analysis is accomplished for disassembling the bolts from crank shaft is given as an exam...     

Establishing the equivalence between Szegedy’s and coined quantum walks using the staggered model

Coined quantum walks (QWs) are being used in many contexts with the goal of understanding quantum systems and building quantum algorithms for quantum computers. Alternative models such as Szegedy’s and continuous-time QWs were proposed taking advantage of the fact that quantum theory seems to allow different quantized versions based on the same classical model, in this case the classical random walk. In this work, we show the conditions upon which coined QWs are equivalent to Szegedy’s QWs. Those QW models have in common a large class of instances, in the sense that the evolution operators are equal when we convert the graph on which the coined QW takes place into a bipartite graph on which Szegedy’s QW takes place, and vice versa. We also show that the abstract search algorithm using the coined QW model can be cast into Szegedy’s searching framework using bipartite graphs with sinks.     

Enhancing CAD-based shape optimisation by automatically updating the CAD model’s parameterisation

Structural and Multidisciplinary Optimization - This paper presents an approach which increases the flexibility of a computer-aided design (CAD) model by automatically refining its parameterization...     

The Interplay Between the Speaker’s and the Hearer’s Perspective

The neutralization of contrasts in form or meaning that is sometimes observed in language production and comprehension is at odds with the classical view that language is a systematic one-to-one pairing of forms and meanings. This special issue is concerned with patterns of forms and meanings in language. The papers in this special issue arose from a series of workshops that were organized to explore variants of bidirectional Optimality Theory and Game Theory as models of the interplay between the speaker’s and the hearer’s perspective.     

Lawler’s minmax cost algorithm: optimality conditions and uncertainty

The well-known \(O(n^2)\) minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an \(O(n^2)\) algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.     

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we solve this question and prove an upper bound of 3\frac1318 n² + O(n){3\frac{13}{18} n^2 + O(n)} for the complexity of this algorithm. We also show a lower bound of 1\frac56 n² - O(n){1\frac{5}{6} n^2 - O(n)} for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of \frac56 n² + O(n){\frac{5}{6} n^2 + O(n)} for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5\frac34n²+O(n){5\frac{3}{4}n^2+O(n)} and a lower bound of \frac18n²-O(n){\frac{1}{8}n^2-O(n)} for its stabilization time. For this algorithm we prove an upper bound of 1\frac12n² + O(n){1\frac{1}{2}n^2 + O(n)} and show a lower bound of n ²−O(n). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and our algorithm is better than both.     

Optimizing the double inverted pendulum’s performance via the uniform neuro multiobjective genetic algorithm

An inverted pendulum is a sensitive system of highly coupled parameters, in laboratories, it is popular for modelling nonlinear systems such as mechanisms and control systems, and also for optimizing programmes before those programmes are applied in real situations. This study aims to find the optimum input setting for a double inverted pendulum (DIP), which requires an appropriate input to be able to stand and to achieve robust stability even when the system model is unknown. Such a DIP input could be widely applied in engineering fields for optimizing unknown systems with a limited budget. Previous studies have used various mathematical approaches to optimize settings for DIP, then have designed control algorithms or physical mathematical models. This study did not adopt a mathematical approach for the DIP controller because our DIP has five input parameters within its nondeterministic system model. This paper proposes a novel algorithm, named UniNeuro, that integrates neural networks (NNs) and a uniform design (UD) in a model formed by input and response to the experimental data (metamodel). We employed a hybrid UD multiobjective genetic algorithm (HUDMOGA) for obtaining the optimized setting input parameters. The UD was also embedded in the HUDMOGA for enriching the solution set, whereas each chromosome used for crossover, mutation, and generation of the UD was determined through a selection procedure and derived individually. Subsequently, we combined the Euclidean distance and Pareto front to improve the performance of the algorithm. Finally, DIP equipment was used to confirm the settings. The proposed algorithm can produce 9 alternative configured input parameter values to swing-up then standing in robust stability of the DIP from only 25 training data items and 20 optimized simulation results. In comparison to the full factorial design, this design can save considerable experiment time because the metamodel can be formed by only 25 experiments using the UD. Furthermore, the proposed algorithm can be applied to nonlinear systems with multiple constraints.     

A new method of classification for Landsat data using the ‘watershed’ algorithm

Many methods of classifying satellite imagery have been suggested. Most of the accepted methods, either supervised or unsupervised, are founded on the assumption that the radiance values of a particular ground cover type can be characterized by some probability distribution having a central value(s) and a range parameter(s). This assumption is rarely, if ever, tenable and hence the methods must produce unnecessarily high rates of misclassification. Thus there is a need for an approach which avoids this type of assumption. Pattern recognition techniques, e.g. the ‘watershed’ algorithm, can be used to divide up the radiance-frequency domain, provided the radiance values can be reduced to 2 dimensions. These methods do not presuppose any ‘shape’ for the radiance-frequency distributions and therefore provide an unbiased aid to the interpretation of satellite imagery.     

A study on measuring surface deformation of the L’Aquila region using the StaMPS technique

This research compares two time-series interferometric synthetic aperture radar (InSAR) methods, namely persistent scatterer SAR interferometry (PS-InSAR) and small baseline subset (SBAS) to retrieve the deformation signal from pixels with different scattering characteristics. These approaches are used to estimate the surface deformation in the L’Aquila region in Central Italy where an earthquake of magnitude Mw 6.3 occurred on 6 April 2009. Fourteen Environmental Satellite (ENVISAT) C-band Advanced Synthetic Aperture Radar (ASAR) images, covering the pre-seismic, co-seismic, and post-seismic period, are used for the study. Both the approaches effectively extract measurement pixels and show a similar deformation pattern in which the north-west and south-east regions with respect to the earthquake epicentre show movement in opposite directions. The analysis has revealed that the PS-InSAR method extracted more number of measurement points (21,103 pixels) as compared to the SBAS method (4886 pixels). A comparison of velocity estimates shows that out of 833 common pixels in both the methods, about 62% (517 pixels) have the mean velocity difference below 3 mm year^?1 and nearly 66% pixels have difference below 5 mm year^?1. It is concluded that StaMPS-based PS-InSAR method performs better in terms of extracting more number of measurement pixels and in the estimation of mean line of sight (LOS) velocity as compared to SBAS method.