检索结果-内蒙古大学图书馆

Engineering Grammar-Based Type Checking for Graph Rewriting Languages

IEEE ACCESS 2022年 10卷 114612-114628页

作者： Yamamoto, Naoki Ueda, Kazunori Waseda Univ Dept Comp Sci & Engn Tokyo 1698555 Japan

The ability to handle evolving graph structures is important both for programming languages and modeling languages. Of various languages that adopt graphs as primary data structures, a graph rewriting language LMNtal provides features of both (concurrent) programming languages and modeling languages, and its implementation unifies ordinary program execution and model checking functionalities. Unlike pointer manipulation in imperative languages, LMNtal allows us to manipulate graph structures in such a way that the well-formedness of graphs is guaranteed by the language itself. However, since the shapes of graphs can be complex and diverse compared to algebraic data structures such as lists and trees, it is a non-obvious important task to formulate types of graphs to verify individual programs. With this motivation, this paper discusses LMNtal ShapeType, a type checking framework that applies the basic idea of Structured Gamma to a concrete graph rewriting language. Types are defined by generative grammars written as LMNtal rules, and type checking of LMNtal programs can accordingly be done by exploiting the model checking features of LMNtal itself. We gave a full implementation of type checking exploiting the features of the LMNtal meta-interpreter and confirmed that it works for practical operations on various graph structures, including single-step and multi-step operations on non-algebraic data structures and data structures with numerical shape constraints.

关键词： Programming data structures Grammar Syntactics Computer languages data models Writing data integrity dynamic data structures graph grammars graph rewriting type checking

来源：评论

学校读者我要写书评

暂无评论

Constant Time and Space Updates for the Sigma-Tau Problem 30th

Constant Time and Space Updates for the Sigma-Tau Problem

引用

30th International Symposium on String Processing and Information Retrieval (SPIRE) / 18th Workshop on Compression, Text, and Algorithms (WCTA)

作者： Liptak, Zsuzsanna Masillo, Francesco Navarro, Gonzalo Williams, Aaron Univ Verona Dept Comp Sci Verona Italy Univ Chile CeBiB Santiago Chile Univ Chile Dept Comp Sci Santiago Chile Williams Coll Dept Comp Sci Williamstown MA USA

ISBN: (纸本)9783031439797;9783031439803

Sawada and Williams in [SODA 2018] and [ACM Trans. Alg. 2020] gave algorithms for constructing Hamiltonian paths and cycles in the Sigma-Tau graph, thereby solving a problem of Nijenhuis and Wilf that had been open for over 40 years. The Sigma-Tau graph is the directed graph whose vertex set consists of all permutations of n, and there is a directed edge from pi to pi ' if p pi ' can be obtained from pi either by a cyclic left-shift (sigma) or by exchanging the first two entries (tau). We improve the existing algorithms from O(n) time per permutation to O(1) time per permutation. Moreover, our algorithms require only O(1) extra space. The result is the first combinatorial generation algorithm for n-permutations that is optimal in both time and space, and lists the objects in a Gray code order using only two types of changes. The simple C code (similar to 50 lines) can be found at https://***/fmasillo/sigma-tau.

关键词： permutations sigma-tau problem dynamic data structures combinatorial generation combinatorial Gray codes

来源：评论

学校读者我要写书评

暂无评论

dynamic "Succincter" 64

Dynamic "Succincter"

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Li, Tianxiao Liang, Jingxun Yu, Huacheng Zhou, Renfei Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing Peoples R China Princeton Univ Dept Comp Sci Princeton NJ USA

ISBN: (纸本)9798350318944

Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work "succincter" by Patrascu [1] showed that any aB-tree can be stored using only two bits of redundancy, while supporting queries to the tree in time proportional to its depth. It has been a versatile building block for constructing succinct data structures, including rank/select data structures, dictionaries, locally decodable arithmetic coding, storing balanced parenthesis, etc. In this paper, we show how to "dynamize" an aB-tree. Our main result is the design of dynamic aB-trees (daB-trees) with branching factor two using only three bits of redundancy (with the help of lookup tables that are of negligible size in applications), while supporting updates and queries in time polynomial in its depth. As an application, we present a dynamic rank/select data structure for n-bit arrays, also known as a dynamic fully indexable dictionary (FID) [2]. It supports updates and queries in O(log n/log log n) time, and when the array has m ones, the data structure occupies log ((n) (m)) + O(n/2(log0.199 n)) bits. Note that the update and query times are optimal even without space constraints due to a lower bound by Fredman and Saks [3]. Prior to our work, no dynamic FID with near-optimal update and query times and redundancy o(n/ log n) was known. We further show that a dynamic sequence supporting insertions, deletions and rank/select queries can be maintained in (optimal) O(log n/ log log n) time and with O(n. poly log log n/ log(2) n) bits of redundancy.

关键词： succinct data structures dynamic data structures B-trees

来源：评论

学校读者我要写书评

暂无评论

A dynamic data structure for temporal reachability with unsorted contact insertions

引用

SOCIAL NETWORK ANALYSIS AND MINING 2022年第1期12卷 1-12页

作者： Brito, Luiz F. A. Albertini, Marcelo K. Casteigts, Arnaud Travencolo, Bruno A. N. Univ Fed Uberlandia Uberlandia MG Brazil Univ Bordeaux Bordeaux France

Temporal graphs represent interactions between entities over the time. These interactions may be direct (a contact between two nodes at some time instant), or indirect, through sequences of contacts called temporal paths (journeys). Deciding whether an entity can reach another through a journey is useful for various applications in communication networks and epidemiology, among other fields. In this paper, we present a data structure that maintains temporal reachability information under the addition of new contacts. In contrast to previous works, the contacts can be inserted in an arbitrary order-in particular, non-chronologically-which corresponds to systems where the information is collected a posteriori (e.g., when trying to reconstruct contamination chains among people). The main component of our data structure is a generalization of transitive closure called timed transitive closure (TTC), which allows us to maintain reachability information relative to all nested time intervals, without storing all these intervals, nor the journeys themselves. Let n be the number of nodes and tau be the number of timestamps in the lifetime of the temporal graph. Our data structure answers reachability queries regarding the existence of a journey from a given node to another within a given time interval in time O(log tau);it has a worst-case insertion time of O(n(2) log tau);and it can reconstruct a valid journey that witnesses reachability in time O(k log tau), where k < n is the maximum number of contacts of this journey. Finally, the space complexity of our reachability data structure is O(n(2)tau), which remains within the worst-case size of the temporal graph itself.

关键词： Temporal graph Reachability dynamic data structures Transitive closure

来源：评论

学校读者我要写书评

暂无评论

On the Planar Two-Center Problem and Circular Hulls

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2022年第4期68卷 1175-1226页

作者： Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

Given a set S of n points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of S. Previously, Eppstein (SODA'97) gave a randomized algorithm of O (n log(2)n) expected time and Chan (CGTA'99) presented a deterministic algorithm of O (n log(2)n log(2)log n) time. In this paper, we propose an O (n log(2)n) time deterministic algorithm, which improves Chan's deterministic algorithm and matches the randomized bound of Eppstein. If S is in convex position, then we solve the problem in O (n log n log log n) deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.

关键词： Two centers Disk coverage Circular hulls dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

dynamic Suffix Array with Polylogarithmic Queries and Updates 2022

Dynamic Suffix Array with Polylogarithmic Queries and Update...

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Kempa, Dominik Kociumaka, Tomasz SUNY Stony Brook Stony Brook NY 11794 USA Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9781450392648

The suffix array SA [1..n] of a text T of length n is a permutation of {1, ..., n} describing the lexicographical ordering of suffixes of T and is considered to be one of the most important data structures for string processing, with dozens of applications in data compression, bioinformatics, and information retrieval. One of the biggest drawbacks of the suffix array is that it is very difficult to maintain under text updates: even a single character substitution can completely change the contents of the suffix array. Thus, the suffix array of a dynamic text is modelled using suffix array queries, which return the value SA [i] given any i is an element of [1..n]. Prior to this work, the fastest dynamic suffix array implementations were by Amir and Boneh, who showed how to answer suffix array queries in (O) over tilde (k) time, where k is an element of [1..n] is a trade-off parameter, with (O) over tilde (n/k)-time text updates [ISAAC 2020]. In a very recent preprint, they also provided a solution with O (log(5)n)-time queries and (O) over tilde (n(2/3))-time updates [arXiv 2021]. We propose the first data structure that supports both suffix array queries and text updates in O(polylog n) time (achieving O(log(4) n) and O(log(3+o (1)) n) time, respectively). Our data structure is deterministic and the running times for all operations are worst-case. In addition to the standard single-character edits (character insertions, deletions, and substitutions), we support (also in O(log (3+o(1)) n) time) the "cut-paste" operation that moves any (arbitrarily long) substring of T to any place in T. To achieve our result, we develop a number of new techniques which are of independent interest. This includes a new flavor of dynamic locally consistent parsing, as well as a dynamic construction of string synchronizing sets with an extra local sparsity property;this significantly generalizes the sampling technique introduced at STOC 2019. We complement our structure by a hardness res

关键词： Suffix array text indexing pattern matching string synchronizing sets dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Tight dynamic Problem Lower Bounds from Generalized BMM and OMv 2022

Tight Dynamic Problem Lower Bounds from Generalized BMM and ...

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Jin, Ce Xu, Yinzhan MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450392648

Popular fine-grained hypotheses have been successful in proving conditional lower bounds for many dynamic problems. Two of the most widely applicable hypotheses in this context are the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis. The main theme of this paper is using k-dimensional generalizations of these two hypotheses to prove new tight conditional lower bounds for dynamic problems. The combinatorial k-Clique hypothesis, which is a standard hypothesis in the literature, naturally generalizes the combinatorial BMM hypothesis. In this paper, we prove tight lower bounds for several dynamic problems under the combinatorial k-Clique hypothesis. For instance, we show that the dynamic Range Mode problem has no combinatorial algorithms with poly(n) pre-processing time, O(n(2/3)(-epsilon)) update time and O(n(2/3)(-epsilon)) query lime for any epsilon > 0, matching the known upper bounds for this problem. Previous lower bounds only ruled out algorithms with O(n(2/3)(-epsilon)) update and query time under the OMv hypothesis. We also show that the dynamic Subgraph Connectivity problem on undirected graphs with m edges has no combinatorial algorithms with poly(m) preprocessing time, O(m(2/3)(-epsilon)) update time and O(m(1-epsilon)) query time for epsilon > 0, matching the upper bound given by Chan, Patrascu, and Roditty [SICOMP'11], and improving the previous update time lower bound (based on OMv) with exponent 1/2. Other examples include tight combinatorial lower bounds for dynamic 2D Orthogonal Range Color Counting, dynamic 2-Pattern Document Retrieval, and dynamic Range Mode in higher dimensions. Furthermore, we propose the OuMv(k) hypothesis as a natural generalization of the OMv hypothesis. Under this hypothesis, we prove tight lower bounds for various dynamic problems. For instance, we show that the dynamic Skyline Points Counting problem in (2k - 1)-dimensional space has no

关键词： fine-grained complexity dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Maintaining Exact Distances under Multiple Edge Failures 2022

Maintaining Exact Distances under Multiple Edge Failures

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Duan, Ran Ren, Hanlin Tsinghua Univ Beijing Peoples R China Univ Oxford Oxford England

ISBN: (纸本)9781450392648

We present the first compact distance oracle that tolerates multiple failures and maintains exact distances. Given an undirected weighted graph G = (V, E) and an arbitrarily large constant d, we construct an oracle that given vertices u, v is an element of V and a set of d edge failures D, outputs the exact distance between u and v in G - D (that is, G with edges in D removed). Our oracle has space complexity O(dn(4)) and query time d(O(d)). Previously, there were compact approximate distance oracles under multiple failures [Chechik, Cohen, Fiat, and Kaplan, SODA'17;Duan, Gu, and Ren, SODA'21], but the best exact distance oracles under d failures require essentially Omega(n(d)) space [Duan and Pettie, SODA'09]. Our distance oracle seems to require n(Omega(d)) time to preprocess;we leave it as an open question to improve this preprocessing time.

关键词： Distance sensitivity oracles dynamic data structures shortest paths

来源：评论

学校读者我要写书评

暂无评论

Buffering updates enables efficient dynamic de Bruijn graphs

引用

COMPUTATIONAL AND STRUCTURAL BIOTECHNOLOGY JOURNAL 2021年 19卷 4067-4078页

作者： Alanko, Jarno Alipanahi, Bahar Settle, Jonathen Boucher, Christina Gagie, Travis Univ Helsinki Dept Comp Sci Helsinki Finland Dalhousie Univ Fac Comp Sci Halifax NS Canada Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL USA

Motivation: The de Bruijn graph has become a ubiquitous graph model for biological data ever since its initial introduction in the late 1990s. It has been used for a variety of purposes including genome assembly (Zerbino and Birney, 2008;Bankevich et al., 2012;Peng et al., 2012), variant detection (Alipanahi et al., 2020b;Iqbal et al., 2012), and storage of assembled genomes (Chikhi et al., 2016). For this reason, there have been over a dozen methods for building and representing the de Bruijn graph and its variants in a space and time efficient manner. Results: With the exception of a few data structures (Muggli et al., 2019;Holley and Melsted, 2020;Crawford et al.,2018), compressed and compact de Bruijn graphs do not allow for the graph to be efficiently updated, meaning that data can be added or deleted. The most recent compressed dynamic de Bruijn graph (Alipanahi et al., 2020a), relies on dynamic bit vectors which are slow in theory and practice. To address this shortcoming, we present a compressed dynamic de Bruijn graph that removes the necessity of dynamic bit vectors by buffering data that should be added or removed from the graph. We implement our method, which we refer to as BufBOSS, and compare its performance to Bifrost, dynamicBOSS, and FDBG. Our experiments demonstrate that BufBOSS achieves attractive trade-offs compared to other tools in terms of time, memory and disk, and has the best deletion performance by an order of magnitude. (C) 2021 The Authors. Published by Elsevier B.V. on behalf of Research Network of Computational and Structural Biotechnology.

关键词： de Bruijn graph dynamic data structures Succinct data structures Burrows-Wheeler transform

来源：评论

学校读者我要写书评

暂无评论

Conditional Lower Bounds for dynamic Geometric Measure Problems

引用

ACM TRANSACTIONS ON ALGORITHMS 2025年第2期21卷

作者： Dallant, Justin Iacono, John Univ Libre Bruxelles Comp Sci Dept Brussels Belgium Aarhus Univ Dept Comp Sci Aarhus Denmark

We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word RAM model, conditioned on the hardness of 3SUM, APSP, or the Online Matrix-Vector Multiplication problem [Henzinger et al., STOC 2015]. In particular, we get lower bounds in the incremental and fully dynamic settings for counting maximal or extremal points in R3, different variants of Klee's Measure Problem, problems related to finding the largest empty disk in a set of points, and querying the size of the ith convex layer in a planar set of points. We also answer a question of Chan et al. [SODA 2022] by giving a conditional lower bound for dynamic approximate square set cover. While many conditional lower bounds for dynamic data structures have been proven since the seminal work of P & abreve;tra & scedil;cu [STOC 2010], few of them relate to computational geometry problems. This is the first article focusing on this topic. Most problems we consider can be solved in O(n log n) time in the static case, and their dynamic versions have only been approached from the perspective of improving known upper bounds. One exception to this is Klee's measure problem in R2, for which Chan [CGTA 2010] gave an unconditional Omega (root n) lower bound on the worst-case update time in a variant of the Word RAM machine with large words. By a similar approach, we show that such a lower bound also holds for an important special case of Klee's measure problem in R3known as the Hypervolume Indicator problem, even for amortized runtime in the incremental setting.

关键词： Computational geometry Fine-grained complexity dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：