On The Space Complexity Of Turn Bounded Pushdown Automata

A pushdown automaton is said to make a turn at a given instant if it changes at that instant from stack increasing to stack decreasing. Let \hbox{NPDA-TURN}(\,f(n)) and \hbox{DPDA-TURN}(\,f(n)) denote the classes of languages accepted by nondeterministic and deterministic pushdown automata respectively that make at most f v ( n ) turns for any input of length n . In this paper the following inclusions that express the space complexity of turn bounded pushdown automata are given: \hbox{DPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log f(n)\log n) , and \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf NSPACE} (\log f(n)\log n) . In particular, it follows that finite-turn pushdown automata are logarithmic space bounded: \hbox{DPDA-TURN}(O(1))\subseteq {\bf DL} and \hbox{NPDA-TURN}(O(1))\subseteq {\bf NL} , from which two corollaries follow: one is that the class of metalinear context-free languages is complete for NL , and the other is that a more tight inclusion \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log n) cannot be derived unless {\bf DL}={\bf NL} , though \hbox{NPDA-TURN} (\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log^2n) holds.     

Fuzzy sets and cut systems in a category of sets with similarity relations

Let \Upomega\Upomega be a complete residuated lattice. Let SetR(\Upomega){\mathbf{SetR}}(\Upomega) be the category of sets with similarity relations with values in \Upomega\Upomega (called \Upomega\Upomega-sets), which is an analogy of the category of classical sets with relations as morphisms. A fuzzy set in an \Upomega\Upomega-set in the category SetR(\Upomega){\mathbf{SetR}}(\Upomega) is a morphism from \Upomega\Upomega-set to a special \Upomega\Upomega-set (\Upomega,?),(\Upomega,\leftrightarrow), where ?\leftrightarrow is the biresiduation operation in \Upomega.\Upomega. In the paper, we prove that fuzzy sets in \Upomega\Upomega-sets in the category SetR(\Upomega){\mathbf{SetR}}(\Upomega) can be expressed equivalently as special cut systems (C_a)_{a ? \Upomega}.(C_{\alpha})_{\alpha\in\Upomega}.     

Quantitative Separation Logic and Programs with Lists

This paper presents an extension of a decidable fragment of Separation Logic for singly-linked lists, defined by Berdine et al. (2004). Our main extension consists in introducing atomic formulae of the form ls ^k (x, y) describing a list segment of length k, stretching from x to y, where k is a logical variable interpreted over positive natural numbers, that may occur further inside Presburger constraints. We study the decidability of the full first-order logic combining unrestricted quantification of arithmetic and location variables. Although the full logic is found to be undecidable, validity of entailments between formulae with the quantifier prefix in the language $^* {$_\mathbbN, "_\mathbbN}^*\exists^* \{\exists_{\bf \mathbb{N}}, \forall_{\bf \mathbb{N}}\}^* is decidable. We provide here a model theoretic method, based on a parametric notion of shape graphs. We have implemented our decision technique, providing a fully automated framework for the verification of quantitative properties expressed as pre- and post-conditions on programs working on lists and integer counters.     

Hybrid Logic Meets IF Modal Logic

The hybrid logic H(@,ˉ){\mathcal{H}(@,\downarrow)} and the independence friendly modal logic IFML are compared for their expressive powers. We introduce a logic IFML _c having a non-standard syntax and a compositional semantics; in terms of this logic a syntactic fragment of IFML is singled out, denoted IFML _c . (In the Appendix it is shown that the game-theoretic semantics of IFML _c coincides with the compositional semantics of IFML _c .) The hybrid logic H(@,ˉ){\mathcal{H}(@,\downarrow)} is proven to be strictly more expressive than IFML _c . By contrast, H(@,ˉ){\mathcal{H}(@,\downarrow)} and the full IFML are shown to be incomparable for their expressive powers. Building on earlier research (Tulenheimo and Sevenster 2006), a PSPACE-decidable fragment of the undecidable logic H(@,ˉ){\mathcal{H}(@,\downarrow)} is disclosed. This fragment is not translatable into the hybrid logic H(@){\mathcal{H}(@)} and has not been studied previously in connection with hybrid logics. In the Appendix IFML _c is shown to lack the property of ‘quasi-positionality’ but proven to enjoy the weaker property of ‘bounded quasi-positionality’. The latter fact provides from the IFML internal perspective an account of what makes the compositional semantics of IFML _c possible.     

The sudden death of entanglement in constructed Yang–Baxter systems

Some Hamiltonians are constructed from the unitary \checkR_i,i+1(q, j){\check{R}_{i,i+1}(\theta, \varphi)}-matrices, where θ and j{\varphi} are time-independent parameters. We show that the entanglement sudden death (ESD) can happen in these closed Yang–Baxter systems. It is found that the ESD is not only sensitive to the initial condition, but also has a great connection with different Yang–Baxter systems. Especially, we find that the meaningful parameter j{\varphi} has a great influence on ESD.     

Quantum search in a possible three-dimensional complex subspace

Suppose we are given an unsorted database with N items and N is sufficiently large. By using a simpler approximate method, we re-derive the approximate formula cos² Φ, which represents the maximum success probability of Grover’s algorithm corresponding to the case of identical rotation angles f = q{\phi=\theta} for any fixed deflection angle F ? [0,p/2){\Phi \in\left[0,\pi/2\right)}. We further show that for any fixed F ? [0,p/2){\Phi \in\left[0,\pi/2\right)}, the case of identical rotation angles f = q{\phi=\theta} is energetically favorable compared to the case |q- f| >> 0{\left|{\theta - \phi}\right|\gg 0} for enhancing the probability of measuring a unique desired state.     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.     

Entanglement and Yangian in a {V^{\otimes 3}} Yang-Baxter system

In this paper, a 8 × 8 unitary Yang-Baxter matrix \breveR₁₂₃(q₁,q₂,f){\breve{R}_{123}(\theta_{1},\theta_{2},\phi)} acting on the triple tensor product space, which is a solution of the Yang-Baxter Equation for three qubits, is presented. Then quantum entanglement and the Berry phase of the Yang-Baxter system are studied. The Yangian generators, which can be viewed as the shift operators, are investigated in detail. And it is worth mentioning that the Yangian operators we constructed are independent of choice of basis.     

Distributed discovery of large near-cliques

Given an undirected graph and 0 ￡ e ￡ 1{0\le\epsilon\le1}, a set of nodes is called an e{\epsilon}-near clique if all but an e{\epsilon} fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size e{\epsilon}-near clique if there exists an e³{\epsilon^3}-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n ^−Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of size Ω(n/(log log n) ^α ) for some a ? (0,1){\alpha \in (0,1)}. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.     

Entanglement and Berry phase in a 9 × 9 Yang–Baxter system

A M-matrix which satisfies the Hecke algebraic relations is presented. Via the Yang–Baxterization approach, we obtain a unitary solution \breveR(q,j₁,j₂){\breve{R}(\theta,\varphi_{1},\varphi_{2})} of Yang–Baxter equation. It is shown that any pure two-qutrit entangled states can be generated via the universal \breveR{\breve{R}}-matrix assisted by local unitary transformations. A Hamiltonian is constructed from the \breveR{\breve{R}}-matrix, and Berry phase of the Yang–Baxter system is investigated. Specifically, for j₁ = j₂{\varphi_{1}\,{=}\,\varphi_{2}}, the Hamiltonian can be represented based on three sets of SU(2) operators, and three oscillator Hamiltonians can be obtained. Under this framework, the Berry phase can be interpreted.     

Process control using VSI cause selecting control charts

The article considers the variable process control scheme for two dependent process steps with incorrect adjustment. Incorrect adjustment of a process may result in shifts in process mean, process variance, or both, ultimately affecting the quality of products. We construct the variable sampling interval (VSI) Z_{[`(X)]</sub>-Z<sub>SX<sup>2</sup></sub>{Z_{\overline{X}}-Z_{S_X^2}} and Z<sub>[`(e)]}-Z_Se²{Z_{\bar{{e}}}-Z_{S_e^2}} control charts to effectively monitor the quality variable produced by the first process step with incorrect adjustment and the quality variable produced by the second process step with incorrect adjustment, respectively. The performance of the proposed VSI control charts is measured by the adjusted average time to signal derived using a Markov chain approach. An example of the cotton yarn producing system shows the application and performance of the proposed joint VSI Z_{[`(X)]</sub> -Z<sub>SX<sup>2</sup></sub> {Z_{\overline{X}} -Z_{S_X^2 }} and Z<sub>[`(e)]} -Z_Se² {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts in detecting shifts in mean and variance for the two dependent process steps with incorrect adjustment. Furthermore, the performance of the VSI Z_{[`(X)]</sub>-Z<sub>SX<sup>2</sup></sub> {Z_{\overline{X}}-Z_{S_X^2 }} and Z<sub>[`(e)]} -Z_Se² {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts and the fixed sampling interval Z_{[`(X)]</sub> -Z<sub>SX<sup>2</sup></sub> {Z_{\overline{X}} -Z_{S_X^2 }} and Z<sub>[`(e)]} -Z_Se² {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts are compared by numerical analysis results. These demonstrate that the former is much faster in detecting small and median shifts in mean and variance. When quality engineers cannot specify the values of variable sampling intervals, the optimum VSI Z_{[`(X)]</sub>-Z<sub>SX<sup>2</sup></sub> {Z_{\overline{X}}-Z_{S_X^2 }} and Z<sub>[`(e)]} -Z_Se² {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts are also proposed by using the Quasi-Newton optimization technique.     

Parsimonious flooding in dynamic graphs

An edge-Markovian process with birth-rate p and death-rate q generates infinite sequences of graphs (G ₀, G ₁, G ₂,…) with the same node set [n] such that G _t is obtained from G _t-1 as follows: if e ? E(G_t-1){e\notin E(G_{t-1})} then e ? E(G_t){e\in E(G_{t})} with probability p, and if e ? E(G_t-1){e\in E(G_{t-1})} then e ? E(G_t){e\notin E(G_{t})} with probability q. In this paper, we establish tight bounds on the complexity of flooding in edge-Markovian graphs, where flooding is the basic mechanism in which every node becoming aware of an information at step t forwards this information to all its neighbors at all forthcoming steps t′ > t. These bounds complete previous results obtained by Clementi et al. Moreover, we also show that flooding in dynamic graphs can be implemented in a parsimonious manner, so that to save bandwidth, yet preserving efficiency in term of simplicity and completion time. For a positive integer k, we say that the flooding protocol is k-active if each node forwards an information only during the k time steps immediately following the step at which the node receives that information for the first time. We define the reachability threshold for the flooding protocol as the smallest integer k such that, for any source s ? [n]{s\in [n]} , the k-active flooding protocol from s completes (i.e., reaches all nodes), and we establish tight bounds for this parameter. We show that, for a large spectrum of parameters p and q, the reachability threshold is by several orders of magnitude smaller than the flooding time. In particular, we show that it is even constant whenever the ratio p/(p + q) exceeds log n/n. Moreover, we also show that being active for a number of steps equal to the reachability threshold (up to a multiplicative constant) allows the flooding protocol to complete in optimal time, i.e., in asymptotically the same number of steps as when being perpetually active. These results demonstrate that flooding can be implemented in a practical and efficient manner in dynamic graphs. The main ingredient in the proofs of our results is a reduction lemma enabling to overcome the time dependencies in edge-Markovian dynamic graphs.     

Shuffle languages are in P

In this paper we show that shuffle languages are contained in one-way-NSPACE(log n) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression E we construct a shuffle automaton which accepts the language generated by E and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.     

A $${\mathcal{O}(|G|n^6)}$$ time extension of inversion transduction grammars

Range concatenation grammars are viewed as a hierarchy of synchronous grammars. It is shown how inversion transduction grammars (ITGs) and extensions thereof, including synchronous tree-adjoining grammars, are captured by the hierarchy, and the expressivity and linguistic relevance of subclasses of the hierarchy are discussed. A O(|G|n⁶){\mathcal{O}(|G|n^6)} time extension of ITGs is proposed. The extension translates cross-serial dependencies into nested ones and handles complex kinds of discontinuous translation units and so-called inside-out alignments. In fact, our O(|G|n⁶){\mathcal{O}(|G|n^6)} time extension generates all possible alignments. It is shown that this additional expressivity comes at the cost of probabilistic parsing.     

The inheritance of BDE-property in sharply dominating lattice effect algebras and (o)-continuous states

We study remarkable sub-lattice effect algebras of Archimedean atomic lattice effect algebras E, namely their blocks M, centers C(E), compatibility centers B(E) and sets of all sharp elements S(E) of E. We show that in every such effect algebra E, every atomic block M and the set S(E) are bifull sub-lattice effect algebras of E. Consequently, if E is moreover sharply dominating then every atomic block M is again sharply dominating and the basic decompositions of elements (BDE of x) in E and in M coincide. Thus in the compatibility center B(E) of E, nonzero elements are dominated by central elements and their basic decompositions coincide with those in all atomic blocks and in E. Some further details which may be helpful under answers about the existence and properties of states are shown. Namely, we prove the existence of an (o)-continuous state on every sharply dominating Archimedean atomic lattice effect algebra E with B(E)\not = C(E).B(E)\not =C(E). Moreover, for compactly generated Archimedean lattice effect algebras the equivalence of (o)-continuity of states with their complete additivity is proved. Further, we prove “State smearing theorem” for these lattice effect algebras.     

Generalized fuzzy interior ideals of semigroups

The concept of $(\overline{\in},\overline{\in} \vee \overline{q})The concept of ([`( ? )],[`( ? )] ú[`(q)])(\overline{\in},\overline{\in} \vee \overline{q})-fuzzy interior ideals of semigroups is introduced and some related properties are investigated. In particular, we describe the relationships among ordinary fuzzy interior ideals, (∈, ∈ ∨ q)-fuzzy interior ideals and ([`( ? )],[`( ? )] ú[`(q)])(\overline{\in},\overline{\in} \vee \overline{q})-fuzzy interior ideals of semigroups. Finally, we give some characterization of [F] _t by means of (∈, ∈ ∨ q)-fuzzy interior ideals.     

When Does Eddy Viscosity Damp Subfilter Scales Sufficiently?

Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore, in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size smaller than Δ initially. From this we deduce that the eddy viscosity ν _e has to depend on the invariants q = \frac12tr(S²)q = \frac{1}{2}\mathrm{tr}(S^{2}) and r = -\frac13tr(S³)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by n_e = \frac32(D/p)² |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re  _τ =590).     

Spreading of Messages in Random Graphs

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n ^−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ n))−n ^−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.     

Testing Periodicity

We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet and let p,n be integers such that p ￡ \fracn2p\leq \frac{n}{2} . A length-n string over Σ, α=(α ₁,…,α _n ), has the property Period(p) if for every i,j∈{1,…,n}, α _i =α _j whenever i≡j (mod p). For an integer parameter g ￡ \fracn2,g\leq \frac{n}{2}, the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property Period( ￡ \fracn2)\mathit{Period}(\leq \frac{n}{2}) is also called Periodicity.     

Looking for the best constant in a Sobolev inequality: a numerical approach

A numerical method for the computation of the best constant in a Sobolev inequality involving the spaces H ²(Ω) and C⁰([`(W)])C^{0}(\overline{\Omega}) is presented. Green’s functions corresponding to the solution of Poisson problems are used to express the solution. This (kind of) non-smooth eigenvalue problem is then formulated as a constrained optimization problem and solved with two different strategies: an augmented Lagrangian method, together with finite element approximations, and a Green’s functions based approach. Numerical experiments show the ability of the methods in computing this best constant for various two-dimensional domains, and the remarkable convergence properties of the augmented Lagrangian based iterative method.