您现在的位置:首页>外文期刊>Journal of computer and system sciences


  • 期刊名称:

    Journal of computer and system sciences

  • 中文名称: 计算机与系统科学杂志
  • 刊频: 1.304
  • ISSN: 0022-0000
  • 出版社: -
  • 简介:
  • 排序:
  • 显示:
  • 每页:
  • 机译 具有复杂权重的平面布尔#CSP的复杂性
    摘要: We show a computational complexity dichotomy theorem for symmetric complex-weighted Boolean #CSP when the constraint graph of the input must be planar. The problems that are #P-hard over general graphs but tractable over planar graphs are precisely those with a holographic reduction to matchgates. We also obtain a dichotomy theorem for a symmetric arity 4 signature with complex weights in the planar Holant framework, which we use in the proof of our #CSP dichotomy. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 有序根二叉树的LR图和外平面图的近线性区域图
    摘要: We study the width requirements of LR-drawings of n-node ordered rooted binary trees; these are the drawings produced by a family of tree drawing algorithms introduced by Chan, who showed how to construct LR-drawings with width O (n(0.48)). We prove that LR-drawings with minimum width can be constructed in O (n(1.48)) time. Further, we show an infinite family of n-node ordered rooted binary trees requiring Omega(n(0.418)) width in any LR-drawing and we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to 455 nodes. We also show that, if n-node ordered rooted binary trees have LR-drawings with f (n) width, for any function f (n), then n-vertex outerplanar graphs have outerplanar straight-line drawings in O(f (n)) area. Finally, we prove that every n-vertex outerplanar graph has an outerplanar straight-line drawing in O (n . 2 root 2log(2)n root logn) area. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 在成员身份未知和退化拜占庭式故障的异步系统中使用omega达成共识
    摘要: We study consensus in asynchronous systems where membership is unknown, and where up to f degenerative Byzantine failures can happen. In our failure model a faulty process can have a Byzantine behavior (i.e., it deviates from its specification), and, furthermore, every faulty process will degenerate such that eventually it will have permanent physical or transmission failures. We present a simple algorithm that solves Consensus using the Omega failure detector and a new broadcast primitive called RFLOB in an asynchronous system with degenerative Byzantine failures, which is optimal with respect to failures because it works when f < n/3. RFLOB guarantees reliable, FIFO and local order broadcast in systems with Byzantine processes and unknown membership. Finally, we present an algorithm that implements an Omega failure detector with unknown membership and minimum connectivity (i.e., communication reliability, and synchrony properties) in a system with degenerative Byzantine failures. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 在时间图中找到小分隔符的复杂性
    摘要: Temporal graphs have time-stamped edges. Building on previous work, we study the problem of finding a small vertex set (the separator) whose removal destroys all temporal paths between two designated terminal vertices. Herein, we consider two models of temporal paths: those that pass through arbitrarily many edges per time step (non-strict) and those that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-completeness versus polynomial-time solvability) for both problem variants. Moreover, we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. Finally, we introduce the notion of a temporal core (vertices whose incident edges change over time) and prove that the non-strict variant is fixed-parameter tractable when parameterized by the temporal core size, while the strict variant remains NP-complete, even for constant-size temporal cores. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 验证单带图灵机是否在线性时间内运行
    • 作者:Gajser, David;
    • 刊名:Journal of computer and system sciences
    • 2020年第Feb.期
    摘要: We discuss the following family of problems, parameterized by integers C >= 2 and D >= 1: Does a given one-tape q-state Turing machine make at most Cn + D steps on all computations on all inputs of length n, for all n? Assuming a fixed tape and input alphabet, we show that these problems are co-NP-complete and we provide good lower bounds. Specifically, these problems cannot be solved in o (q((C)(-1)()/4)) nondeterministic time by multi-tape Turing machines. We also show that the complements of these problems can be solved in O(q(C+2)) nondeterministic time and cannot be solved in o(q((C-1)/4)) nondeterministic time by multi-tape Turing machines. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 带有滑动时间窗口的时间顶点覆盖
    摘要: Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 关于低维机器人游戏的可判定性和复杂性
    摘要: A robot game, also known as a Z-VAS game, is a two-player vector addition game played on the integer lattice Z(n), where one of the players, Adam, aims to avoid the origin while the other player, Eve, aims to reach the origin. The problem is to decide whether or not Eve has a winning strategy. In this paper we prove undecidability of the two-dimensional robot game closing the gap between undecidable and decidable cases. We also prove that deciding the winner in a robot game with states in dimension one is EXPSPACE-complete and study a subclass of robot games where deciding the winner is in EXPTIME. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 在对抗P与NP时要知道什么
    摘要: We call any consistent and sufficiently powerful formal theory that enables to algorithmically verify whether some text is a proof algorithmically verifiable mathematics (AV-mathematics). We say a decision problem L subset of Sigma* is almost everywhere solvable if for all but finitely many inputs x is an element of Sigma*, one can prove "x is an element of L" or "x is not an element of L" in AV-mathematics. We study what kind of problems related to algorithms and computational complexity are not almost everywhere solvable in AV-mathematics. We observe that this is true for all semantically nontrivial problems about programs and show several results of the kind "There exist programs that are provably algorithms for which it is neither provable that they do not work in polynomial time, nor that they do not solve SATISFIABILITY." Finally, we prove that, if DLOG = NLOG, or BPP = PSPACE, then there exist constructive proofs for it and almost constructive in the case P = NP. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 多部分伪语音图游戏中的上下文
    摘要: Analyzing pseudo-telepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures generating equivalent scenarios. We introduce a new tool called multipartiteness width to investigate which scenarios are hard to decompose and show that there exist graphs generating scenarios with a linear multipartiteness width. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 HV平面性:算法和复杂性
    摘要:An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing, that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17]. On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 对抗性多路访问信道中确定性广播的数据包延迟
    摘要:We study broadcasting in multiple access channels with dynamic packet arrivals and jamming. Communication environments are represented by adversarial models that specify constraints on packet arrivals and jamming. We consider deterministic distributed broadcast algorithms and give upper bounds on the worst-case packet latency and the number of queued packets in relation to the parameters defining adversaries. Packet arrivals are determined by a rate of injections and a number of packets that can be generated in one round. Jamming is constrained by a rate with which an adversary can jam rounds and by a number of consecutive rounds that can be jammed. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 关于First Fit的总和着色的性能保证
    摘要:In sum coloring, it is required to find a proper coloring of the vertices of a graph using positive integers, such that the sum of colors of the vertices is minimized. First Fit is the natural coloring algorithm that processes vertices one by one (in some order), and colors the current vertex with the minimum color that was not used for any of its already considered neighbors. Here, we study the approximation ratio of First Fit for sum coloring for the class of claw-free graphs, its most natural subclasses, and its generalizations, and get tight bounds for it. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 参数化移位组合优化
    摘要:Shifted combinatorial optimization is a new nonlinear optimization framework broadly extending standard combinatorial optimization, involving the choice of several feasible solutions simultaneously. This framework captures well studied and diverse problems, from sharing and partitioning to so-called vulnerability problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, typically harder. Already with explicitly given input set SCO may be NP-hard. Here we initiate a study of the parameterized complexity of this framework. First we show that SCO over an explicitly given set parameterized by its cardinality may be in XP, FPT or P, depending on the objective function. Second, we study SCO over sets definable in MSO logic (which includes, e.g., the well known MSO-partitioning problems). Our main results are that SCO over MSO definable sets is in XP parameterized by the MSO formula and treewidth (or clique-width) of the input graph, and W[1]-hard even under further severe restrictions. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 弹性和弹性防御关键DNS权威基础架构上的DDoS攻击
    • 作者:Wang, Zheng;
    • 刊名:Journal of computer and system sciences
    • 2019年第FEB.期
    摘要:The critical DNS authoritative infrastructure is increasingly targeted by DDoS attacks in recent years. This paper proposes a novel mitigating solution to DDoS attacks on DNS authoritative name servers. The solution uses DNAME record to signal domain redirection directive to recursive resolvers, which then accordingly redirect their subsequent query traffic to the redirection domains. In response to DDoS attacks, multiple domains can be chained to elastically and adaptiyely provision and release authoritative resources to scale rapidly on demand. The simulation results validate the efficacy of the solution. (C) 2017 Elsevier Inc. All rights reserved.
  • 机译 SL(2,Z)中的向量和标量可达性问题
    摘要:This paper solves three open problems about the decidability of the vector and scalar reachability problems and the point to point reachability by fractional linear transformations over finitely generated semigroups of matrices from SL(2, Z). Our approach to solving these problems is based on the characterization of reachability paths between vectors or points, which is then used to translate the numerical problems on matrices into computational problems on words and regular languages. We will also give geometric interpretations of these results. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 实体链接框架的表达能力
    摘要:We develop a unifying approach to declarative entity linking by introducing the notion of an entity-linking framework and an accompanying notion of the certain links in such a framework. In an entity-linking framework, logic-based constraints are used to express properties of the desired link relations in terms of source relations and, possibly, in terms of other link relations. The definition of the certain links in such a framework makes use of weighted repairs and consistent answers in inconsistent databases. We demonstrate the modeling capabilities of this approach by showing that numerous concrete entity linking scenarios can be cast as such entity-linking frameworks for suitable choices of constraints and weights. By using the certain links as a measure of expressive power, we investigate the relative expressive power of several entity-linking frameworks and obtain sharp comparisons. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 同步马尔可夫决策过程的复杂性
    摘要:We consider Markov decision processes (MDP) as generators of sequences of probability distributions over states. A probability distribution is p-synchronizing if the probability mass is at least p in a single state, or in a given set of states. We consider four temporal synchronizing modes: a sequence of probability distributions is always p-synchronizing, eventually p-synchronizing, weakly p-synchronizing, or strongly p-synchronizing if, respectively, all, some, infinitely many, or all but finitely many distributions in the sequence are p-synchronizing. We provide tight results on the expressiveness, decidability, complexity, and memory requirement for winning strategies for all synchronizing modes in MDPs. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 无复制成本记录自动机:结构,表达性和封闭性
    摘要:Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study some structural properties, expressiveness, and closure properties of copyless CRA. We show that copyless CRA are strictly less expressive than weighted automata and are not closed under reverse operation. To find a better class we impose restrictions on copyless CRA, which ends successfully with a new robust computational model that is closed under reverse and other extensions. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 概率自动机的确定性和表达性类别
    摘要:k-Hierarchical probabilistic automata (HPA) are probabilistic automata whose states are partitioned into k+1 levels such that for any state and input symbol, at most one transition goes to a state at the same level, and others go to higher level states. We show that 1-HPA, with acceptance threshold 1/2 (in the finite and infinite word cases) can recognize non regular languages, and the non-emptiness and non-universality problems for 1-HPA with threshold 1/2 are decidable in EXPTIME and are PSPACE-hard. We present a new sufficient condition when 1-HPA recognize regular languages. We show that the emptiness problem is undecidable for 2-HPAs. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 计算β-无环超图的最小横向
    摘要:We prove that one can count in polynomial time the number of minimal transversals of beta-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line of research initiated in M.M. Kante and T. Uno (2017) [18]. (C) 2018 Elsevier Inc. All rights reserved.
  • 联系方式:010-58892860转803 (工作时间) 18141920177 (微信同号)
  • 客服邮箱:kefu@zhangqiaokeyan.com
  • 京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-1 六维联合信息科技(北京)有限公司©版权所有
  • 客服微信
  • 服务号