On average and highest number of flips in pancake sorting

We are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from the top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down. We are interested in the largest value of the number of flips needed to sort a stack of $n$ pancakes, both in the unburnt version ($f\left(n\right)$) and in the burnt version ($g\left(n\right)$).We present exact values of $f\left(n\right)$ up to $n=19$ and of $g\left(n\right)$ up to $n=17$ and disprove a conjecture of Cohen and Blum by showing that the burnt stack $?I_{15}$ is not the hardest to sort for $n=15$.We also show that sorting a random stack of $n$ unburnt pancakes can be done with at most $17n/12+O\left(1\right)$ flips on average. The average number of flips of the optimal algorithm for sorting stacks of $n$ burnt pancakes is shown to be between $n+\Omega (n/logn)$ and $7n/4+O\left(1\right)$ and we conjecture that it is $n+\Theta (n/logn)$.Finally we show that sorting the stack $?I_n$ needs at least $?(3n+3)/2?$ flips, which slightly increases the lower bound on $g\left(n\right)$. This bound together with the upper bound for sorting $?I_n$ found by Heydari and Sudborough in 1997 [10] gives the exact number of flips to sort it for $n\equiv 3(mod4)$ and $n\ge 15$.     

State complexity of power

The number of states in a deterministic finite automaton (DFA) recognizing the language $L^k$, where $L$ is regular language recognized by an $n$-state DFA, and $k?2$ is a constant, is shown to be at most $n{2}^{(k?1)n}$ and at least $(n?k)2^{(k?1)(n?k)}$ in the worst case, for every $n>k$ and for every alphabet of at least six letters. Thus, the state complexity of $L^k$ is $\Theta \left(n{2}^{(k?1)n}\right)$. In the case $k=3$ the corresponding state complexity function for $L^3$ is determined as $\frac{6n?3}{8}{4}^n?(n?1)2^n?n$ with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of $L^k$ is demonstrated to be $nk$. This bound is shown to be tight over a two-letter alphabet.     

Longest paths and cycles in faulty star graphs

In this paper, we investigate the star graph $S_n$ with faulty vertices and/or edges from the graph theoretic point of view. We show that between every pair of vertices with different colors in a bicoloring of $S_n$, $n⩾4$, there is a fault-free path of length at least $n!-2f_v-1$, and there is a path of length at least $n!-2f_v-2$ joining a pair of vertices with the same color, when the number of faulty elements is $n-3$ or less. Here, $f_v$ is the number of faulty vertices. $S_n$, $n⩾4$, with at most $n-2$ faulty elements has a fault-free cycle of length at least $n!-2f_v$ unless the number of faulty elements are $n-2$ and all the faulty elements are edges incident to a common vertex. It is also shown that $S_n$, $n⩾4$, is strongly hamiltonian-laceable if the number of faulty elements is $n-3$ or less and the number of faulty vertices is one or less.     

Numerical results on some generalized random Fibonacci sequences

Random Fibonacci sequences are stochastic versions of the classical Fibonacci sequence $f_{n+1}=f_n+f_{n?1}$ for $n>0$, and $f_0=f_1=1$, obtained by randomizing one or both signs on the right side of the defining equation and/or adding a “growth parameter.” These sequences may be viewed as coming from a sequence of products of i.i.d. random matrices and their rate of growth measured by the associated Lyapunov exponent. Following the techniques presented by Embree and Trefethen in their numerical paper Embree and Trefethen (1999) [2], we study the behavior of the Lyapunov exponents as a function of the probability $p$ of choosing $+$ in the sign randomization.     

Eigenvalues of a real supersymmetric tensor

In this paper, we define the symmetric hyperdeterminant, eigenvalues and E-eigenvalues of a real supersymmetric tensor. We show that eigenvalues are roots of a one-dimensional polynomial, and when the order of the tensor is even, E-eigenvalues are roots of another one-dimensional polynomial. These two one-dimensional polynomials are associated with the symmetric hyperdeterminant. We call them the characteristic polynomial and the E-characteristic polynomial of that supersymmetric tensor. Real eigenvalues (E-eigenvalues) with real eigenvectors (E-eigenvectors) are called H-eigenvalues (Z-eigenvalues). When the order of the supersymmetric tensor is even, H-eigenvalues (Z-eigenvalues) exist and the supersymmetric tensor is positive definite if and only if all of its H-eigenvalues (Z-eigenvalues) are positive. An $m\mathrm{th}$-order $n$-dimensional supersymmetric tensor where $m$ is even has exactly $n{(m-1)}^{n-1}$ eigenvalues, and the number of its E-eigenvalues is strictly less than $n{(m-1)}^{n-1}$ when $m\ge 4$. We show that the product of all the eigenvalues is equal to the value of the symmetric hyperdeterminant, while the sum of all the eigenvalues is equal to the sum of the diagonal elements of that supersymmetric tensor, multiplied by ${(m-1)}^{n-1}$. The $n{(m-1)}^{n-1}$ eigenvalues are distributed in $n$ disks in $C$. The centers and radii of these $n$ disks are the diagonal elements, and the sums of the absolute values of the corresponding off-diagonal elements, of that supersymmetric tensor. On the other hand, E-eigenvalues are invariant under orthogonal transformations.     

On the bounds of feedback numbers of (n,k)-star graphs

The feedback number of a graph G is the minimum number of vertices whose removal from G results in an acyclic subgraph. We use $f(n,k)$ to denote the feedback number of the $(n,k)$-star graph $S_{n,k}$ and $p(n,k)$ the number of k-permutations of an n-element set. This paper proves that$p(n,k)?2(k?1)!\left(\begin{array}{c}\hfill n\hfill \\ \hfill k?1\hfill \end{array}\right)?f(n,k)?p(n,k)?2(k?1)!\sum _{i=1}^{\theta }\left(\begin{array}{c}\hfill n?2i+1\hfill \\ \hfill k?i\hfill \end{array}\right),$ where $\theta =\min \{k?1,n?k+1\}$.     

Equations over sets of integers with addition only

Systems of equations of the form $X=Y+Z$ and $X=C$ are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set $S\subseteq \mathbb{N}$ there exists a system with a unique (least, greatest) solution containing a component T with $S=\{n|16n+13\in T\}$. Testing solution existence for these equations is ${\mathrm{\Pi }}_1^0$-complete, solution uniqueness is ${\mathrm{\Pi }}_2^0$-complete, and finiteness of the set of solutions is ${\mathrm{\Sigma }}_3^0$-complete. A similar construction for integers represents any hyper-arithmetical set $S\subseteq \mathbb{Z}$ by a set $T\subseteq \mathbb{Z}$ satisfying $S=\{n|16n\in T\}$, whereas testing solution existence is ${\mathrm{\Sigma }}_1^1$-complete.     

Deterministic extractors for small-space sources

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on ${\{0,1\}}^n$ as sources generated by width $2^s$ branching programs. Specifically, there is a constant $\eta >0$ such that for any $\zeta >n^{?\eta }$, our algorithm extracts $m=(\delta ?\zeta )n$ bits that are exponentially close to uniform (in variation distance) from space s sources with min-entropy δn, where $s=\Omega ({\zeta }^{3}n)$. Previously, nothing was known for $\delta ?1/2$, even for space 0. Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of r independent smaller sources over ${\{0,1\}}^{?}$, where the total min-entropy over all the smaller sources is k. We give deterministic extractors for such sources when k is as small as $\mathsf{polylog}(r)$, for small enough ?.     

The best keying protocol for sensor networks

Many sensor networks (especially networks of mobile sensors or networks that are deployed to monitor crisis situations) are deployed in an arbitrary and unplanned fashion. Thus, any sensor in such a network can end up being adjacent to any other sensor in the network. To secure the communications between every pair of adjacent sensors in such a network, each sensor $x$ in the network needs to store $n?1$ symmetric keys that sensor $x$ shares with all the other sensors, where $n$ is an upper bound on the number of sensors in the network. This storage requirement of the keying protocol is rather severe, especially when $n$ is large and the available storage in each sensor is modest. Earlier efforts to redesign this keying protocol and reduce the number of keys to be stored in each sensor have produced protocols that are vulnerable to impersonation, eavesdropping, and collusion attacks. In this paper, we present a fully secure keying protocol where each sensor needs to store $(n+1)/2$ keys, which is much less than the $n?1$ keys that need to be stored in each sensor in the original keying protocol. We also show that in any fully secure keying protocol, each sensor needs to store at least $(n?1)/2$ keys.     

Innovation based on Gaussian elimination to compute generalized inverse AT,S(2)

In this paper, we execute elementary row and column operations on the partitioned matrix $\left(\begin{array}{cc}\hfill GAG\hfill & \hfill G\hfill \\ \hfill G\hfill & \hfill 0\hfill \end{array}\right)$ into $\left(\begin{array}{cc}\hfill \left(\begin{array}{cc}\hfill I_s\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill \end{array}\right)\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill ?A_{T,S}^{\left(2\right)}\hfill \end{array}\right)$to compute generalized inverse $A_{T,S}^{\left(2\right)}$ of a given complex matrix $A$, where $G$ is a matrix such that $R\left(G\right)=T$ and $N\left(G\right)=S$. The total number of multiplications and divisions operations is $T(m,n,s)=2m{n}^2+\frac{4m?s?1}{2}ns+(m?s)ns+mns$ and the upper bound of $T(m,n,s)$ is less than $6m{n}^2?\frac{3}{2}{n}^3?\frac{1}{2}{n}^2$ when $n\le m$. A numerical example is shown to illustrate that this method is correct.     

A unified theory of structural tractability for constraint satisfaction problems

In this paper we derive a generic form of structural decomposition for the constraint satisfaction problem, which we call a guarded decomposition. We show that many existing decomposition methods can be characterised in terms of finding guarded decompositions satisfying certain specified additional conditions.Using the guarded decomposition framework we are also able to define a new form of decomposition, which we call a spread-cut. We show that the discovery of width-k spread-cut decompositions is tractable for each k, and that spread-cut decompositions strongly generalise many existing decomposition methods. Finally we exhibit a family of hypergraphs $H_n$, for $n=1,2,3\dots$, where the minimum width of any hypertree decomposition of each $H_n$ is 3n, but the width of the best spread-cut decomposition is only $2n+1$.     

The Laplacian spectral radius of bicyclic graphs with a given girth

Let $?(n,g)$ be the class of bicyclic graphs on $n$ vertices with girth $g$. Let ${?}_1(n,g)$ be the subclass of $?(n,g)$ consisting of all bicyclic graphs with two edge-disjoint cycles and ${?}_2(n,g)=?(n,g)?{?}_1(n,g)$. This paper determines the unique graph with the maximal Laplacian spectral radius among all graphs in ${?}_1(n,g)$ and ${?}_2(n,g)$, respectively. Furthermore, the upper bound of the Laplacian spectral radius and the extremal graph for $?(n,g)$ are also obtained.