The categories L-\mathbf{Top}_{0} and L-\mathbf{Sob} as epireflective hulls

We show that the category \(L\) - \(\mathbf{Top}_{0}\) of \(T_{0}\) - \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}\) of \(L\) -topological spaces and the category \(L\) - \(\mathbf{Sob}\) of sober \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}_{0}\) .     

Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

Universal regular control for generic semilinear systems

We consider discrete-time projective semilinear control systems \(\xi _{t+1} = A(u_t) \cdot \xi _t\) , where the states \(\xi _t\) are in projective space \(\mathbb {R}\hbox {P}^{d-1}\) , inputs \(u_t\) are in a manifold \(\mathcal {U}\) of arbitrary finite dimension, and \(A :\mathcal {U}\rightarrow \hbox {GL}(d,\mathbb {R})\) is a differentiable mapping. An input sequence \((u_0,\ldots ,u_{N-1})\) is called universally regular if for any initial state \(\xi _0 \in \mathbb {R}\hbox {P}^{d-1}\) , the derivative of the time- \(N\) state with respect to the inputs is onto. In this paper, we deal with the universal regularity of constant input sequences \((u_0, \ldots , u_0)\) . Our main result states that generically in the space of such systems, for sufficiently large \(N\) , all constant inputs of length \(N\) are universally regular, with the exception of a discrete set. More precisely, the conclusion holds for a \(C^2\) -open and \(C^\infty \) -dense set of maps \(A\) , and \(N\) only depends on \(d\) and on the dimension of \(\mathcal {U}\) . We also show that the inputs on that discrete set are nearly universally regular; indeed, there is a unique non-regular initial state, and its corank is 1. In order to establish the result, we study the spaces of bilinear control systems. We show that the codimension of the set of systems for which the zero input is not universally regular coincides with the dimension of the control space. The proof is based on careful matrix analysis and some elementary algebraic geometry. Then the main result follows by applying standard transversality theorems.     

Fault tolerance of hypercubes and folded hypercubes

Let \(G = (V,E)\) be a connected graph. The conditional edge connectivity \(\lambda _\delta ^k(G)\) is the cardinality of the minimum edge cuts, if any, whose deletion disconnects \(G\) and each component of \(G - F\) has \(\delta \ge k\) . We assume that \(F \subseteq E\) is an edge set, \(F\) is called edge extra-cut, if \(G - F\) is not connected and each component of \(G - F\) has more than \(k\) vertices. The edge extraconnectivity \(\lambda _\mathrm{e}^k(G)\) is the cardinality of the minimum edge extra-cuts. In this paper, we study the conditional edge connectivity and edge extraconnectivity of hypercubes and folded hypercubes.     

Approximation of integrable functions based on \phi -transform

Let \(E\) be a bounded subset of real line which contains its infimum and supremum. In this paper, we have defined the \(\phi -\) transform and its inverse, where \(\phi \) is a function from \(E\) into \((0,1]\) . We will have shown that real-valued integrable functions on \([a, b]\) and real-valued continuous functions on \(E\) can be approximated by this transformation with an arbitrary precision.     

Informational correlation between two parties of a quantum system: spin-1/2 chains

We introduce the informational correlation \(E^{AB}\) between two interacting quantum subsystems \(A\) and \(B\) of a quantum system as the number of arbitrary parameters \(\varphi _i\) of a unitary transformation \(U^A\) (locally performed on the subsystem \(A\) ) which may be detected in the subsystem \(B\) by the local measurements. This quantity indicates whether the state of the subsystem \(B\) may be effected by means of the unitary transformation applied to the subsystem \(A\) . Emphasize that \(E^{AB}\ne E^{BA}\) in general. The informational correlations in systems with tensor product initial states are studied in more details. In particular, it is shown that the informational correlation may be changed by the local unitary transformations of the subsystem \(B\) . However, there is some non-reducible part of \(E^{AB}(t)\) which may not be decreased by any unitary transformation of the subsystem \(B\) at a fixed time instant \(t\) . Two examples of the informational correlations between two parties of the four-node spin-1/2 chain with mixed initial states are studied. The long chains with a single initially excited spin (the pure initial state) are considered as well.     

Growth rates for persistently excited linear systems

We consider a family of linear control systems \(\dot{x}=Ax+\alpha Bu\) on \(\mathbb {R}^d\) , where \(\alpha \) belongs to a given class of persistently exciting signals. We seek maximal \(\alpha \) -uniform stabilization and destabilization by means of linear feedbacks \(u=Kx\) . We extend previous results obtained for bidimensional single-input linear control systems to the general case as follows: if there exists at least one \(K\) such that the Lie algebra generated by \(A\) and \(BK\) is equal to the set of all \(d\times d\) matrices, then the maximal rate of convergence of \((A,B)\) is equal to the maximal rate of divergence of \((-A,-B)\) . We also provide more precise results in the general single-input case, where the above result is obtained under the simpler assumption of controllability of the pair \((A,B)\) .     

Isomorphisms and functors of fuzzy sets and cut systems

Any fuzzy set \(X\) in a classical set \(A\) with values in a complete (residuated) lattice \( Q\) can be identified with a system of \(\alpha \) -cuts \(X_{\alpha }\) , \(\alpha \in Q\) . Analogical results were proved for sets with similarity relations with values in \( Q\) (e.g. \( Q\) -sets), which are objects of two special categories \({\mathbf K}={Set}( Q)\) or \({SetR}( Q)\) of \( Q\) -sets, and for fuzzy sets defined as morphisms from an \( Q\) -set into a special \(Q\) -set \(( Q,\leftrightarrow )\) . These fuzzy sets can be defined equivalently as special cut systems \((C_{\alpha })_{\alpha }\) , called f-cuts. This equivalence then represents a natural isomorphism between covariant functor of fuzzy sets \(\mathcal{F}_{\mathbf K}\) and covariant functor of f-cuts \(\mathcal{C}_{\mathbf K}\) . In this paper, we prove that analogical natural isomorphism exists also between contravariant versions of these functors. We are also interested in relationships between sets of fuzzy sets and sets of f-cuts in an \(Q\) -set \((A,\delta )\) in the corresponding categories \({Set}( Q)\) and \({SetR}( Q)\) , which are endowed with binary operations extended either from binary operations in the lattice \(Q\) , or from binary operations defined in a set \(A\) by the generalized Zadeh’s extension principle. We prove that the resulting binary structures are (under some conditions) isomorphic.     

Accelerating 2D orthogonal matching pursuit algorithm on GPU

Two-dimensional orthogonal matching pursuit (2D-OMP) algorithm is an extension of the one-dimensional OMP (1D-OMP), whose complexity and memory usage are lower than the 1D-OMP when they are applied to 2D sparse signal recovery. However, the major shortcoming of the 2D-OMP still resides in long computing time. To overcome this disadvantage, we develop a novel parallel design strategy of the 2D-OMP algorithm on a graphics processing unit (GPU) in this paper. We first analyze the complexity of the 2D-OMP and point out that the bottlenecks lie in matrix inverse and projection. After adopting the strategy of matrix inverse update whose performance is superior to traditional methods to reduce the complexity of original matrix inverse, projection becomes the most time-consuming module. Hence, a parallel matrix–matrix multiplication leveraging tiling algorithm strategy is launched to accelerate projection computation on GPU. Moreover, a fast matrix–vector multiplication, a parallel reduction algorithm, and some other parallel skills are also exploited to boost the performance of the 2D-OMP further on GPU. In the case of the sensing matrix of size 128 \(\times \) 256 (176 \(\times \) 256, resp.) for a 256 \(\times \) 256 scale image, experimental results show that the parallel 2D-OMP achieves 17 \(\times \) to 41 \(\times \) (24 \(\times \) to 62 \(\times \) , resp.) speedup over the original C code compiled with the O \(_2\) optimization option. Higher speedup would be further obtained with larger-size image recovery.     

Quantum entropy-typical subspace and universal data compression

The quantum entropy-typical subspace theory is specified. It is shown that any \(\rho ^{\otimes n}\) with von Neumann \(\hbox {entropy}\le h\) can be preserved approximately by the entropy-typical subspace with \(\hbox {entropy}=h\) . This result implies an universal compression scheme for the case that the von Neumann entropy of the source does not exceed \(h\) .     

Greedy routing in small-world networks with power-law degrees

In this paper we study decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variant of J. Kleinberg’s grid-based small-world model in which (1) the number of long-range edges of each node is not fixed, but is drawn from a power-law probability distribution with exponent parameter \(\alpha \ge 0\) and constant mean, and (2) the long-range edges are considered to be bidirectional for the purposes of routing. This model is motivated by empirical observations indicating that several real networks have degrees that follow a power-law distribution. The measured power-law exponent \(\alpha \) for these networks is often in the range between 2 and 3. For the small-world model we consider, we show that when \(2 < \alpha < 3\) the standard greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the grid, finishes in an expected number of \(O(\log ^{\alpha -1} n\cdot \log \log n)\) steps, for any source–target pair. This is asymptotically smaller than the \(O(\log ^2 n)\) steps needed in Kleinberg’s original model with the same average degree, and approaches \(O(\log n)\) as \(\alpha \) approaches 2. Further, we show that when \(0\le \alpha < 2\) or \(\alpha \ge 3\) the expected number of steps is \(O(\log ^2 n)\) , while for \(\alpha = 2\) it is \(O(\log ^{4/3} n)\) . We complement these results with lower bounds that match the upper bounds within at most a \(\log \log n\) factor.     

Fault tolerance in distributed systems using fused state machines

Replication is a standard technique for fault tolerance in distributed systems modeled as deterministic finite state machines (DFSMs or machines). To correct \(f\) crash or \(\lfloor f/2 \rfloor \) Byzantine faults among \(n\) different machines, replication requires \(nf\) backup machines. We present a solution called fusion that requires just \(f\) backup machines. First, we build a framework for fault tolerance in DFSMs based on the notion of Hamming distances. We introduce the concept of an ( \(f\) , \(m\) )-fusion, which is a set of \(m\) backup machines that can correct \(f\) crash faults or \(\lfloor f/2 \rfloor \) Byzantine faults among a given set of machines. Second, we present an algorithm to generate an ( \(f\) , \(f\) )-fusion for a given set of machines. We ensure that our backups are efficient in terms of the size of their state and event sets. Third, we use locality sensitive hashing for the detection and correction of faults that incurs almost the same overhead as that for replication. We detect Byzantine faults with time complexity \(O(n f)\) on average while we correct crash and Byzantine faults with time complexity \(O(n \rho f)\) with high probability, where \(\rho \) is the average state reduction achieved by fusion. Finally, our evaluation of fusion on the widely used MCNC’91 benchmarks for DFSMs shows that the average state space savings in fusion (over replication) is 38 % (range 0–99 %). To demonstrate the practical use of fusion, we describe its potential application to two areas: sensor networks and the MapReduce framework. In the case of sensor networks a fusion-based solution can lead to significantly fewer sensor-nodes than a replication-based solution. For the MapReduce framework, fusion can reduce the number of map-tasks compared to replication. Hence, fusion results in considerable savings in state space and other resources such as the power needed to run the backups.     

Optimality of partial adiabatic search and its circuit model

In this paper, we first uncover a fact that a partial adiabatic quantum search with \(O(\sqrt{N/M})\) time complexity is in fact optimal, in which \(N\) is the total number of elements in an unstructured database, and \(M\) ( \(M\ge 1\) ) of them are the marked ones(one) \((N\gg M)\) . We then discuss how to implement a partial adiabatic search algorithm on the quantum circuit model. From the implementing procedure on the circuit model, we can find out that the approximating steps needed are always in the same order of the time complexity of the adiabatic algorithm.     

Deterministic generation of singlet states for N-atoms in coupled cavities via quantum Zeno dynamics

We propose an efficient scheme to drive two atoms in two coupled cavities into a two-atom singlet state via quantum Zeno dynamics and virtual excitations by one step. Then, we convert the two-atom singlet state into a three-atom singlet state in three coupled bimodal cavities with the same principle. We also discuss the influence of decoherence induced by cavity decay and atomic spontaneous emission by numerical calculation. This scheme is robust against both the cavity decay and atomic spontaneous emission since there are no excited cavity fields involved during the operation process, and the atoms are only virtually excited. Actually, if multi-level atoms and multi-mode cavities are applicable, we can convert the ( \(n-1\) )-atom ( \(n\ge 3\) ) singlet state into a \(n\) -atom singlet state in coupled cavity arrays with the same principle in theory.     

Some kinds of primitive and non-primitive words

If the length of a primitive word \(p\) is equal to the length of another primitive word \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . This was obtained separately by Tetsuo Moriya in 2008 and Shyr and Yu in 1994. In this paper, we prove that if the length of \(p\) is divisible by the length of \(q\) and the length of \(p\) is less than or equal to \(m\) times the length of \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . Then we show that if \(uv,u\) are non-primitive words and the length of \(u\) is divisible by the length \(v\) or one of the length of \(u\) and \(uv\) is odd for any two nonempty words \(u\) and \(v\) , then \(u\) is a power of \(v\) .     

Łukasiewicz logic and Riesz spaces

We initiate a deep study of Riesz MV-algebras which are MV-algebras endowed with a scalar multiplication with scalars from \([0,1]\) . Extending Mundici’s equivalence between MV-algebras and \(\ell \) -groups, we prove that Riesz MV-algebras are categorically equivalent to unit intervals in Riesz spaces with strong unit. Moreover, the subclass of norm-complete Riesz MV-algebras is equivalent to the class of commutative unital C \(^*\) -algebras. The propositional calculus \({\mathbb R}{\mathcal L}\) that has Riesz MV-algebras as models is a conservative extension of ?ukasiewicz \(\infty \) -valued propositional calculus and is complete with respect to evaluations in the standard model \([0,1]\) . We prove a normal form theorem for this logic, extending McNaughton theorem for ? ukasiewicz logic. We define the notions of quasi-linear combination and quasi-linear span for formulas in \({\mathbb R}{\mathcal L},\) and relate them with the analogue of de Finetti’s coherence criterion for \({\mathbb R}{\mathcal L}\) .     

The Local Discontinuous Galerkin Method for the Fourth-Order Euler–Bernoulli Partial Differential Equation in One Space Dimension. Part II: A Posteriori Error Estimation

In this paper new a posteriori error estimates for the local discontinuous Galerkin (LDG) method for one-dimensional fourth-order Euler–Bernoulli partial differential equation are presented and analyzed. These error estimates are computationally simple and are obtained by solving a local steady problem with no boundary condition on each element. We use the optimal error estimates and the superconvergence results proved in Part I to show that the significant parts of the discretization errors for the LDG solution and its spatial derivatives (up to third order) are proportional to \((k+1)\) -degree Radau polynomials, when polynomials of total degree not exceeding \(k\) are used. These results allow us to prove that the \(k\) -degree LDG solution and its derivatives are \(\mathcal O (h^{k+3/2})\) superconvergent at the roots of \((k+1)\) -degree Radau polynomials. We use these results to construct asymptotically exact a posteriori error estimates. We further apply the results proved in Part I to prove that, for smooth solutions, these a posteriori LDG error estimates for the solution and its spatial derivatives at a fixed time \(t\) converge to the true errors at \(\mathcal O (h^{k+5/4})\) rate. We also prove that the global effectivity indices, for the solution and its derivatives up to third order, in the \(L^2\) -norm converge to unity at \(\mathcal O (h^{1/2})\) rate. Our proofs are valid for arbitrary regular meshes and for \(P^k\) polynomials with \(k\ge 1\) , and for periodic and other classical mixed boundary conditions. Our computational results indicate that the observed numerical convergence rates are higher than the theoretical rates. Finally, we present a local adaptive procedure that makes use of our local a posteriori error estimate.