您现在的位置:首页>外文期刊>Information and computation

期刊信息

  • 期刊名称:

    Information and computation

  • 中文名称: 信息与计算
  • 刊频: 1.225
  • ISSN: 0890-5401
  • 出版社: -
  • 简介:
  • 排序:
  • 显示:
  • 每页:
全选(0
<1/20>
1368条结果
  • 机译 由排除的拓扑未成年人定义的二元约束满足问题
    摘要:The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A binary CSP instance can be presented as a labelled graph encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of this graph. One type of restriction is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture classes defined by language restrictions, or the well-known structural property of acyclicity.We extend the notion of pattern and introduce the notion of a topological minor of a binary CSP instance. By forbidding a finite set of patterns from occurring as topological minors we obtain a compact mechanism for expressing novel tractable subproblems of the CSP, including new generalisations of the class of acyclic instances. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 关于逐块对称Matchgate签名和更高域的#CSP
    摘要:For any n >= 3 and q >= 3, we prove that the EQUALITY function (=(n)) on n variables over a domain of size q cannot be realized by matchgates under holographic transformations. This is a consequence of our theorem on the structure of blockwise symmetric matchgate signatures. This has the implication that the standard holographic algorithms based on matchgates, a methodology known to be universal for #CSP over the Boolean domain, cannot produce P-time algorithms for planar #CSP over any higher domain q >= 3. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 蜂鸣算法中的设计模式:示例,仿真和分析
    摘要:We consider networks of entities which interact using beeps. In the basic model by Cornejo and Kuhn (2010), entities either beep or listen in each round. Those who beep cannot detect simultaneous beeps. Those who listen distinguish only between silence and nonsilence. We call this model BL (beep or listen). Stronger models enable collision detection when beeping (BcdL), listening (BLcd), or both (BcdLcd).We identify a set of generic design patterns in beeping algorithms: multi-slot phases; exclusive beeps; adaptive probability; internal or peripheral collision detection (and their emulation). Using them, we formulate concisely a number of algorithms for basic tasks like colouring, degree computation, and MIS. We analyse their complexities, improving known bounds of the MIS algorithm by Jeavons et al. (2016). Finally, inspired by Afek et al. (2013), we show that all Las Vegas algorithms using collision detection are convertible into Monte Carlo algorithms with emulated detection, with a logarithmic slowdown. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 自动机网格
    摘要:We contribute new relations to the taxonomy of different conversions from regular expressions to equivalent finite automata. In particular, we are interested in transformations that construct automata such as, the follow automaton, the partial derivative automaton, the prefix automaton, the automata based on pointed expressions recently introduced and studied, and last but not least the position, or Glushkov automaton (A(POS)), and their double reversed construction counterparts. We deepen the understanding of these constructions and show that with the artefacts used to construct the Glushkov automaton one is able to capture most of them. As a byproduct we define a dual version A((POS) over left arrow) of the position automaton which plays a similar role as A(POS) but now for the reverse expression. Moreover, it turns out that the prefix automaton A(Pre) is central to reverse expressions, because the determinisation of the double reversal of A(Pre) (first reverse the expression, construct the automaton A(Pre), and then reverse the automaton) can be represented as a quotient of any of the considered deterministic automata that we consider in this investigation. This shows that although the conversion of regular expressions and reversal of regular expressions to finite automata seems quite similar, there are significant differences. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 BFS树构造的第一个全多项式稳定算法
    摘要:The construction of a spanning tree is a fundamental task in distributed systems which allows to resolve other tasks (i.e., routing, mutual exclusion, network reset). In this paper, we are interested in the problem of constructing a Breadth First Search (BFS) tree. Stabilization is a versatile technique which ensures that the system recovers a correct behavior from an arbitrary global state resulting from transient faults.A filly polynomial algorithm has a round complexity in O(d(a)) and a step complexity in O(n(b)) where d and n are the diameter and the number of nodes of the network and a and b are constants. We present the first fully polynomial stabilizing algorithm constructing a BFS tree under a distributed daemon. Moreover, as far as we know, it is also the first fully polynomial stabilizing algorithm for spanning tree construction. Its round complexity is in Theta(d(2)) and its step complexity is in O(n(6)). (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 关于子序列和前缀的塔的高度
    摘要:A tower is a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word. We study upper and lower bounds on the number of words in maximal finite towers between two regular languages with respect to the size of the NFA (respectively the DFA) representation. We show that the upper bound is polynomial in the number of states and exponential in the size of the alphabet, and that it is asymptotically tight if the size of the alphabet is fixed. If the alphabet may grow with the number of states of the automata, the lower bound on the height of towers is exponential with respect to that number. In this case the asymptotically optimal bound remains an open problem. Since, in many cases, the constructed towers are sequences of prefixes, we also study towers of prefixes. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 Lempel-Ziv压缩结构用于文档检索
    摘要:Document retrieval structures index a collection of string documents, to retrieve those that are relevant to query strings p: document listing retrieves all documents where p appears; top k retrieval retrieves the k most relevant of those. Classical structures use too much space in practice. Most current research uses compressed suffix arrays, but fast indices still use 17-21 bpc (bits per character), whereas small ones take milliseconds per returned answer. We present the first document retrieval structures based on Lempel-Ziv compression, precisely LZ78. Our structures use 7-10 bpc and dominate a large part of the space/time tradeoffs. They also enable more efficient partial or approximate answers: our document listing outputs the first 75%-80% of the answers at a rate of one per microsecond; for top-k retrieval we return a result of 90% quality at the same rate and using just 4-6 bpc. This outperforms current indices by a wide margin. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 常规DAG语言的语言理论特性
    摘要:We study sets of directed acyclic graphs, called regular DAG languages, which are accepted by a recently introduced type of DAG automata motivated by current developments in natural language processing. We prove (or disprove) closure properties, establish pumping lemmata, characterize finite regular DAG languages, and show that \"unfolding\" turns regular DAG languages into regular tree languages, which implies a linear growth property and the regularity of the path languages of regular DAG languages. Further, we give polynomial decision algorithms for the emptiness and finiteness problems, and show that deterministic DAG automata can be minimized and tested for equivalence in polynomial time. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 商店语言和应用程序
    摘要:The store language of a machine of some arbitrary type is the set of all store configurations (state plus store contents but not input) that can appear in an accepting computation. New algorithms and characterizations of store languages are obtained, such as the result that any nondeterministic pushdown automaton augmented with reversal-bounded counters, where the pushdown can \"flip\" its contents a bounded number of times, can be accepted by a machine with only reversal-bounded counters. Connections are made between store languages and several model checking and reachability problems, such as accepting the set of all predecessor and successor configurations of a machine from a given (regular) set of configurations. For a variety of different machine models often containing multiple parallel data stores, these sets can be accepted with a machine model that is simpler than the original model itself. Store languages are key to showing these properties. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 “迭代堆栈自动机和复杂性类”的更正[Inf。计算95(1)(1991)21-75]
    摘要:The notion of alternation is adjusted to its intended meaning. (C) 2019 Published by Elsevier Inc.
  • 机译 反应系统动力学的复杂性
    摘要:Reaction systems are discrete dynamical systems inspired by bio-chemical processes, whose dynamical behaviour is expressed by set-theoretic operations on finite sets. Reaction systems thus provide a description of bio-chemical phenomena that complements the more traditional approaches, for instance those based on differential equations. A comprehensive list of decision problems about the dynamical behaviour of reaction systems (such as cycles and fixed/periodic points, attractors, and reachability) is provided along with the corresponding computational complexity, which ranges from tractable problems to PSPACE-complete problems. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 参数化AC〜0的一些下界
    摘要:We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical AC(0). Among others, we derive such a lower bound for all fpt-approximations of the parameterized clique problem and for a parameterized halting problem, which recently turned out to link problems of computational complexity, descriptive complexity, and proof theory. To show the lower bound mentioned first we prove a strong AC(0) version of the planted clique conjecture: AC(0)-circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size <= n(xi) (where 0 <= xi < 1). (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 分离逻辑验证指针程序的完整性和表达性
    摘要:Reynolds' separation logical system for pointer program verification is investigated. This paper proves its completeness theorem that states that every true asserted program is provable in the logical system. In order to prove the completeness, this paper shows the expressiveness theorem that states the weakest precondition of every program and every assertion can be expressed by some assertion. This paper also introduces an extension of the assertion language with inductive definitions and proves the soundness theorem, the expressiveness theorem, and the completeness theorem. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 通信网络色散和熵测度的最大流最小割定理
    摘要:The paper presents four distinct new ideas and results for communication networks:1) We show that relay-networks (i.e. communication networks where different nodes use the same coding functions) can be used to model dynamic networks, in a way, akin to Kripke's possible worlds. Changes in the network are modelled by considering a multiverse where different possible situations arise as worlds existing in parallel.2) We introduce the term model, which is a simple, graph-free symbolic approach to communication networks. This model yields an algorithm to calculate the capacity of a given communication network.3) We state and prove variants of a theorem concerning the dispersion of information in single-receiver communications. The dispersion theorem resembles the max-flow min-cut theorem for commodity networks. The proof uses a very weak kind of network coding, called routing with dynamic headers.4) We show that the solvability of an abstract multi-user communication problem is equivalent to the solvability of a single-target communication in a suitable relay network. In the paper, we develop a number of technical ramifications of these ideas and results. We prove a max-flow min-cut theorem for the Renyi entropy with order less than one, given that the sources are equiprobably distributed; conversely, we show that the max-flow min-cut theorem fails for order greater than one. We also show that linear network coding fails for relay networks, although routing with dynamic headers is asymptotically sufficient to reach capacity. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 具有完美信息和较少随机位置的均值支付随机博弈的伪多项式算法
    摘要:We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G = (V, E), with local rewards r : E -> Z, and three types of positions: black V-B, white V-W, and random V-R forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when vertical bar V-R vertical bar = 0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper,(1) we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with vertical bar V-R vertical bar = 0 (1), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in vertical bar V-W vertical bar + vertical bar V-B vertical bar, the maximum absolute local reward, and the common denominator of the transition probabilities. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 上三角自由单调态的自由对的刻画
    • 作者:Honkala, Juha;
    • 刊名:Information and computation
    • 2019年第AUG.期
    摘要:We study combinatorics on morphisms. More precisely, we study free monoid morphisms and their freeness properties. By definition, a set F of endomorphisms of a free monoid is free, if every product formed of morphims from F can be uniquely factorized. We show that if f and g are endomorphisms of the free monoid A* having upper triangular incidence matrices with diagonal entries at least two, then the pair {f, g} is free if and only if f and g do not commute. This result implies that for such pairs freeness is very easy to decide. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 更快的FPTAS用于计数和随机生成背包解决方案
    摘要:In the #P-complete problem of counting 0/1 Knapsack solutions, the input consists of a sequence of n nonnegative integer weights w(1), ..., w(n) and an integer C, and we have to find the number of subsequences (subsets of indices) with total weight at most C. We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for this problem, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes from Gopalan et al. (2011) [9], Stefankovic et al. (2012) [6] and the randomized counting and random generation algorithms in Dyer (2003) [5].Our method is general, and it can be directly applied on top of combinatorial decompositions (such as dynamic programming solutions) of various problems. For example, we also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG. (C) 2019 The Authors. Published by Elsevier Inc.
  • 机译 概率模态逻辑的表达性:一种渐进的方法
    摘要:Logical characterizations of probabilistic bisimulation and simulation for Labelled Markov Processes were given by Desharnais et al. These results hold for systems defined on analytic state spaces and assume countably many labels in the case of bisimulation and finitely many labels in the case of simulation.We revisit these results by giving simpler and more streamlined proofs. In particular, our proof for simulation has the same structure as the one for bisimulation, relying on a new result of a topological nature. We also propose a new notion of event simulation.Our proofs assume countably many labels, and we show that the logical characterization of bisimulation may fail when there are uncountably many labels. However, with a stronger assumption on the transition functions (continuity instead of just measurability), we regain the logical characterization result for arbitrarily many labels. These results arose from a game-theoretic understanding of probabilistic simulation and bisimulation. (C) 2019 Elsevier Inc. All rights reserved.
  • 机译 合并和布尔语法最难的语言
    摘要:A famous theorem by Greibach (\"The hardest context-free language\", SIAM J. Comp., 1973) states that there exists such a context-free language L-0, that every context-free language over any alphabet is reducible to L-0 by a homomorphic reduction-in other words, is representable as its inverse homomorphic image h(-1)(L-0), for a suitable homomorphism h. This paper establishes similar characterizations for conjunctive grammars, that is, for grammars extended with a conjunction operator, as well as for Boolean grammars, which are further equipped with a negation operator. At the same time, it is shown that no such characterization is possible for several subclasses of linear grammars. (C) 2018 Elsevier Inc. All rights reserved.
  • 机译 在线加权模式匹配
    摘要:A weighted sequence is a sequence of probability distributions over an alphabet of sizes sigma. Weighted sequences arise naturally in many applications. We study the problem of weighted pattern matching in which we are given a string pattern P of length m, a weight threshold 1/z, and a weighted text Xarriving on-line. We say that Poccurs in X at position i if the product of probabilities of the letters of P at positions i-m + 1, . . . , i in X is at least 1/z. We first discuss how to apply a known general scheme that transforms off-line pattern matching algorithms to on-line algorithms to obtain an on-line algorithm that requires O((sigma+ logz) logm) or O(sigma log(2) m) time per arriving position; with the space requirement however being O(m min(sigma, z)). Our main result is a new algorithm that processes each arriving position of X in O(z+ sigma) time using O(m + z) extra space. (C) 2019 Elsevier Inc. All rights reserved.
  • 联系方式:010-58892860转803 (工作时间) 18141920177 (微信同号)
  • 客服邮箱:kefu@zhangqiaokeyan.com
  • 京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-1 六维联合信息科技(北京)有限公司©版权所有
  • 客服微信
  • 服务号