Gray-code representation of real number and the induced computability structure
Gray-code representation of real number and the induced computability structure
批准号:
15500010
负责人:
TSUIKI Hideki
金额:
$1.6万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (C)
财政年份:
2003
资助国家:
日本
项目状态:
已结题
起止时间:
2003 至 2005
中文摘要
我们研究了与实数可计算结构相关的计算、拓扑和领域理论问题,这些实数可计算结构由{0,1,bot}无限序列(灰码表示)和不确定多头机(IM2-machine)的表示形式推导而来。im2机器可以用带有守卫的逻辑编程语言来实现,比如GHC(守卫角子句)。当我们考虑{0,1,bot}无穷数列上的函数时,GHC中可表示的函数集大于im2可计算的函数集,但当只考虑实数表示时,它们是相等的。函数式语言是无法实现IM2-machines的,但通过对函数式语言进行扩展,用一个受限的amb算子,用顺序图约简规则代替项约简规则来实现IM2-machines的能力。我们将它作为Haskell语言的扩展来实现。表示拓扑空间所需的底部数量与空间的拓扑维数相等。我们在代数定义域上得到了一个更一般的结果,并从定义域理论上证明了它。拓扑空间的编码与子基是密切相关的。生成自然计算结构的编码将生成一个基于正则开集对的二进子基。通过拓扑研究相应子基的性质,可以表征灰度码表示的效率。
英文摘要
We studied computational, topological, and domain-theoretic problems related to the computable structure of real numbers derived form representation with {0,1,bot}-infinite sequences (Gray-code representation) and indeterministic multi-head machine (IM2-machine) operating on them.1.IM2-machines can be realized with logic programming languages with guards like GHC (Guarded Horn Clauses). The set of functions expressible in GHC is larger than the set of IM2-computable functions when we consider functions over {0,1,bot}-infinite sequences but they are equal when only real number representation is considered.2.IM2-machines cannot be realized with functional languages, but by extending a functional language with a restricted amb operator which is realized with sequential graph reduction rules instead of term reduction rules, one can implement the ability of IM2-machines. We have implemented it as an extension of the Haskell language.3.The number of bottoms required to represent a topological space and the topological dimension of the space is equal. We have a more general result on an algebraic domain, which is proved domain-theoretically.4.Codings and subbases of a topological space are closely related. Codings which induce natural computational structure will induce a dyadic subbase, which is based on pairs of regular open sets. The efficiency of the Gray-code representation can be characterized through properties of the corresponding subbase, which are studied topologically.
期刊论文(29)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
Compact metric spaces as minimal-limit sets in domains of bottomed sequences
紧致度量空间作为有底序列域中的最小极限集
DOI:
--
发表时间:
2004
期刊:
Mathematical Structures in Computer Science 14(6)
影响因子:
--
作者:
[M.Oyamaguchi, Y.Ohta, Hideki Tsuiki]
通讯作者:
Hideki Tsuiki
Dyadic subbases and efficiency properties of the induced (0, 1, bot) ^omega-representations
诱导的 (0, 1, bot) ^omega 表示的二元底基和效率特性
DOI:
--
发表时间:
2004
期刊:
Topology Proceedings 28(2)
影响因子:
--
作者:
[Chika Oshima, Naoki Itou, Kazushi Nishimoto, Masahide Naemura, Hideki Tsuiki]
通讯作者:
Hideki Tsuiki
A Domain-theoretic Semantics of Lax Generic Functions
宽松泛型函数的领域理论语义
DOI:
--
发表时间:
2003
期刊:
Theoretical Computer Science 294
影响因子:
--
作者:
[Hideki Tsuiki, Keiji Sugihara, Hideki Tsuiki, Hideki Tsuiki, Hideki Tsuiki, Hideki Tsuiki, Hideki Tsuiki, Hideki Tsuiki, Hideki Tsuiki, Hideki Tsuiki, Hideki Tsuiki]
通讯作者:
Hideki Tsuiki
Embedding Compact Metric Spaces as Minimal-limit Sets in Domains of Bottomed Sequences
将紧度量空间嵌入为有底序列域中的最小极限集
DOI:
--
发表时间:
2004
期刊:
Mathematical Structures in Computer Science 14(6)
影响因子:
--
作者:
[有村光晴, 長岡浩司, Hideki Tsuiki]
通讯作者:
Hideki Tsuiki
Hideki Tsuiki: "Embedding Compact Metric Spaces as Minimal-limit Sets in Domains of Bottomed Sequences"Mathematical Structures in Computer Science.
Hideki Tsuiki:“将紧度量空间嵌入为底序列域中的最小极限集”计算机科学中的数学结构。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
共 13 条
Studies on representation-based computational structures of spaces and figures, and on related structures like fractals
-
批准号:22500014
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.41万
-
财政年份:2010
-
负责人:TSUIKI Hideki
-
依托单位:
Research on computable structures of continuous spaces like the real number through representation in bottomed sequences
-
批准号:18500013
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.32万
-
财政年份:2006
-
负责人:TSUIKI Hideki
-
依托单位:
海外基金