Search

Abstract: An RNA secondary structure is considered to be planar if its arc graph can be embedded into a plane without edge crossing. In this paper, a graphical criterion of planarity is presented based on graphical composition for RNA secondary structures with pseudoknots in Rivas–Eddy Class. Effective planar testing algorithms are introduced based on our graphical criterion. [Copyright &y& Elsevier]

Abstract: At the conference CiE 2005, the first author introduced a new model for analog computations, namely interval-valued computations. In this model, computations work on the so-called interval-valued bytes, which are special subsets of the interval rather than a finite sequence of bits. The question was posed there, which complexity is needed to solve -complete problems in this paradigm. In this paper, after formalizing the computational model, we answer this question. We show that the validity problem of quantified propositional formulae is decidable by a linear interval-valued computation. As a consequence, all polynomial space problems are decidable by a polynomial interval-valued computation. Furthermore, it is proven that coincides with the class of languages which are decidable by a restricted polynomial interval-valued computation. [Copyright &y& Elsevier]

Abstract: This paper presents an improved model-based reasoning method to test circuit faults. The testing procedure is applicable even when the target system contains multiple faulty modes. Using our method, the observation could be planned appropriately to guarantee correct solutions to be in the restricted candidate space. The existent consistency-checking method and abductive reasoning method are special cases of our method. The relationship between the testing procedure and the corresponding prime implication is analyzed for algorithmic implementation. [Copyright &y& Elsevier]

An Election is a method of selection of individuals to hold the public office in democracy. Ballot is basically a piece of paper that is used to cast vote during election. In ballot paper voting system each voter uses a ballot paper which is not shared and basically it is a paper printed with the name and symbols of the candidates. The Electronic Voting Machine is basically a memory recorder which records the vote casted by the voters. In this paper, main advantages of E-voting systems for country is highlighted. For constructing E-voting systems, every countries need to do great attention to Verification and Validation requirements. In this research, E-voting scheme with face recognition using deep learning technique is proposed. The process of casting vote is accomplished by blockchain technology and blind signature mechanism. The main objective of the proposed scheme is to explore the positive effects of security and safety in online voting system. • The Election is a method of selection of individuals to hold the public office in democracy. • The Electronic Voting Machine is basically a memory recorder which records the vote casted by the voters. • The aim of the research is to E-voting scheme with face recognition using deep learning technique is proposed. • The main objective of the proposed scheme is to explore the positive effects of security and safety in online voting system. [ABSTRACT FROM AUTHOR]

Abstract: Considering the smallest and the greatest factors with respect to the lexicographic order we associate to each infinite word two other infinite words and . In this paper we prove that the inequalities characterize standard Sturmian words (proper ones and periodic ones) and that the condition “for any and lexicographic order satisfying one has ” characterizes standard episturmian words. [Copyright &y& Elsevier]

The generalized connectivity of a graph G , denoted as κ k (G) , is a generalization of the traditional connectivity and is a parameter to measure the capability of connecting multiple vertices in G. The divide-and-swap cube D S C n is a variant of the hypercube with a nice hierarchical structure and plentiful properties. This paper investigates the generalized connectivity on D S C n. We obtain the result κ 4 (D S C n) = d , where d = log 2 ⁡ n ≥ 1 , by the construction showing that there are d internally disjoint trees connecting any four arbitrary vertices of D S C n. As a corollary, one can directly obtain κ 3 (D S C n) = d. • The generalized k -connectivity κ k (G) is the maximum number of internally disjoint trees connecting any k vertices of G. • The divide-and-swap cube D S C n is a variant of the hypercube with a nice hierarchical structure and plentiful properties. • This paper obtains the result κ 4 (D S C n) = d , where d = log 2 ⁡ n ≥ 1. • As a corollary, we also obtain κ 3 (D S C n) = d. [ABSTRACT FROM AUTHOR]

Thorup and Zwick [1] introduced the notion of approximate distance oracles, a data structure that produces for an n -vertex, m -edge weighted undirected graph G = (V , E) , distance estimations in constant query time. They presented a distance oracle of size O (k n 1 + 1 / k) that given a pair of vertices u , v ∈ V at distance d (u , v) produces in O (k) time an estimation that is bounded by (2 k − 1) d (u , v) , i.e., a (2 k − 1) -multiplicative approximation (stretch). Thorup and Zwick [1] presented also a lower bound based on the girth conjecture of Erdős. For sparse unweighted graphs (i.e., m = O ˜ (n)) the lower bound does not apply. Pǎtraşcu and Roditty [2] used the sparsity of the graph and obtained a distance oracle that uses O ˜ (n 5 / 3) space, has O (1) query time and a stretch of 2. Pǎtraşcu et al. [3] presented infinitely many distance oracles with fractional stretch factors that for graphs with m = O ˜ (n) converge exactly to the integral stretch factors and the corresponding space bound of Thorup and Zwick. It is not known, however, whether graph sparsity can help to get a stretch which is better than (2 k − 1) using only O ˜ (k n 1 + 1 / k) space. In this paper we answer this open question and prove a separation between sparse and dense graphs by showing that using sparsity it is possible to obtain better stretch/space tradeoffs than those of Thorup and Zwick. We show that for every k ≥ 2 there is a distance oracle of size O ˜ (k m 1 + 1 / k) that produces in O (k) time an estimation d ⁎ (u , v) that satisfies d (u , v) ≤ d ⁎ (u , v) ≤ (2 k − 1) d (u , v) − 4 , for k > 2 , and d (u , v) ≤ d ⁎ (u , v) ≤ 3 d (u , v) − 2 , for k = 2. Another contribution of this paper is a refined stretch analysis of Thorup and Zwick distance oracles that allows us to obtain a better understanding of this important data structure. We present simple conditions for every w ∈ V that characterize the exact scenarios in which every query that involves w produces an estimation of stretch strictly better than 2 k − 1 , even in the case of dense graphs. We complement this contribution with an experiment on real world graphs. The main finding in the experiment is that different real world graphs are likely to satisfy the required conditions and hence the stretch of Thorup and Zwick distance oracles is much better than its worst case bound in these real world graphs. • Graph sparsity can help to get space-stretch tradeoffs for Distance Oracle which are strictly better than Thorup and Zwick space-stretch tradeoffs for general undirected graphs. • A refined stretch analysis of Thorup and Zwick Distance Oracle that characterizes several cases in which the stretch is strictly better than 2 k − 1. • An experiment on real world graphs shows that the cases characterized in the refined stretch analysis are quite frequent, and thus, in many real world graphs, the actual stretch is much better than the worst case stretch bound. [ABSTRACT FROM AUTHOR]

This paper proposes the first implementation of a self-stabilizing regular register emulated by n servers that is tolerant to both Mobile Byzantine Agents and transient failures in a round-free synchronous model. Differently from existing Mobile Byzantine Tolerant register implementations, this paper considers a weaker model where: (i) the computation of the servers is decoupled from the movements of the Byzantine agents, i.e., movements may happen before, concurrently, or after the generation or the delivery of a message, and (ii) servers are not aware of their failure state i.e., they do not know if and when they have been corrupted by a Mobile Byzantine agent. The proposed protocol tolerates (i) any finite number of transient failures, and (ii) up to f Mobile Byzantine agents. In addition, our implementation uses bounded timestamps from the Z 13 domain and it is optimal with respect to the number of servers needed to tolerate f Mobile Byzantine agents in the given model (i.e., n > 6 f when Δ = 2 δ , and n > 8 f when Δ = δ , where Δ represents the period at which the Byzantine agents move and δ is the upper bound on the communication latency). [ABSTRACT FROM AUTHOR]

By using the PoW protocol, mining pools compete to successfully mine blocks to pursue rewards. Generally, the reward from a mined block includes the fixed block subsidies and the time-varying transaction fees. The latter are offered by the senders whose transactions are packaged into blocks and are increasing with the block size being larger. However, the larger block size brings the longer latency, resulting in a smaller probability of successfully mining. Therefore, decision on the optimal block size of a block to trade off two factors above mentioned is a complex and crucial problem for the mining pools. In this paper, we model the repeated mining competition dynamics among mining pools as an evolutionary game, in which each mining pool has two strategies: following the upper bound of block size B ¯ , or selecting a block size smaller than B ¯. Because of the bounded rationality, each mining pool pursues its evolutionary stable strategy (ESS) on block size by continuous learning and adjustments during the whole mining process. A framework is built for the general evolutionary game, based on which we then explore the existence and stability of the ESSs for a case of two mining pools. Numerical experiments using the real Bitcoin data are conducted to demonstrate the theoretical results in this paper. • A framework is built for the general evolutionary game. • Based on the analysis framework, we then explore the existence and stability of the ESSs for a case of two mining pools. • Numerical experiments using the real-world Bitcoin data are conducted to demonstrate the theoretical results in this paper. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]

This paper enriches a pre-existing decision algorithm, which in turn augmented a fragment of Tarski's elementary algebra with one-argument real functions endowed with a continuous first derivative. In its present (still quantifier-free) version, our decidable language embodies the addition of functions and multiplication of functions by scalars; the issue we address is the one of satisfiability. As regards real numbers, individual variables and constructs designating the basic arithmetic operations are available, along with comparison relators. As regards functions, we have variables of another sort, out of which compound terms are formed by means of constructs designating addition and differentiation. An array of predicates designates various relationships between functions, as well as function properties, that may hold over intervals of the real line; those are: function comparisons, strict and non-strict monotonicity / convexity / concavity, comparisons between the derivative of a function and a real-valued term. Our decision method consists in preprocessing the given formula into an equi-satisfiable quantifier-free formula of the elementary algebra of real numbers, whose satisfiability can then be checked by means of Tarski's decision method. No direct reference to functions will appear in the target formula, each function variable having been superseded by a collection of stub real variables; hence, in order to prove that the proposed translation is satisfiability-preserving, we must figure out a flexible-enough family of interpolating C 1 functions that can accommodate a model for the source formula whenever the target formula turns out to be satisfiable. With respect to the results announced in earlier papers of the same stream, a significant effort went into designing the family of interpolating functions so that it could meet the new constraints stemming from the presence of function addition (along with differentiation) among the constructs of our fragment of mathematical analysis. • A formal language RDF* concerned with differentiable real functions is proposed. • The class of differentiable functions treated is closed under addition. • The expressive power of RDF* is illustrated through a gallery of examples. • A satisfiability-preserving algorithm reducing RDF* formulas into an existential sentence of Tarskian algebra is presented. • The correctness of the reduction algorithm is reported. [ABSTRACT FROM AUTHOR]

A mixed dominating set of a graph G = (V , E) is a mixed set D of vertices and edges, such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is NP -hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight w v and all edges are assigned the same nonnegative weight w e , and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: 1. for w e ≥ w v , a 2-approximation algorithm; 2. for w e ≥ 2 w v , inapproximability within ratio 1.3606 unless P = N P and within ratio 2 under UGC; 3. for 2 w v > w e ≥ w v , inapproximability within ratio 1.1803 unless P = N P and within ratio 1.5 under UGC; 4. for w e < w v , inapproximability within ratio (1 − ϵ) ln ⁡ | V | unless P = N P for any ϵ > 0. [ABSTRACT FROM AUTHOR]

The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer Δ ≥ 2 , the Shearer threshold is the value λ ⁎ (Δ) = (Δ − 1) Δ − 1 / Δ Δ. It is known that for λ < − λ ⁎ (Δ) , there are graphs G with maximum degree Δ whose independent set polynomial, evaluated at λ , is at most 0. Also, there are no such graphs for any λ > − λ ⁎ (Δ). This paper is motivated by the computational problem of approximating the independent set polynomial when λ < − λ ⁎ (Δ). The key issue in complexity bounds for this problem is "implementation". Informally, an implementation of a real number λ ′ is a graph whose hard-core partition function, evaluated at λ , simulates a vertex-weight of λ ′ in the sense that λ ′ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ < − λ ⁎ (Δ) , it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ > λ ⁎ (Δ). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most Δ at any value λ < − λ ⁎ (Δ). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness). [ABSTRACT FROM AUTHOR]