Mutually unbiased maximally entangled bases in $$\mathbb {C}^d\otimes \mathbb {C}^d$$

We study mutually unbiased maximally entangled bases (MUMEB’s) in bipartite system \(\mathbb {C}^d\otimes \mathbb {C}^d (d \ge 3)\). We generalize the method to construct MUMEB’s given in Tao et al. (Quantum Inf Process 14:2291–2300, 2015), by using any commutative ring R with d elements and generic character of \((R,+)\) instead of \(\mathbb {Z}_d=\mathbb {Z}/d\mathbb {Z}\). Particularly, if \(d=p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s}\) where \(p_1, \ldots , p_s\) are distinct primes and \(3\le p_1^{a_1}\le \cdots \le p_s^{a_s}\), we present \(p_1^{a_1}-1\) MUMEB’s in \(\mathbb {C}^d\otimes \mathbb {C}^d\) by taking \(R=\mathbb {F}_{p_1^{a_1}}\oplus \cdots \oplus \mathbb {F}_{p_s^{a_s}}\), direct sum of finite fields (Theorem 3.3).     

Tuples of Disjoint $\mathsf{NP}$ -Sets

Disjoint -pairs are a well studied complexity-theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint -pairs to disjoint k-tuples of -sets for k≥2. We define subclasses of the class of all disjoint k-tuples of -sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from the proof system. In our main result we show that complete disjoint -pairs exist if and only if complete disjoint k-tuples of -sets exist for all k≥2. Further, this is equivalent to the existence of a propositional proof system in which the disjointness of all k-tuples is shortly provable. We also show that a strengthening of this conditions characterizes the existence of optimal proof systems. An extended abstract of this paper appeared in the proceedings of the conference CSR 2006 (Lecture Notes in Computer Science 3967, 80–91, 2006). Supported by DFG grant KO 1053/5-1.     

Parameterized Complexity of Satisfying Almost All Linear Equations over \mathbb{F}_{2}

The problem MaxLin2 can be stated as follows. We are given a system S of m equations in variables x ₁,…,x _n , where each equation $\sum_{i \in I_{j}}x_{i} = b_{j}$ is assigned a positive integral weight w _j and $b_{j} \in\mathbb{F}_{2}$ , I _j ?{1,2,…,n} for j=1,…,m. We are required to find an assignment of values in $\mathbb{F}_{2}$ to the variables in order to maximize the total weight of the satisfied equations. Let W be the total weight of all equations in S. We consider the following parameterized version of MaxLin2: decide whether there is an assignment satisfying equations of total weight at least W?k, where k is a nonnegative parameter. We prove that this parameterized problem is W[1]-hard even if each equation of S has exactly three variables and every variable appears in exactly three equations and, moreover, each weight w _j equals 1 and no two equations have the same left-hand side. We show the tightness of this result by proving that if each equation has at most two variables then the parameterized problem is fixed-parameter tractable. We also prove that if no variable appears in more than two equations then we can maximize the total weight of satisfied equations in polynomial time.     

Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.     

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}\) .     

About the Decidability of Polyhedral Separability in the Lattice $$\mathbb {Z}^d$$

The recognition of primitives in digital geometry is deeply linked with separability problems. This framework leads us to consider the following problem of pattern recognition : given a finite lattice set \(S\subset \mathbb {Z}^d\) and a positive integer n, is it possible to separate S from \(\mathbb {Z}^d \setminus S\) by n half-spaces? In other words, does there exist a polyhedron P defined by at most n half-spaces satisfying \(P\cap \mathbb {Z}^d = S\)? The difficulty comes from the infinite number of constraints generated by all the points of \(\mathbb {Z}^d\setminus S\). It makes the decidability of the problem non-straightforward since the classical algorithms of polyhedral separability can not be applied in this framework. We conjecture that the problem is nevertheless decidable and prove it under some assumptions: in arbitrary dimension, if the interior of the convex hull of S contains at least one lattice point or if the dimension d is 2 or if the dimension \(d=3\) and S is not in a specific configuration of lattice width 0 or 1. The proof strategy is to reduce the set of outliers \(\mathbb {Z}^d\setminus S\) to its minimal elements according to a partial order “is in the shadow of.” These minimal elements are called the lattice jewels of S. We prove that under some assumptions, the set S admits only a finite number of lattice jewels. The result about the decidability of the problem is a corollary of this fundamental property.     

Quaternary Codes and Biphase Sequences from $$\mathbb{Z}_8 $$ -Codes

Composing the Carlet map with the inverse Gray map, a new family of cyclic quaternary codes is constructed from 5-cyclic -codes. This new family of codes is inspired by the quaternary Shanbag–Kumar–Helleseth family, a recent improvement on the Delsarte–Goethals family. We conjecture that these -codes are not linear. As applications, we construct families of low-correlation quadriphase and biphase sequences.     

Mutually unbiased special entangled bases with Schmidt number 2 in $${\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}$$

A way of constructing special entangled basis with fixed Schmidt number 2 (SEB2) in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k\in z^+,3\not \mid k)\) is proposed, and the conditions mutually unbiased SEB2s (MUSEB2s) satisfy are discussed. In addition, a very easy way of constructing MUSEB2s in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k=2^l)\) is presented. We first establish the concrete construction of SEB2 and MUSEB2s in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4}\) and \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{8}\), respectively, and then generalize them into \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k\in z^+,3\not \mid k)\) and display the condition that MUSEB2s satisfy; we also give general form of two MUSEB2s as examples in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k=2^l)\).     

Efficient controller synthesis for a fragment of \hbox {MTL}_{0, \infty }

In this paper we offer an efficient controller synthesis algorithm for assume-guarantee specifications of the form $\varphi _1 \wedge \varphi _2 \wedge \cdots \wedge \varphi _n \rightarrow \psi _1 \wedge \psi _2 \wedge \cdots \wedge \psi _m$ . Here, $\{\varphi _i,\psi _j\}$ are all safety-MTL $_{0, \infty }$ properties, where the sub-formulas $\{\varphi _i\}$ are supposed to specify assumptions of the environment and the sub-formulas $\{\psi _j\}$ are specifying requirements to be guaranteed by the controller. Our synthesis method exploits the engine of Uppaal-Tiga and the novel translation of safety- and co-safety-MTL $_{0, \infty }$ properties into under-approximating, deterministic timed automata. Our approach avoids determinization of Büchi automata, which is the main obstacle for the practical applicability of controller synthesis for linear-time specifications. The experiments demonstrate that the chosen specification formalism is expressive enough to specify complex behaviors. The proposed approach is sound but not complete. However, it successfully produced solutions for all the experiments. Additionally we compared our tool with Acacia+ and Unbeast, state-of-the-art LTL synthesis tools; and our tool demonstrated better timing results, when we applied both tools to the analogous specifications.     

Interval-Valued and Intuitionistic Fuzzy Mathematical Morphologies as Special Cases of \mathbb{L}-Fuzzy Mathematical Morphology

Mathematical morphology (MM) offers a wide range of tools for image processing and computer vision. MM was originally conceived for the processing of binary images and later extended to gray-scale morphology. Extensions of classical binary morphology to gray-scale morphology include approaches based on fuzzy set theory that give rise to fuzzy mathematical morphology (FMM). From a mathematical point of view, FMM relies on the fact that the class of all fuzzy sets over a certain universe forms a complete lattice. Recall that complete lattices provide for the most general framework in which MM can be conducted.     

Phase field computations for surface diffusion and void electromigration in {mathbb{R}^3}

We consider a finite element approximation of a phase field model for the evolution of voids by surface diffusion in an electrically conducting solid. The phase field equations are given by a degenerate Cahn–Hilliard equation with an external forcing induced by the electric field. We describe the iterative scheme used to solve the resulting nonlinear discrete equations and present some numerical experiments in three space dimensions. The first author was supported by the EPSRC grant EP/C548973/1.     

On-line graph coloring of {\mathbb{P}_5}-free graphs

Kierstead et al. (SIAM J Discret Math 8:485–498, 1995) have shown 1 that the competitive function of on-line coloring for -free graphs (i.e., graphs without induced path on 5 vertices) is bounded from above by the exponential function . No nontrivial lower bound was known. In this paper we show the quadratic lower bound . More precisely, we prove that is the exact competitive function for ()-free graphs. In this paper we also prove that 2 - 1 is the competitive function of the best clique covering on-line algorithm for ()-free graphs.     

Unextendible maximally entangled bases in $${\mathbb {C}}^{pd}\otimes {\mathbb {C}}^{qd}$$

The construction of unextendible maximally entangled bases is tightly related to quantum information processing like local state discrimination. We put forward two constructions of UMEBs in \({\mathbb {C}}^{pd}\otimes {\mathbb {C}}^{qd}\)(\(p\le q\)) based on the constructions of UMEBs in \({\mathbb {C}}^{d}\otimes {\mathbb {C}}^{d}\) and in \({\mathbb {C}}^{p}\otimes {\mathbb {C}}^{q}\), which generalizes the results in Guo (Phys Rev A 94:052302, 2016) by two approaches. Two different 48-member UMEBs in \({\mathbb {C}}^{6}\otimes {\mathbb {C}}^{9}\) have been constructed in detail.     

Chain conditions on \textit{BL}-algebras

The aim of this paper is to solve the open problem appeared in Motamed and Moghaderi (Soft Comput 2012), about the relation between Noetherian (Artinian) $\textit{BL}$ -algebras in short exact sequences. Also, a better theorem to improve its results is suggested. The relation between Noetherian and Artinian $\textit{BL}$ -algebras is found, the concept of length for a filter in $\textit{BL}$ -algebras is introduced and properties of finite length $\textit{BL}$ -algebras are developed. Finally, it is proved that any $\textit{BL}$ -algebra has finite length if and only if be Noetherian and Artinian.     

$$\mathbf {L^\infty }$$-error estimates for the obstacle problem revisited

In this paper, we present an alternative approach to a priori \(L^\infty \)-error estimates for the piecewise linear finite element approximation of the classical obstacle problem. Our approach is based on stability results for discretized obstacle problems and on error estimates for the finite element approximation of functions under pointwise inequality constraints. As an outcome, we obtain the same order of convergence proven in several works before. In contrast to prior results, our estimates can, for example, also be used to study the situation where the function space is discretized but the obstacle is not modified at all.     

\frac{13}{9}-Approximation for Graphic TSP

The Travelling Salesman Problem is one of the fundamental and intensively studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides’s algorithm with an approximation factor of \(\frac{3}{2}\) , even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only \(\frac{4}{3}\) . Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis Gharan et al. (FOCS, 550–559, 2011), and then by Mömke and Svensson (FOCS, 560–569, 2011). In this paper, we provide an improved analysis of the approach presented in Mömke and Svensson (FOCS, 560–569, 2011) yielding a bound of \(\frac{13}{9}\) on the approximation factor, as well as a bound of \(\frac{19}{12}+\varepsilon\) for any ε>0 for a more general Travelling Salesman Path Problem in graphic metrics.     

Multivariate numerical approximation using constructive L^{2} (\mathbb{R}) RBF neural network

For the multivariate continuous function, using constructive feedforward L² (\mathbbR) L^{2} (\mathbb{R}) radial basis function (RBF) neural network, we prove that a L² (\mathbbR) L^{2} (\mathbb{R}) RBF neural network with n + 1 hidden neurons can interpolate n + 1 multivariate samples with zero error. Then, we prove that the L² (\mathbbR) L^{2} (\mathbb{R}) RBF neural network can uniformly approximate any continuous multivariate function with arbitrary precision. The correctness and effectiveness are verified through eight numeric experiments.     

The Updatable \overline{X} & S Control Charts

The tools for Statistical Process Control (SPC) should be continuously improved in order to continuously improve the product quality. This article proposes a scenario for continuously improving the & S control charts during the use of the charts. It makes use of the information collected from the out-of-control cases in a manufacturing process to update the charting parameters (i.e. the sample size, sampling interval and control limits) step-by-step. Consequently, the resultant control charts (called the updatable charts) become more and more effective to detect the mean shift δ_μ and standard deviation shift δ_σ for the particular process. The updatable charts are able to considerably reduce the average value of the loss function due to the occurrences of the out-of-control cases. Noteworthily, unlike the designs of the economic control charts, the designs of the updatable charts only require limited number of specifications that can be easily decided.