文献

J-GLOBAL ID：202002265259994667   整理番号：20A1444656

多項式時間代数構造の定義可能部分集合【JST・京大機械翻訳】

Definable Subsets of Polynomial-Time Algebraic Structures

著者 (2件)： Bazhenov Nikolay (Sobolev Institute of Mathematics, Novosibirsk, Russia) ,  Bazhenov Nikolay (Novosibirsk State University, Novosibirsk, Russia)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12159  ページ： 142-154  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 有限署名[数式:原文を参照]における構造Sは,SのドメインとSの基礎的操作と関係が多項式時間計算可能であれば多項式時間である。意味プログラミングのアプローチに従って,与えられた多項式時間構造Sのために,著者らは,パラメータを有する[数式:原文を参照]式によって定義できる[数式:原文を参照]のすべての部分集合を含むファミリーB(S)を考察した。これらの集合の各々は多項式時間計算可能として知られている。したがって,標準集合理論的操作に付与されたB(S)は,Sと関連する多項式時間言語の自然Boole代数を形成する。同形写像まで,Sが多項式時間構造である代数B(S)は,正確に計算可能な原子Boole代数であることを証明した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： Boole代数 ,  集合論 ,  言語 ,  *同形写像
準シソーラス用語： 多項式時間 , 【Automatic Indexing@JST】

著者キーワード (7件)： 多項式時間構造 ,  [数式:原文を参照]公式 ,  [数式:原文を参照]定義可能性 ,  遺伝的有限超構造 ,  計算可能な構造理論 ,  リスト構造 ,  Boole代数

分類 (2件)： 計算理論  (JB02000A) ,  システム・制御理論一般  (IA02010H)

タイトルに関連する用語 (4件)： 多項式時間 ,  代数 ,  定義 ,  部分集合