Warning : Undefined variable $type in /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php on line 3
Warning : "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/includes/json/FormatJson.php on line 297
Warning : Trying to access array offset on value of type bool in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 660
Warning : session_name(): Session name cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 834
Warning : ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 126
Warning : ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 127
Warning : session_cache_limiter(): Session cache limiter cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 133
Warning : session_set_save_handler(): Session save handler cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 140
Warning : "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/languages/LanguageConverter.php on line 773
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 294
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 300
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
http:///mymemo.xyz/wiki/api.php?action=feedcontributions&feedformat=atom&user=123.176.148.176
miniwiki - 利用者の投稿記録 [ja]
2024-05-23T15:17:01Z
利用者の投稿記録
MediaWiki 1.31.0
カール・ワイエルシュトラス
2017-06-17T08:43:20Z
<p>123.176.148.176: /* 業績 */</p>
<hr />
<div>[[ファイル:Karl_Weierstrass.jpg|thumb|right|カール・ワイエルシュトラス]]<br />
'''カール・テオドル・ヴィルヘルム・ワイエルシュトラス'''({{lang|de|Karl Theodor Wilhelm Weierstraß}}, [[1815年]][[10月31日]] – [[1897年]][[2月19日]])は[[ドイツ]]の[[数学者]]である。姓のワイ (Wei) の部分はヴァイと表記するほうが正確である。また、"er" に当たる部分はエル/ヤ/ア、"st" はシュト/スト、"raß" はラス/ラースとそれぞれ表記されることがある。<br />
<br />
== 経歴 ==<br />
[[バイエルン州]]オステンフェルデの教養あるカトリック教徒の家庭に生まれ育つ<ref name="math">日本数学会編、『岩波数学辞典 第4版』、岩波書店、2007年、項目「ワイエルシュトラス」より。ISBN 978-4-00-080309-0 C3541 </ref>。<br />
<br />
父に言われ、1834年に[[ライン・フリードリヒ・ヴィルヘルム大学ボン|ボン大学]]に入学し法律や経済学を専攻したものの<ref name="math"/> 、真の関心は数学にあり<ref name="math"/>、[[ビール]]と決闘に熱中して4年間で一つも単位を取らなかった。その後、1839年に[[ヴェストファーレン・ヴィルヘルム大学|ミュンスター大学]]の[[教職課程]]に入り、クリストフ・グーデルマンに出会い、楕円関数論への関心を持つようになった<ref name="math"/>。卒業後、26歳で教員として田舎の高校に就職する<ref name="math"/>。教員としての仕事([[数学]]に[[国語]]に[[地理]]、そして[[体操]]まで教えた)をしながら、[[ニールス・アーベル]]の定理と[[カール・グスタフ・ヤコブ・ヤコビ]]の二重周期関数の研究の統合を目指した。<br />
<br />
1854年、[[クレレ誌]]にヤコビ逆問題に関する論文を掲載され<ref name="math"/>、1856年ベルリン大学に招聘される。1864年に正教授に就任<ref name="math"/>、最後までこの地位にあった<ref name="math"/>。晩年は数学界の権威として尊敬され、ベルリン大学でも多くの聴衆を集めた<ref name="math"/>。<br />
<br />
== 業績 ==<br />
初期の業績は超[[楕円積分]]の研究で、これがきっかけで[[フンボルト大学ベルリン|ベルリン大学]]に招聘された。[[楕円関数]]論では、位数2の楕円関数である<math>\wp</math>関数の研究を行い、[[複素解析]]では、[[解析接続]]に基づいた厳密な方法を発展させた。その他、[[イプシロン-デルタ論法]]、[[一様収束]]の概念の考案など、[[微分積分学]]の基礎付けや、一変数複素関数、代数関数のべき級数による理論の整備に業績を残した。とくに[[ベルンハルト・リーマン|リーマン]]とともに複素解析の研究を進めたのは有名であり<ref name="math" />、リーマンが直感的方法を好んだのに対してワイエルシュトラスは厳密な解析的手法を好んだとされる<ref name="math" />。いたるところ微分不能な連続関数の具体例を示し、[[実解析]]においてもその名を轟かし<ref name="math" />、[[極小曲面]]の理論で[[幾何学]]にも業績がある<ref name="math"/>。<br />
<br />
弟子には、[[ミッタク=レフラー]]、[[ソフィア・コワレフスカヤ]]がいる。<br />
<br />
== 参考文献 ==<br />
{{reflist}}<br />
<br />
== 関連記事 ==<br />
* [[ヴァイエルシュトラスの楕円函数]]<br />
* [[カゾラーティ・ワイエルシュトラスの定理]]:真性特異点の近傍の像は稠密である<br />
* [[楕円関数#ワイエルシュトラスの楕円関数|ワイエルシュトラスのペー関数]]:古典的な楕円関数<br />
* [[ボルツァーノ=ワイエルシュトラスの定理]]:有界な無限集合は集積点を持つ<br />
* [[リンデマンの定理|リンデマン=ワイエルシュトラスの定理]]:[[円周率]]や[[ネイピア数]]などの数が超越数であることを示す<br />
* [[ワイエルシュトラス関数]]<br />
<br />
{{Normdaten}}<br />
<br />
{{DEFAULTSORT:わいえるしゆとらす かある ておとる ういるへるむ}}<br />
[[Category:19世紀の数学者|151031]]<br />
[[Category:ドイツの数学者]]<br />
[[Category:コプリ・メダル受賞者]]<br />
[[Category:王立協会外国人会員]]<br />
[[Category:フンボルト大学ベルリンの教員]]<br />
[[Category:1815年生]]<br />
[[Category:1897年没]]<br />
[[Category:数学に関する記事]]</div>
123.176.148.176
INTERCAL
2016-12-01T12:59:50Z
<p>123.176.148.176: en:Don Woodsとen:Donald Woodsは別人です</p>
<hr />
<div>'''INTERCAL'''はプログラム言語。それ自身が[[プログラミング言語]]の[[パロディ]]にもなっており、実用言語ではない。いわゆる[[難解プログラミング言語]]の典型例として知られている。<br />
<br />
INTERCALは、[[FORTRAN]]や[[COBOL]]はもちろん、[[1960年代]]に提案された数々のプログラミング言語の構造や表記法も皮肉の対象としている。そのため、[[C言語|C]]や[[Java]]に慣れ親しんだ今日の観点からすると、そのユーモアは少々時代遅れに感じられる部分もある。<br />
<br />
== 概要 ==<br />
INTERCALは[[1972年]]、[[プリンストン大学]]の学生であった[[ドン・ウッズ]]と[[ジェイムズ・リヨン]]によって作成された<ref name="original-manual">[http://www.muppetlabs.com/~breadbox/intercal/intercal.txt The Original INTERCAL Manual]</ref>。現行バージョンであるC-INTERCALは、[[エリック・レイモンド]]によって保守されている<ref name="resources-page">[http://www.muppetlabs.com/~breadbox/intercal/ INTERCAL Resources on the Web]</ref>。INTERCALという名前は、製作者らによれば "Compiler Language With No Pronounceable Acronym" (発音できる[[頭字語]]のないコンパイラ言語)からつけられたものだという。<br />
<br />
INTERCALは意図的に、他のあらゆる主だったコンピュータ言語とは異なるように設計されている<ref name="original-manual" />。他のプログラム言語におけるごく普通の処理も、INTERCALでは不可解で無駄の多い文法で表現される。例として、INTERCALのリファレンスマニュアルの一部を以下に示す。<br />
<br />
{{quotation|理解しがたい仕事をやっている人は高く評価される。この事実はよく知られており、現実においてもしばしば実証されている。例えば誰かが「INTERCALで32ビットの変数に65536を代入する最も簡単な方法は<br />
<br />
<pre>DO :1 <- #0¢#256</pre><br />
<br />
である」と言ったとしよう。常識的プログラマであれば、こんな書き方は馬鹿げている、と言うだろう。しかし実際にはこの方法が最も簡単な方法であるため、たまたまそこを通った上司には(上司というのはそういうものである)、そのプログラマが馬鹿のように見えることになる。実際にはなにも間違っていないプログラマには、極めて悲劇的なことである。}}<br />
<br />
INTERCALのマニュアルにはこの他にも、逆説的で馬鹿げた、あるいはユーモラスな説明が数多く書かれている。<br />
<br />
{{quotation|注意! メッシュ(INTERCALのマニュアルでの「#」の呼び方)とインターリーブ演算子を決して間違えないようにしてください! ただし、間違ってしまうような状況にある場合はその限りではありません。}}<br />
<br />
INTERCALにはこの他にも、プログラマ的美的感覚とは決して相容れない数々の特徴がある。例えば、ステートメントに"READ OUT"、"IGNORE"、"FORGET"、"PLEASE"といったキーワードが用いられている。マニュアルでは、アルファベット以外の[[ASCII]]文字が独特の名称で呼ばれている。例えば、シングルクォート(')とダブルクォート(")はそれぞれ「火花(sparks)」「ウサギの耳(rabbit ears)」、等価記号(=)は「半メッシュ(half mesh)」といった具合である。他のプログラム言語では代入に等価記号が使用されるが、INTERCALでは"<-"を用いる。この記号はそれぞれ「アングル(angle)」と「ワーム(worm)」と呼ばれている。<br />
<br />
オリジナルのプリンストン大学版では[[パンチカード]]と[[EBCDIC]]の文字セットが使用されていた。そのため、ASCIIのコード体系を採用しているコンピュータ上でINTERCALを実行する場合、2種類の文字を別の文字に置き換える必要がある。ミングル演算子は"ハードウェアに対応して増加するソフトウェアのコストを表現する"「¢」の代わりに「$」を、単項排他的論理和演算子として"[[排他的論理和]](XOR)を初めて目にした人々の平均的反応を正確に表現した"「∀」の代わりに「?」を用いる。<br />
<br />
[[ネットニュース|Usenet]]のニューズグループ alt.lang.intercal は、INTERCALやその他の難解プログラム言語の研究と鑑賞のために作られたものである。<br />
<br />
意図的に鈍重かつ冗漫な言語であるべく作成されたにもかかわらず、INTERCALは[[チューリング完全]]である。つまり、十分なメモリさえあれば、万能[[チューリングマシン]]が計算可能なあらゆる問題を処理することができる。ただし、実行速度はきわめて遅い。ベンチマークとして[[サン・マイクロシステムズ|SUN]] SPARCStation-1上で[[エラトステネスの篩]]を実行したところ、65536以下の素数を全て計算するのにかかった時間は、Cでは0.5秒以下であるが、INTERCALでは17時間以上であった<ref name="stross-1992">[http://www.catb.org/~esr/intercal/stross.html INTERCAL — the Language from Hell] (チャールズ・ストロス、''Computer Shopper'' [UK], 1992年9月)</ref>。<br />
<br />
[[IOCCC|International Obfuscated C Code Contest]](国際醜いCプログラムコンテストの意)のようなコンテストを見てもわかるとおり、INTERCAL以外の言語であってもINTERCALと同等あるいはそれ以上の理解しづらいプログラムを書くことは可能である。しかし、これらの読みにくいコードは、通常なんらかの意図を持って記述されたものである。これに対して、INTERCALの読みにくさは言語仕様によるものである。<br />
<br />
INTERCALのマニュアルには「INTERCALの設計上の目標は、前例のないものを作ることだ」と記載されている。これはおそらく制御構造とデータの操作演算子の両方を対象にしていると思われるが、確かに設計者は部分的にこの試みに成功している。唯一知られている例外は[[1967年]]にリリースされたソビエトのメインフレーム[[BESM-6]]のある命令で、これは事実上INTERCALのセレクト演算子とほぼ同様である。<br />
<br />
後発の言語には一部にINTERCALと同様の設計が見られるものもある。たとえば代入記号では、[[1988年]]に誕生した[[S言語]]でも <- を用いている。([[論理学]]で代入や定義を表す記号 ← を模したものであるので、代入に等号を用いるより自然と考える立場もある。)なお、代入に = を使うことには問題がある、という意見はFORTRANの昔からあり := などを使う言語も少なくない(C言語では、設計者らの簡単な調査によればコード中には代入のほうが比較より多く現れるので、代入のほうを短い = にしたという話がある)。一部の言語では ∈ の代用として <- を使う。<br />
<br />
== バリエーション ==<br />
ウッズとリヨンによる最初のINTERCALは、[[入出力]]の能力が極めて制限されていた。入力できるデータは桁が指定された数字のみ、出力は拡張された[[ローマ数字]]のみであった。<br />
<br />
インターネット上で利用可能な再実装版のC-INTERCALは、より一般的な仕様となっている。これは難解プログラミング言語の愛好家達によるものである。C-INTERCALにはオリジナル版からの何点かの変更と、新しく導入されたいくつかの機能が存在する。[[COME FROM]]ステートメント<ref>発想の元は{{doi|10.1145/358027.358043}}の提案(このdoiは再録版のもので、初出はデータメーション誌([[:en:Datamation]])1973年12月号)である。</ref>やチューリング・テキスト・モデルによるテキストの入出力機能がその例である。<br />
<br />
C-INTERCALの作者はまた、TriINTERCALというバリアントも作成した<ref name="tri-internal">[http://groups.google.co.uk/group/alt.lang.intercal/msg/a1b9db14c09bdbdf Wimps don't read this message (long) -- alt.lang.intercal]</ref>。これは[[3進記数法|3進数]]によるシステムで、演算子が一般化されている。<br />
更に新しいバリアントとしてThreaded Intercalがある<ref name="threaded-intercal">[http://www.cse.unsw.edu.au/~malcolmr/intercal/threaded.html Threaded Intercal]</ref>。このバリアントでは[[マルチスレッド]]をサポートするために、"COME FROM"ステートメントの機能が拡張されている。<br />
<br />
== Hello, world ==<br />
伝統的な[[Hello world]]プログラムを使い、INTERCALが通常の言語とどれだけ異なっているかを示す。Cでは、以下のように記述される。<br />
<br />
<source lang="c"> <br />
#include <stdio.h><br />
int main(void) {<br />
printf("hello, world\n");<br />
return 0;<br />
}<br />
</source><br />
<br />
C-INTERCALでは以下のようになる。コードはより長く、かつ読みにくいものになっている。<br />
<br />
<pre><br />
DO ,1 <- #13<br />
PLEASE DO ,1 SUB #1 <- #234<br />
DO ,1 SUB #2 <- #112<br />
DO ,1 SUB #3 <- #112<br />
DO ,1 SUB #4 <- #0<br />
DO ,1 SUB #5 <- #64<br />
DO ,1 SUB #6 <- #194<br />
DO ,1 SUB #7 <- #48<br />
PLEASE DO ,1 SUB #8 <- #22<br />
DO ,1 SUB #9 <- #248<br />
DO ,1 SUB #10 <- #168<br />
DO ,1 SUB #11 <- #24<br />
DO ,1 SUB #12 <- #16<br />
DO ,1 SUB #13 <- #214<br />
PLEASE READ OUT ,1<br />
PLEASE GIVE UP<br />
</pre><br />
<br />
== 脚注 ==<br />
<references /><br />
<br />
== 外部リンク ==<br />
<br />
*[http://www.catb.org/~esr/intercal/ The INTERCAL Resources Page].<br />
*[http://www.muppetlabs.com/~breadbox/intercal/ INTERCAL Resources on the Web] - いくつかの実装も紹介されている。<br />
*[http://www.progsoc.uts.edu.au/~sbg/intercal/intercal.html INTERCAL reference manual]<br />
*[http://www.progsoc.uts.edu.au/~sbg/intercal/ick.html C-INTERCAL supplemental reference manual]<br />
*[http://www.cse.unsw.edu.au/~malcolmr/intercal/threaded.html Threaded Intercal]<br />
* [http://groups.google.com/group/alt.lang.intercal/ alt.lang.intercal]<br />
----<br />
本記事の英語版の初期のバージョンには、[http://www.catb.org/~esr/jargon/ The Jargon File 4.2.3 Mar 2001]([[ジャーゴンファイル]])の文章が含まれている。<br />
<br />
[[Category:難解プログラミング言語]]<br />
[[Category:プログラミング言語]]</div>
123.176.148.176
合流性
2016-09-24T13:53:12Z
<p>123.176.148.176: /* 合流性の例 */</p>
<hr />
<div>'''合流性'''({{lang-en-short|''confluence''}})は[[項書き換え]]システムなどの特性で、項を複数の方法で書き換え可能な場合に、その複数の方法で書き換えた結果は適切に書き換えてやれば合流するという性質のことである。合流性は''チャーチ・ロッサー性''と呼ばれる特性と等価である。合流性を持つシステムは書き換え規則の適用順序によらない一貫性を持ち、[[遅延評価]]、[[並行計算|並行評価]]、[[部分評価]]などの柔軟な評価方法が可能になる。<br />
<br />
== 合流性の例 ==<br />
一般的な算術の規則は[[項書き換え]]系と見なすことができる。次のような式があるとする。<br />
: {{math|(11 + 9) &times; (2 + 4)}}.<br />
この式を書き換える方法は2種類ある。最初の括弧の中を単純化するか、2番目の括弧の中を単純化するかである。最初の括弧の中を先に項書き換えで単純化すると、次のようになる。<br />
: {{math|1=20 &times; (2 + 4) = 20 &times; 6 = 120}}.<br />
2番目の括弧の中を先に単純化すると、次のようになる。<br />
: {{math|1=(11 + 9) &times; 6 = 20 &times; 6 = 120}}.<br />
算術式は複数の方法で書き換え可能で、どの方法でも最終的な結果[[正規化 (項書き換え)|正規形]]は同じになる。つまり、算術規則からなる[[項書き換え]]系は合流性を持つ。<br />
<br />
これを項書き換えの流れとして表現すると以下のようになる。<br />
<br />
:<math><br />
\begin{array}{|rcccl|}<br />
\hline<br />
\color{MidnightBlue}{\mbox{eval left}}&&(11+9)\times(2+4)&&\color{MidnightBlue}{\mbox{eval right}}\\<br />
&\color{MidnightBlue}{\swarrow}&&\color{MidnightBlue}{\searrow}&\\<br />
20\times(2+4)&&&&(11+9)\times 6\\<br />
&\color{MidnightBlue}{\searrow}&&\color{MidnightBlue}{\swarrow}&\\<br />
\color{MidnightBlue}{\mbox{eval right}}&&20 \times 6&&\color{MidnightBlue}{\mbox{eval left}}\\<br />
&&\color{MidnightBlue}{\downarrow}&&\\<br />
&&120&&\\<br />
\hline<br />
\end{array}<br />
</math><br />
<br />
== 定義 ==<br />
[[Image:Confluence.svg|thumb|right|図1: 合流性の定義]]<br />
<br />
一般的な[[項書き換え]]システムを考えると、特定の項を書き換え可能な規則や書き換え可能な部分が複数あるため、書き換えの流れは1通りとは限らない。合流性とは、同じ項から始まる相異なるかも知れない書き換えの流れから二つの項を取り出した時、常に両項を同じ形に書き換えることが可能である事、即ち任意の項 ''a'' を簡約化していって項 ''b'', ''c'' を得たならば、必ず ''b'', ''c'' から合流できる項 ''d'' が存在することである。<br />
<br />
より形式的には、抽象書換え系 <math>\left\langle A, \to \right\rangle</math> について、''a'' から ''b'' への簡約化 {{lang|en|(reduction)}} を {{math|''a'' &rarr; ''b''}}、簡約化の有限のステップを <math>a \overset{*}{{}\to{}} b</math> と表現した場合、合流性の定義は以下のようになる。<br />
:<math>\forall a,b,c\in A,\,\exists d\in A,\,a\overset{*}{{}\to{}}b \quad\text{and}\quad a\overset{*}{{}\to{}}c </math><br />
::<math>\implies b\overset{*}{{}\to{}}d \quad\text{and}\quad c\overset{*}{{}\to{}}d </math><br />
<br />
これを図で表現したものが図1である。実線は[[全称記号]]、点線は[[存在記号]]を意味し、* は簡約化の有限のステップを表す。<br />
<br />
書き換え系が合流性を満たすとき、以下が成り立つ。<br />
* 項 ''a'' の正規形は高々1個しか存在しない。<br />
* 等式 {{math|1=''a'' = ''b''}} が成立するならば、適当な項 ''c'' が存在して <math>a \overset{*}{{}\to{}} c</math> かつ <math>b \overset{*}{{}\to{}} c</math> である。<br />
なお、正規形が高々一個である事を指して「書き換え順序によらず、結果が一意に定まる」と言われることがあるが、そもそも正規形に辿り着くことが可能かどうか(つまりその順序での書き換えの「結果」と呼べるものが存在するかどうか)は書き換え順序によって変化する事があるため、厳密にはミスリーディングである。常に一意な結果があると言うには「結果」の定義に加え[[正規化 (項書き換え)|強正規化性]]等の性質が追加で必要になる。<br />
<br />
== 関連する他の性質 ==<br />
[[Image:Local-confluence.svg|thumb|right|図2: 局所合流性の定義]]<br />
[[Image:Semi-confluence.svg|thumb|right|図3: 準合流性の定義]]<br />
[[Image:Strong-confluence.svg|thumb|right|図4: 強合流性の定義]]<br />
<br />
合流性に関連した性質として、局所合流性、準合流性、強合流性、チャーチ・ロッサー性などがある。<br />
<br />
=== チャーチ・ロッサー性 ===<br />
'''チャーチ・ロッサー性'''({{lang|en|''Church-Rosser property''}})とは、抽象書き換え系 <math>\left\langle A, \to \right\rangle</math> の任意の <math>a,\,b \in\,A</math> について <math>a \overset{*}{{}\leftrightarrow{}} b</math> ならば <math>a\,\overset{*}{{}\to{}}c \quad\text{and}\quad b\,\overset{*}{{}\to{}}c </math> となるような ''c'' が存在することである。ここで <math>a \overset{*}{{}\leftrightarrow{}} b</math> は ''a'' と ''b'' それぞれの方向に有限ステップで簡約できることを表す。<br />
<br />
チャーチ・ロッサー性は合流性と等価である。チャーチ・ロッサー性は[[ラムダ計算]]でのベータ簡約の合流性を示す[[チャーチ・ロッサーの定理]]で用いられた。<br />
=== 局所合流性 ===<br />
要素 {{math|''a'' &isin; ''A''}} が '''局所合流性'''({{lang|en|''Local confluence''}})を持つとは、<math>c\,\leftarrow\,a\,\rightarrow\,b</math> となる任意の {{math|''b'', ''c'' &isin; ''A''}} について <math>c\,\overset{*}{{}\to{}}d\,\overset{*}{{}\leftarrow{}}b </math> となるような ''d'' が存在することである。これを図で表現したものが図2である。<br />
<br />
局所合流性は、''弱合流性''({{lang|en|''Weak confluence''}})あるいは''弱チャーチ・ロッサー性''({{lang|en|''Weak Church-Rosser property''}})と呼ばれることもある。<br />
<br />
局所合流性は合流性より弱い性質で、全ての要素が局所合流性を持つ場合でも、例えば書き換え規則にループが含まれる場合など、システム全体の合流性が成立するとは限らない。<br />
<br />
ただし、システムが停止性と局所合流性とを持つ場合、システムは合流性を持つ(''ニューマンの補助定理''、{{lang|en|Newman's lemma}})。<br />
=== 準合流性 ===<br />
要素 {{math|''a'' &isin; ''A''}} が '''準合流性'''({{lang|en|''Semi-confluence''}})を持つとは、<math>c\,\leftarrow\,a\,\overset{*}\rightarrow\,b</math> となる任意の {{math|''b'', ''c'' &isin; ''A''}} について <math>c\,\overset{*}{{}\to{}}d\,\overset{*}{{}\leftarrow{}}b </math> となるような ''d'' が存在することである。これを図で表現したものが図3である。<br />
<br />
全ての要素が準合流性を持つならば、システムは合流性を持つ。<br />
=== 強合流性 ===<br />
'''強合流性'''({{lang|en|''Strong confluence''}})は局所合流性を強くした性質である。要素 {{math|''a'' &isin; ''A''}} が強合流性を持つとは、<math>c\,\leftarrow\,a\,\rightarrow\,b</math> となる任意の {{math|''b'', ''c'' &isin; ''A''}} について <math>c\,\overset{=}{{}\to{}}d\,\overset{*}{{}\leftarrow{}}b </math> となるような ''d'' が存在することである。ここで <math>c\,\overset{=}{{}\to{}}d</math> とは、 <math>c\,{{}\to{}}d</math> か <math>c\,= d</math> のいずれかが成立することを表す。これを図で表現したものが図4である。<br />
<br />
全ての要素が強合流性を持つならば、システムは合流性を持つ。強合流性は以下の定理と共に用いることができる:<br />
抽象書換え系 <math>\left\langle A, \to_1 \right\rangle</math>, <math>\left\langle A, \to_2 \right\rangle</math> で <math>\rightarrow _1\,\subseteq\, \rightarrow _2\, \subseteq\, \overset{*} \to _1</math> かつ <math>(A,\rightarrow _2)</math> が強合流性を持つならば、<math>(A,\rightarrow _1)</math> は合流性を持つ。<br />
<br />
== 関連項目 ==<br />
* [[項書き換え]]<br />
* [[ラムダ計算]]<br />
* [[グレブナー基底]]<br />
* [[クヌース・ベンディックス完備化アルゴリズム]]<br />
<br />
== 参考文献 ==<br />
* Bezem, M. et al (ed). ''Term Rewriting Systems''. Cambridge Tracts in Theoretical Computer Science, 2003. ISBN 9780521391153<br />
* Franz Baader and Tobias Nipkow. [http://www.forsoft.de/~nipkow/TRaAT/ ''Term Rewriting and All That'']. Cambridge University Press, 1998. ISBN 978-0521779203 <br />
* 外山芳人. [http://www.nue.riec.tohoku.ac.jp/lab-intro/TRS-intro/98ss_intro_trs.pdf ''項書き換えシステム入門''].(pdf) 信学技報, SS98-15, pp.31-38, 1998.<br />
<br />
== 外部リンク ==<br />
* {{MathWorld | urlname=Confluent | title=Confluent}}<br />
* [http://www.nue.riec.tohoku.ac.jp/lab-intro/TRS-intro/index.html ''項書き換えシステム入門'']. 東北大学 電気通信研究所<br />
<br />
{{DEFAULTSORT:こうりゅうせい}}<br />
<br />
[[Category:形式言語]]<br />
[[Category:形式手法]]<br />
[[Category:数理論理学]]<br />
[[Category:計算理論]]<br />
[[Category:数学に関する記事]]</div>
123.176.148.176
Warning : Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46