专栏首页arxiv.org翻译专栏随机存取机器程序的程序代数(cs)
原创

随机存取机器程序的程序代数(cs)

本文提出了一种以随机存取机(RAM)指令为基本指令的指令序列的代数理论,以及指令序列在执行过程中产生的行为,以及这些行为与RAM存储器之间的相互作用。这一理论为理论的发展提供了条件,例如计算复杂度和算法分析,这些领域通过提供等式推理的可能性来区分自身,以确定指令序列是否计算给定函数,并且提供了比任何已知版本的设置更通用计算的RAM模型。在此背景下,介绍了一个半现实版本的RAM计算模型和一个面向位的时间复杂度度量方法。

原文题目:Program algebra for random access machine programs

原文: This paper presents an algebraic theory of instruction sequences with instructions for a random access machine (RAM) as basic instructions, the behaviours produced by the instruction sequences concerned under execution, and the interaction between such behaviours and RAM memories. This theory provides a setting for the development of theory in areas such as computational complexity and analysis of algorithm that distinguishes itself by offering the possibility of equational reasoning to establish whether an instruction sequence computes a given function and being more general than the setting provided by any known version of the RAM model of computation. In this setting, a semi-realistic version of the RAM model of computation and a bit-oriented time complexity measure for this version are introduced.

原文作者:C. A. Middelburg

原文地址:https://arxiv.org/abs/2007.09946

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一种高效实用的多重加权Voronoi图计算算法及实现(CS CG)

    本文提出了一种简单的波前方法来计算欧氏平面上点和直线段的多重加权Voronoi图。如果输入点可以假设为随机加权点,则使用所谓的叠加排列[Har-Peled&Ra...

    用户7454091
  • 工业机器人协同安全保障面临的挑战(cs)

    中文摘要:系统安全和网络安全等相关关键属性的协同保障是关键系统工程中最棘手的挑战之一。在本章中,我们总结了协调保障安全和安全的方法。然后,我们从安全和安全的角度...

    用户7454091
  • 动力学方程的保守半拉格朗日格式第一部分:重构(cs)

    在本文中,我们提出并分析一种重建技术,使一个人设计高阶保守半拉格朗日格式的动力学方程。所提出的重构可以通过对数值解的多项式重构取滑动平均来获得。给出了高阶保守重...

    用户7454091
  • 形态系统中探索性搜索的分层组织潜在模块(CS AI)

    在许多自然和人工系统中,由局部相互作用引起的复杂形态模式的自组织是一个令人着迷的现象。在人工世界中,这种形态发生系统的典型例子是细胞自动机。但是,它们的机制通常...

    刘子蔚
  • 一种高效实用的多重加权Voronoi图计算算法及实现(CS CG)

    本文提出了一种简单的波前方法来计算欧氏平面上点和直线段的多重加权Voronoi图。如果输入点可以假设为随机加权点,则使用所谓的叠加排列[Har-Peled&Ra...

    用户7454091
  • gan生成图像at 1024² 的 代码 论文

    https://github.com/tkarras/progressive_growing_of_gans

    用户1908973
  • md5算法原理一窥(其一)

        首先,需要了解的事,md5并不是传说中的加密算法,只是一种散列算法。其加密的算法并不是我们说所的那样固定不变,只是一种映射的关系。 所以解密MD5没有现...

    Gxjun
  • 调查计算语言文档双语方法中的语言影响(Computation and Language)

    对于濒危语言而言,数据收集活动必须能够应对很多数据源自口传而且生产副本费用高昂的挑战。因此,为了确保录音的可解释性,至少要将这些录音转译成使用广泛的语言版本。本...

    用户6868260
  • 通过重写模板生成的少量的自然语言(CS.CL)

    谷歌Assistant、Alexa和Siri等虚拟助手能够让用户在网上使用自然语言与大量服务和APIs交互。响应生成模块将策略模块生成的动作转换为自然语言语句。...

    用户7236395
  • SketchGraphs:计算机辅助设计中关系几何建模的大型数据集(CS)

    参数化计算机辅助设计(CAD)是机械工程物理设计的主流范式。与关系几何不同的是,参数化CAD模型从二维草图开始,由几何图元(例如线段、圆弧)和它们之间的明确约束...

    N乳酸菌

扫码关注云+社区

领取腾讯云代金券