Tracking performance characterization and improvement of a piezoactuated micropositioning system based on an empirical index

Motion tracking is an important problem in micropositioning systems dedicated to ultra-precision robotic micromanipulation. This paper investigates the periodic motion tracking performance of a micropositioning system based on an empirical tracking performance index (TPI), which is proposed with the consideration of both tracking errors and tracking frequencies. To improve the TPI of a micropositioning system with piezoelectric actuation, a two-loop controller consisting of an _H∞$H_{\infty }$ robust controller and a disturbance observer is implemented. Experimental studies are conducted on an XY parallel micropositioning system for the motion tracking tests. Results demonstrate that a sole _H∞$H_{\infty }$ robust controller is insufficient to produce a satisfactory tracking performance with low-frequency control. In contrast, the two-loop controller endows the system with both a lower tracking error and a better TPI than the conventional robust control does. The experimental results not only validate the effectiveness of the proposed control method in improving tracking performance but also confirm the feasibility of the TPI in quantitatively characterizing the performance of a micropositioning system.     

An efficient parallel algorithm for building the separating tree

We present an efficient parallel algorithm for building the separating tree for a separable permutation. Our algorithm runs in O(log²n)$O\left({log}^{2}n\right)$ time using O(nlog^1.5n)$O\left(n{log}^{1.5}n\right)$ operations on the CREW PRAM and O(log²n)$O\left({log}^{2}n\right)$ time using O(nlognloglogn)$O(nlognloglogn)$ operations on the COMMON CRCW PRAM.     

The weight distributions of cyclic codes with two zeros and zeta functions

We consider the weight distribution of the binary cyclic code of length 2ⁿ−1$2^n-1$ with two zeros α^a,α^b${\alpha }^a,{\alpha }^b$. Our proof gives information in terms of the zeta function of an associated variety. We carry out an explicit determination of the weight distribution in two cases, for the cyclic codes with zeros α³,α⁵${\alpha }^3,{\alpha }^5$ and α,α¹¹$\alpha ,{\alpha }^{11}$. These are the smallest cases of two infinite families where finding the weight distribution is an open problem. Finally, an interesting application of our methods is that we can prove that these two codes have the same weight distribution for all odd n$n$.     

State-complexity hierarchies of uniform languages of alphabet-size length

We study the state complexity of certain simple languages. If A$A$ is an alphabet of k$k$ letters, then a k$k$-language   is a nonempty set of words of length k$k$, that is, a uniform language of length k$k$. We show that the minimal state complexity of a k$k$-language is k+2$k+2$, and the maximal, (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. We prove constructively that, for every i$i$ between the minimal and maximal bounds, there is a language of state complexity i$i$. We introduce a class of automata accepting sets of words that are permutations of A$A$; these languages define a complete hierarchy of complexities between k²−k+3$k^2-k+3$ and 2^k+1$2^k+1$. The languages of another class of automata, based on k$k$-ary trees, define a complete hierarchy of complexities between 2^k+1$2^k+1$ and (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. This provides new examples of uniform languages of maximal complexity.     

Non-linear polynomial selection for the number field sieve

We present an algorithm to find two non-linear polynomials for the Number Field Sieve integer factorization method. This algorithm extends Montgomery’s “two quadratics” method; for degree 3$3$, it gives two skewed polynomials with resultant O(N^5/4)$O\left(N^{5/4}\right)$, which improves on the Williams O(N^4/3)$O\left(N^{4/3}\right)$ result (Williams, 2010).     

Faster two-dimensional pattern matching with rotations

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n²m³)$\mathrm{O}(n^2{m}^3)$, where the size of the text is n×n$n\times n$ and the size of the pattern is m×m$m\times m$. In this paper we present a new algorithm for the problem whose running time is O(n²m²)$\mathrm{O}(n^2{m}^2)$.     

On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field

We derive an explicit count for the number of singular n×n$n\times n$ Hankel (Toeplitz) matrices whose entries range over a finite field with q$q$ elements by observing the execution of the Berlekamp/Massey algorithm on its elements. Our method yields explicit counts also when some entries above or on the anti-diagonal (diagonal) are fixed. For example, the number of singular n×n$n\times n$ Toeplitz matrices with 0’s on the diagonal is q²ⁿ⁻³+qⁿ⁻¹−qⁿ⁻²$q^{2n-3}+q^{n-1}-q^{n-2}$.     

An approximation algorithm to the k-Steiner Forest problem

Given a graph G$G$, an integer k$k$, and a demand set D={(_s1,_t1),…,(_sl,_tl)}$D=\{(s_1,t_1),\dots ,(s_l,t_l)\}$, the k$k$-Steiner Forest problem finds a forest in graph G$G$ to connect at least k$k$ demands in D$D$ such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n^2/3logl)$O(n^{2/3}logl)$. We give a simpler and faster approximation algorithm to this problem with performance ratio O(n^2/3logk)$O(n^{2/3}logk)$ via greedy approach, improving the previously best known ratio in the literature.     

On the size of Boyer–Moore automata

In this work we study the size of Boyer–Moore automata introduced in Knuth, Morris & Pratt’s famous paper on pattern matching. We experimentally show that a finite class of binary patterns produce very large Boyer–Moore automata, and find one particular case which we conjecture, generates automata of size Ω(m⁶)$\Omega \left(m^6\right)$. Further experimental results suggest that the maximal size could be a polynomial of O(m⁷)$O\left(m^7\right)$, or even an exponential O(2^0.4m)$O\left(2^{0.4m}\right)$, where m$m$ is the length of the pattern.     

Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor

We consider a two-edge connected, undirected graph G=(V,E)$G=(V,E)$, with n$n$ nodes and m$m$ non-negatively real weighted edges, and a single source shortest paths tree (SPT) T$T$ of G$G$ rooted at an arbitrary node r$r$. If an edge in T$T$ is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge  , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog²n)$O\left(m{log}^{2}n\right)$ time and O(m)$O\left(m\right)$ space algorithm to find a best swap edge for every edge of T$T$, thus improving for m=o(n²/log²n)$m=o(n^2/{log}^{2}n)$ the previously known O(n²)$O\left(n^2\right)$ time and space complexity algorithm.     

Computing the pathwidth of directed graphs with small vertex cover

We give an algorithm that computes the pathwidth of a given directed graph D   in 3^τ(D)n^O(1)$3^{\tau (D)}{n}^{O(1)}$ time where n is the number of vertices of D   and τ(D)$\tau (D)$ is the number of vertices of a minimum vertex cover of the underlying undirected graph of D. This result extends that of [5] for undirected graphs to directed graphs. Moreover, our algorithm is based on a standard dynamic programming with a simple tree-pruning trick, which is extremely simple and easy to implement. An additional advantage of our algorithm is that a minimum vertex cover appears in the analysis but not in the algorithm itself, in contrast to the algorithm of [5] which needs to compute a minimum vertex cover.     

Alternative proof of the Lyndon–Schützenberger Theorem

Some observations on products of primitive words are discussed. By these results, alternative proof is given for the Lyndon–Schützenberger Theorem, which says that every solution of the equation a^mbⁿ=c^k$a^m{b}^n=c^k$ over Σ^*${\Sigma }^{*}$ is trivial.     

Load-balancing on swapped or OTIS networks

Existing local iterative algorithms for load-balancing are ill-suited to many large-scale interconnection networks. The main reasons are complicated Laplace spectrum computations and flow scheduling strategies. Many large-scale networks are modular and/or hierarchically structured, a prime example being the class of swapped or OTIS networks that have received much attention in recent years. We propose a new local scheme, called DED-X, for load-balancing on homogeneous and heterogeneous swapped/OTIS networks. Our scheme needs spectral information only for the much smaller basis or factor graph, which is of size O(n)$O\left(n\right)$ rather than O(n²)$O\left(n^2\right)$, and it schedules load flow on intragroup and intergroup links separately. We justify the improvements offered by DED-X schemes over traditional X schemes analytically and verify the advantages of our approach, in terms of efficiency and stability, via simulation.     

A parameterized view on matroid optimization problems

Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial n^O(k)$n^{O\left(k\right)}$ time brute force algorithm for finding a k$k$-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅n^O(1)$f\left(k\right)\cdot n^{O\left(1\right)}$) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ?$?$, then we can determine in randomized time f(k,?)⋅n^O(1)$f(k,?)\cdot n^{O\left(1\right)}$ whether there is an independent set that is the union of k$k$ blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k$k$-element set in the intersection of ?$?$ matroids, or finding k$k$ terminals in a network such that each of them can be connected simultaneously to the source by ?$?$ disjoint paths.