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

Combining Functional and Automata Synthesis to Discover Causal Reactive Programs

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2023年第POPL期7卷 1628-1658页

作者： Das, Ria Tenenbaum, Joshua B. Solar-Lezama, Armando Tavares, Zenna Stanford Univ Stanford CA 94305 USA MIT Cambridge MA 02139 USA Basis Res Inst Chicago IL USA Columbia Univ New York NY 10027 USA

We present a new algorithm that synthesizes functional reactive programs from observation data. The key novelty is to iterate between a functional synthesis step, which attempts to generate a transition function over observed states, and an automata synthesis step, which adds any additional latent state necessary to fully account for the observations. We develop a functional reactive DSL called Autumn that can express a rich variety of causal dynamics in time-varying, Atari-style grid worlds, and apply our method to synthesize Autumn programs from data. We evaluate our algorithm on a benchmark suite of 30 Autumn programs as well as a third-party corpus of grid-world-style video games. We find that our algorithm synthesizes 27 out of 30 programs in our benchmark suite and 21 out of 27 programs from the third-party corpus, including several programs describing complex latent state transformations, and from input traces containing hundreds of observations. We expect that our approach will provide a template for how to integrate functional and automata synthesis in other induction domains.

关键词： synthesis automata reactive causal

来源：评论

学校读者我要写书评

暂无评论

A column generation approach to the discrete barycenter problem

引用

DISCRETE OPTIMIZATION 2022年第0期43卷 100674-100674页

作者： Borgwardt, Steffen Patterson, Stephan Univ Colorado Denver CO 80202 USA Louisiana State Univ Shreveport LA 71105 USA

The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of discrete probability measures. Although an exact barycenter is computable through linear programming, the underlying linear program can be extremely large. For worst-case input, a best known linear programming formulation is exponential in the number of variables, but has a low number of constraints, making it an interesting candidate for column generation. In this paper, we devise and study two column generation strategies: a natural one based on a simplified computation of reduced costs, and one through a Dantzig-Wolfe decomposition. For the latter, we produce efficiently solvable subproblems, namely, a pricing problem in the form of a classical transportation problem. The two strategies begin with an efficient computation of an initial feasible solution. While the structure of the constraints leads to the computation of the reduced costs of all remaining variables for setup, both approaches may outperform a computation using the full program in speed, and dramatically so in memory requirement. In our computational experiments, we exhibit that, depending on the input, either strategy can become a best choice. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Discrete barycenter Optimal transport Linear programming Column generation

来源：评论

学校读者我要写书评

暂无评论

Error-Correcting Codes for Short Tandem Duplication and Edit Errors

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第2期68卷 871-880页

作者： Tang, Yuanyuan Farnoud, Farzad Univ Virginia Dept Elect & Comp Engn Charlottesville VA 22903 USA Univ Virginia Dept Comp Sci Charlottesville VA 22903 USA

Due to its high data density and longevity, DNA is considered a promising medium for satisfying ever-increasing data storage needs. However, the diversity of errors that occur in DNA sequences makes efficient error-correction a challenging task. This paper aims to address simultaneously correcting two types of errors, namely, short tandem duplication and edit errors, where an edit error may be a substitution, deletion, or insertion. We focus on tandem repeats of length at most 3 and design codes for correcting an arbitrary number of duplication errors and one edit error. Because an edited symbol can be duplicated many times (as part of substrings of various lengths), a single edit can affect an unbounded substring of the retrieved word. However, we show that with appropriate preprocessing, the effect may be limited to a substring of finite length, thus making efficient error-correction possible. We construct a code for correcting the aforementioned errors and provide lower bounds for its rate. Compared to optimal codes correcting only duplication errors, numerical results show that the asymptotic cost of protecting against an additional edit is only 0.003 bits/symbol when the alphabet has size 4, an important case corresponding to data storage in DNA.

关键词： DNA Error correction codes Memory Task analysis Sequential analysis Noise measurement Media DNA data storage error-correcting codes duplication errors edit errors

来源：评论

学校读者我要写书评

暂无评论

WHISTLE: CPU Abstractions for Hardware and Software Memory Safety Invariants

引用

IEEE TRANSACTIONS ON COMPUTERS 2023年第3期72卷 811-825页

作者： Kim, Sungkeun Mahmud, Farabi Huang, Jiayi Majumder, Pritam Tsai, Chia-Che Muzahid, Abdullah Kim, Eun Jung Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA

Memory safety invariants extracted from a program can help defend and detect against both software and hardware memory violations. For instance, by allowing only specific instructions to access certain memory locations, system can detect out-of-bound or illegal pointer dereferences that lead to correctness and security issues. In this paper, we propose CPU abstractions, called WHISTLE, to specify and check program invariants to provide defense mechanism against both software and hardware memory violations at runtime. WHISTLE ensures that the invariants must be satisfied at every memory access. We present a fast invariant address translation and retrieval scheme using a specialized cache. It stores and checks invariants related to global, stack and heap objects. The invariant checks can be performed synchronously or asynchronously. WHISTLE uses synchronous checking for high security-critical programs, while others are protected by asynchronous checking. A fast exception is proposed to alert any violations as soon as possible in order to close the gap for transient attacks. Our evaluation shows that WHISTLE can detect both software and hardware, spatial and temporal memory violations. WHISTLE incurs 53% overhead when checking synchronously, or 15% overhead when checking asynchronously.

关键词： Cache architecture hardware defense hardware-assisted security memory safety program invariants

来源：评论

学校读者我要写书评

暂无评论

Pseudorandom Bits and Lower Bounds for Randomized Turing Machines

引用

THEORY OF computing 2022年 18卷 1-12页

作者： Viola, Emanuele Northeastern Univ Khoury Coll Comp Sci Boston MA 02115 USA

We exhibit a pseudorandom generator with nearly quadratic stretch for randomized Turing machines, which have a one-way random tape and a two-way work tape. This is the first generator for this model. Its stretch is essentially the best possible given current lower bounds. We use the generator to prove a time lower bound in the above Turing machine model extended with a two-way read-only input tape. The lower bound is of the form n1+s1(1) and is for a function computable in linear time with two quantifier alternations. Previously lower bounds were not known even for functions computable in simply exponential time.

关键词： lower bound Turing machine pseudorandom generator tape

来源：评论

学校读者我要写书评

暂无评论

Distributionally Robust Fair Transit Resource Allocation During a Pandemic

引用

TRANSPORTATION SCIENCE 2022年第4期57卷 954页

作者： Sun, Luying Xie, Weijun Witten, Tim Virginia Tech Dept Ind Syst Engn Blacksburg VA 24061 USA Blacksburg Transit Blacksburg VA 24060 USA

This paper studies the distributionally robust fair transit resource allocation model (DrFRAM) under the Wasserstein ambiguity set to optimize the public transit resource allocation during a pandemic. We show that the proposed DrFRAM is highly nonconvex and nonlinear, and it is NP-hard in general. Fortunately, we show that DrFRAM can be reformulated as a mixed integer linear programming (MILP) by leveraging the equivalent representation of distributionally robust optimization and monotonicity properties, binarizing integer variables, and linearizing nonconvex terms. To improve the proposed MILP formulation, we derive stronger ones and develop valid inequalities by exploiting the model structures. Additionally, we develop scenario decomposition methods using different MILP formulations to solve the scenario subproblems and introduce a simple yet effective no one left-based approximation algorithm with a provable approximation guarantee to solve the model to near optimality. Finally, we numerically demonstrate the effectiveness of the proposed approaches and apply them to real-world data provided by the Blacksburg Transit.

关键词： distributionally robust mixed-integer programming strong formulations valid inequalities

来源：评论

学校读者我要写书评

暂无评论

Transmit Correlation Diversity: Generalization, New Techniques, and Improved Bounds

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第6期68卷 3841-3869页

作者： Zhang, Fan Ngo, Khac-Hoang Yang, Sheng Nosratinia, Aria Univ Texas Dallas Dept Elect & Comp Engn Richardson TX 75080 USA Chalmers Univ Technol Dept Elect Engn S-41296 Gothenburg Sweden Paris Saclay Univ CentraleSuplec Lec F-91190 Gif Sur Yvette France

When the users in a MIMO broadcast channel experience different spatial transmit correlation matrices, a class of gains is produced that is denoted transmit correlation diversity. This idea was conceived for channels in which transmit correlation matrices have mutually exclusive eigenspaces, allowing non-interfering training and transmission. This paper broadens the scope of transmit correlation diversity to the case of partially and fully overlapping eigenspaces and introduces techniques to harvest these generalized gains. For the two-user MIMO broadcast channel, we derive achievable degrees of freedom (DoF) and achievable rate regions with/without channel state information at the receiver (CSIR). When CSIR is available, the proposed achievable DoF region is tight in some configurations of the number of receive antennas and the channel correlation ranks. We then extend the DoF results to the K -user case by analyzing the interference graph that characterizes the overlapping structure of the eigenspaces. Our achievability results employ a combination of product superposition in the common part of the eigenspaces, and pre-beamforming (rate splitting) to create multiple data streams in non-overlapping parts of the eigenspaces. Massive MIMO is a natural example in which spatially correlated link gains are likely to occur. We study the achievable downlink sum rate for a frequency-division duplex massive MIMO system under transmit correlation diversity.

关键词： MIMO broadcast channels spatial correlation channel state information rate splitting product superposition

来源：评论

学校读者我要写书评

暂无评论

MC-CIM: Compute-in-Memory With Monte-Carlo Dropouts for Bayesian Edge Intelligence

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2023年第2期70卷 884-896页

作者： Shukla, Priyesh Nasrin, Shamma Darabi, Nastaran Gomes, Wilfred Trivedi, Amit Ranjan Univ Illinois Dept Elect & Comp Engn Chicago IL 60607 USA Intel Santa Clara CA 95054 USA

We propose MC-CIM, a compute-in-memory (CIM) framework for robust, yet low power, Bayesian edge intelligence. Deep neural networks (DNN) with deterministic weights cannot express their prediction uncertainties, thereby pose critical risks for applications where the consequences of mispredictions are fatal such as surgical robotics. To address this limitation, Bayesian inference of a DNN has gained attention. Using Bayesian inference, not only the prediction itself, but the prediction confidence can also be extracted for planning risk-aware actions. However, Bayesian inference of a DNN is computationally expensive, ill-suited for real-time and/or edge deployment. An approximation to Bayesian DNN using Monte Carlo Dropout (MC-Dropout) has shown high robustness along with low computational complexity. Enhancing the computational efficiency of the method, we discuss a novel CIM module that can perform in-memory probabilistic dropout in addition to in-memory weight-input scalar product to support the method. We also propose a compute-reuse reformulation of MC-Dropout where each successive instance can utilize the product-sum computations from the previous iteration. Even more, we discuss how the random instances can be optimally ordered to minimize the overall MC-Dropout workload by exploiting combinatorial optimization methods. Application of the proposed CIM-based MC-Dropout execution is discussed for MNIST character recognition and visual odometry (VO) of autonomous drones. The framework reliably gives prediction confidence amidst non-idealities imposed by MC-CIM to a good extent. Proposed MC-CIM with 16 x 31 SRAM array, 0.85 V supply, 16nm low-standby power (LSTP) technology consumes 32 pJ for 30 MC-Dropout instances of probabilistic inference in its most optimal computing and peripheral configuration, saving similar to 34% energy compared to typical execution.

关键词： Bayesian inference compute-in-memory Monte-Carlo dropout visual odometry

来源：评论

学校读者我要写书评

暂无评论

ALCH: An imperative language for chemical reaction network-controlled tile assembly

引用

NATURAL computing 2024年第2期23卷 365-385页

作者： Klinge, Titus H. Lathrop, James, I Moreno, Sonia Potter, Hugh D. Raman, Narun K. Riley, Matthew R. Drake Univ Des Moines IA 50311 USA Iowa State Univ Ames IA 50011 USA Univ British Columbia Vancouver BC Canada

Schiefer and Winfree recently introduced the chemical reaction network-controlled tile assembly model (CRN-TAM), a variant of the abstract tile assembly model (aTAM). In the CRN-TAM, tile reactions are mediated via non-local chemical signals controlled by a chemical reaction network. This paper introduces ALCH, an imperative programming language for specifying CRN-TAM programs that can be compiled and simulated. ALCH includes standard language features such as Boolean variables, conditionals, loops, and CRN-TAM-specific constructs such as adding and removing tiles. ALCH also includes the branch and parallel structures which harness the nondeterministic and parallel nature of the CRN-TAM. ALCH also supports functional tileset specification. Using ALCH, we show that the discrete Sierpinski triangle and the discrete Sierpinski carpet can be strictly self-assembled in the CRN-TAM, which shows the CRN-TAM can self-assemble infinite shapes at scale 1 that the aTAM cannot. ALCH allows us to present these constructions at a high level, abstracting species and reactions into C-like code that is simpler to understand. We employ two new CRN-TAM techniques in our constructions. First, we use ALCH's nondeterministic branching feature to probe previously placed tiles of the assembly and detect the presence and absence of tiles. Second, we use scaffolding tiles to precisely control tile placement by occluding any undesired binding sites. This paper is an extension of our previous work, updated to include a Sierpinski carpet construction and the parallel command.

关键词： Tile assembly Chemical reaction network Sierpinski triangle Sierpinski carpet Molecular programming language

来源：评论

学校读者我要写书评

暂无评论

Domain Wall Leaky Integrate-and-Fire Neurons With Shape-Based Configurable Activation Functions

引用

IEEE TRANSACTIONS ON ELECTRON DEVICES 2022年第5期69卷 2353-2359页

作者： Brigner, Wesley H. Hassan, Naimul Hu, Xuan Bennett, Christopher H. Garcia-Sanchez, Felipe Cui, Can Velasquez, Alvaro Marinella, Matthew J. Incorvia, Jean Anne C. Friedman, Joseph S. Univ Texas Dallas Dept Elect & Comp Engn Richardson TX 75080 USA Sandia Natl Labs Albuquerque NM 87213 USA Univ Salamanca Dept Appl Phys Salamanca 37008 Spain Univ Texas Austin Dept Elect & Comp Engn Austin TX 78712 USA Air Force Res Lab Informat Directorate Rome NY 13441 USA Arizona State Univ Tempe AZ 85281 USA

CMOS devices display volatile characteristics and are not well suited for analog applications such as neuromorphic computing. Spintronic devices, on the other hand, exhibit both non-volatile and analog features, which are well suited to neuromorphic computing. Consequently, these novel devices are at the forefront of beyond-CMOS artificial intelligence applications. However, a large quantity of these artificial neuromorphic devices still require the use of CMOS to implement various neuromorphic functionalities, which decreases the efficiency of the system. To resolve this, we have previously proposed a number of artificial neurons and synapses that do not require CMOS for operation. Although these devices are a significant improvement over previous renditions, their ability to enable neural network learning and recognition is limited by their intrinsic activation functions. This work proposes modifications to these spintronic neurons that enable configuration of the activation functions through control of the shape of a magnetic domain wall track. Linear and sigmoidal activation functions are demonstrated in this work, which can be extended through a similar approach to enable a wide variety of activation functions.

关键词： Neurons Synapses Spintronics Magnetic tunneling Neuromorphic engineering Magnetic domain walls Mathematical models Artificial neural network leaky integrate-and-fire (LIF) neuron multilayer perceptron neuromorphic computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：