業績リスト
１９９２年８月１４日現在
夜久竹夫
著書 ３（共同執筆）
論文 １５（印刷中のものを含む）
講演論文・技術報告等 ４３
口頭発表 ５１
学位論文
Parallel maps induced by cellular automata （セルオ－トマタ
による並列写像），早稲田大学博士学位論文５８８，１９７７．
I．著書
１．（共同執筆）”理工系の基礎数学”，東海大学出版会，１９７８，
３６１ｐｐ．
２．（共同執筆）”マイクロコンピュ－タハンドブック”，オ－ム社，
１９８５，１０７９ｐｐ．
３．（共同執筆）”構造エデイタ”，共立出版，１９８７，１９８ｐｐ．
II． 論文
１．The constructibility of a configuration in a cellular automaton,
J. Comput. System Sci. 7 (1973), 481 - 496, (MR 48#10724, OLDINSPC
564485).
２．Surjectivity of nondeterministic parallel maps induced by nondeter-
ministic cellular automata, J. Comput. System Sci. 12 (1976), 1
- 5, (MR 54#4671, OLDINSPC 884890)
３．Inverse and injectivity of parallel relation induced by cellular
automata, Proc. Amer. Math. Soc. 58 (1976), 216 - 220,（MR 56#2703).
４．Partition of graphs into chains of minimal block number, Proc. Fac.
Sci. Tokai Univ. 18 (1983), 41 - 44, (MR 85d05128).
５．（二木厚吉氏、足立暁生氏と共著）A control structure between itera-
tion and recursion, Proc.Fac. Sci. Tokai Univ. 18 (1983), 119 - 129,
(ZM #4380-18-119-83).
６．Wiring a Turing machine in the cellular automaton and the sur-
jectivity problem for a parallel map, Proc. Fac. Sci. Tokai Univ.
20 (1985), 51 - 72, (MR 87b68079).
７．（二木厚吉氏他と共著）階層型流れ図言語Ｈｉｃｈａｒｔの情報処理記号、 早稲田大学情報科学研究教育センター紀要 ３（１９８６），９２－１０７．
８．（二木厚吉氏、足立暁生氏と共著）Complexity of substitutive programs,
"Topology and Computer Science" (S. Suzuki Ed.), 451 - 472, Kino-
kuniya, 1987.
９．（二木厚吉氏他と共著）Ｈｉｃｈａｒｔとプログラム開発環境ＥＴＡ＿-
ＡＩＤＥ， ”構造エデイタ”（原田賢一編），１６５－１８２、共立出版、
１９８７．
１０．（二木厚吉氏他と共著）HICHART - A hierarchical flowchart descrip-
tion language-, Proc. IEEE COMPSAC 11 (1987), 157 - 163,
(INSPECC 3096363).
１１．（郷信義氏他と共著）Ｈｉｃｈａｒｔプログラム図式の生成方法、情報処
理学会論文誌３１（１９９０），1463 - 1473．
１２．（共著）プログラム図式を用いたプログラム教育開発環境，
電子情報通信学会論文誌Ｊ７５－Ａ（１９９２年２月），４３１ー４４０， 技術報告２４．
１３．（共著）木構造図式の描画問題，情報処理学会論文誌（１９９２年）．
１４．(with K.Ogura et al), Generation of the Hichart program diagrams,
J. Inform. Process. １５（１９９２）, （印刷中）, 技術報告３６．
１５．（山神憲司氏、植村憲治氏と共著）ある種の非サイクル的有向グラフの
極大パス被覆を与える線形時間アルゴリズム，
電子情報通信学会論文誌ＤＩ（１９９２年），印刷中，技術報告２１．
［投稿中，準備中のもの］
１６．（山神憲司氏、植村憲治氏と共著）有向グラフのパス被覆問題の並行計算
量について，電子情報通信学会論文誌ＤＩに投稿中，技術報告３０．
１７．（共著）再代入プログラムの計算複雑度，
電子情報通信学会論文誌ＤＩに投稿中，技術報告２０．
１８．（共著）有向グラフにおける交互部分グラフとパス被覆問題，
電子情報通信学会論文誌Ａに投稿中，技術報告３１，技術報告３７．
１９．（共著）境界付きＮＬＣグラフ言語に対するポンプの補題，
電子情報通信学会論文誌ＤＩ投稿中，技術報告３４．
２０． Solving path covering problems for the digraphs with
the alternate subgraphs, J. Assoc. Comput. Machin. に投稿中 ，
技術報告３８．
２１．（共著）A Pumping Lemma in the BNLC Graph Grammars,（J. Inform.
Sci. に投稿中），技術報告３５．
２２．A Linear Time Algorithm That Provides a Maximal Path Cover in
the Binary Branch Digraphs, (Inform. Comput.に投稿中）
III．技術報告，講演論文，講究録，解説論文
１．不確定セルオ－トマタに対する並列写像の全射性について， 京都大学数理
解析研究所講究録 １７９（１９７３），１２７－１４０．
２．不確定セルオ－トマタによる不確定並列写像の逆写像と単射性について，
京都大学数理解析研究所講究録 ２１３（１９７４），２２０－２２６．
３．フロ－グラフの分岐数について，京都大学数理解析研究所講究録２５９
（１９７６），１５８－１６４．
４．オ－トマトンとアルゴリズム， Ｃ＆Ａ （Computation and Analysis）
セミナ－会報 １（１９７７）．
５．（二木厚吉氏と共著）フロ－チャ－トの木構造型記法，電子通信学会オ－ト
マトンと言語研究会資料集ＡＬ－７８（１９７８），６１－６６．
６．ある種のグラフの極大マッチングを与える線形時間アルゴリズム，京都大学
数理解析研究所講究録 ３５３（１９７９），６８－７７．
７．（二木厚吉氏と共著）木フロ－チャ－トとその計算図式について，電子通信
学会講演論文集，１９７９．
８．（二木厚吉氏， 足立暁生氏と共著） 木フロ－チャ－トとプログラムテキ
ストの導出木について，情報処理学会第２０回全国大会講演論文集１９７９，
２８１－２８２．
９．（二木厚吉氏，足立暁生氏と共著） 流れ木による手続きとデ－タ型の記述，
情報処理学会ソフトウェア工学研究会資料集１６ （１９８０），１－１６．
１０．（吉田洋一氏，田中恵子氏と共著），ＬＩＳＰインタ－プリタ，東海大学
電子計算機室広報 ８（１９８０），７－８．
１１．（二木厚吉氏，足立暁生氏と共著）An extended iteration statement
and its computability, 京都大学数理解析研究所講究録 ３８１
（１９８０），１８０－１９４．
１２．（共著）”ＷＥＳＴＲＡＮ使用解説書”，東海大学電子計算センタ－，
１９８０，１６ ｐｐ．
１３．（大沢優氏，高橋英一郎氏と共著） 制限された再帰呼出しの実現，情報
処理学会第２３回全国大会講演論文集 （１９８１）， １６９－１７０．
１４．（上原実氏，吉田希代子氏と共著） 事務計算の流れ木による構造的表現，
情報処理学会第２３回全国大会講演論文集 （１９８１），４０３－４０４．
１５．（久保田美明氏と共著） ＬＩＳＰシステムの作成，東海大学電子計算機
室広報 ９（１９８１），１８－２０．
１６．（郷信義氏，岡田直之氏，長田芳一氏，岸本美紀氏，高橋美智子氏と共著）
木フロ－チャ－ト記述言語ＨＩＣＨＡＲＴの処理系実現について，情報処理
学会講演論文集 （１９８３）．
１７．（二木厚吉氏，足立暁生氏と共著） 階層的フロ－チャ－ト記述言語
ＨＩＣＨＡＲＴによるプログラムの記述，”計算機科学の基礎理論”報告書
（１９８４），４８４－４９４，昭和５８年度文部省科学研究費補助金によ
る研究組織．
１８．（大川知氏と共著）階層的フロ－チャ－ト言語ＨＩＣＨＡＲＴのグラフ文
法上の性質，情報処理学会講演論文集（１９８４）．
１９．（川畑守氏，杉田公生氏，植村憲治氏，郷信義氏と共著）ＨＩＣＨＡＲＴ
を用いた教育用プログラムデ－タベ－スシステムＨ／ＢＡＳＥ，ＣＡＩ学会
第９回研究発表大会論文（１９８４），１４３－１４６．
２０．（共著） Complexity of substitutive programs，京都大学数理解析研究
所講究録 （１９８５）．
２１．（共著) Complexity of path covering problems in acyclic alternate
graphs，（同上，１９８５）．
２２．（共著) Hichart-Pascal トランスレ－タ，情報処理学会第３０回全国大
会講演論文集 ，１９８５．
２３．（共著）Hichart エデイタ，同上 ，１９８５ ．
２４．（共著）ＨＩＣＨＡＲＴを用いた教育用プログラムデ－タベ－スシステム
Ｈ／ＢＡＳＥ ＩＩ，ＣＡＩ学会第１２回研究発表大会論文集 （１９８７），
２５３－２５６．
２５．（共著）ＨＩＣＨＡＲＴを用いたプログラム教育環境，ＣＡＩ学会第１２
回研究発表大会論文集、１９８７．
２６．（共著）ETA87-An extension of the Hichart processing system, 情報
処理学会第３５回全国大会講演論文集（１９８７），１２０１ー１２０２．
２７．代入構造及びその再帰構造と繰り返し構造への関係，（英文：The
complexity of substitutive programs）,
電子情報通信学会コンピュテーション研究会資料 COMP87-80, 1 - 8,
1988.
２８．（共著）Ｈｉｃｈａｒｔ流れ図の描画アルゴリズム、 日本ソフトウェア
科学会第５回大会論文集（１９８８），１８１－１８４．
２９．（共著）木構造図式の美的描画について、京都大学数理解析研究所講究録、 １９８９．
３０．（共著）有向グラフのパスカバー問題の並行計算量について、京都大学数 理解析研究所講究録、１９８９．
３１．（共著）交互部分グラフとパス被覆問題について、電子情報通信学会コン ピュテーション研究会資料ＣＯＭＰ９０（１９９０）．
３２．（共著）Ｈｉｃｈａｒｔを用いた教育用プログラムデータベースシステム
：Ｈ／ＢＡＳＥ（３）、ＣＡＩ学会第１５回研究発表大会論文集（１９９０）
２９２ー２９５．
３３．（共著）グラフ文法とそのＣＡＩシステムへの応用，同上，
１１７ー１２０．
３４．（共著）ＢＮＬＣ言語に対するポンプの補題，電子情報通信学会コン ピュテーション研究会資料ＣＯＭＰ９１（１９９１年２月）．
３５．（共著）境界つきＢＮＬＣグラフ文法に対する標準形，電子情報通信学会
コンピュテーション研究会資料ＣＯＭＰ９１（１９９１年７月）．
３６．(with N.Go et al), Generation of the Hichart program diagrams,
J. Inform. Process., Res. Rep. Dept. Inform. Sci. Tokyo Denki Univ.
TDU-IS-21, 1991.
３７．（共著）Partition of Path Covers of the Digraphs to
the Alternate Subgraphs, Res. Rep. Dept. Inform. Sci. Tokyo Denki
Univ. TDU-IS-22, 1991.
３８．Solving Path Covering Problems for the Digraphs with
the Alternate Subgraphs, Res. Rep. Dept. Inform. Sci. Tokyo Denki
Univ. TDU-IS-23, 1991.
３９．（共著）木構造図式の描画問題，情報処理学会アルゴリズム研究会技術報 告（１９９２）．
４０．（共著）プログラム図式とプログラム仕様書の統合的処理系の研究，東京 電機大学総合研究所年報１１（１９９２），１２３ー１２６．
４１．（共著）プログラムデータベース，私立大学情報処理教育協議会報（１９ ９２）．
４２．（共著）境界付きＮＬＣグラフ文法の生成能力について，言語理論とオー トマトン理論報告（１９９２），予定
４３．（共著）境界付きＮＬＣグラフ言語の標準型，京都大学数理解析研究所講 究録（１９９２）
IV．口頭発表
１．Cellular automataの決定問題について，第２回言語理論とオ－トマトン
理論シンポジウム，１９７２年７月，浜松市．
２．不確定オ－トマタの並列写像に対するエデンの園問題について，京都大学
数理解析研究所研究集会，１９７３年２月，京都市．
３．細胞オ－トマタの並列写像について，セルオ－トマトンシンポジウム，
１９７３年３月，福岡市．
４．細胞オ－トマタの並列写像について，日本数学会年会，１９７３年４月．
５．不確定セルオ－トマタによる並列写像の逆写像と単射性について，京都大学
数理解析研究所研究集会，１９７４年３月，京都市．
６．セルオ－トマトンによる並列写像と単射性について，日本数学会年会，
１９７４年４月，東京都．
７．（岩田茂樹氏と共著）フロ－グラフの生成出樹木の分岐数と対応するフロ－
チャ－トのプログラムについて，日本数学会年会，１９７５年４月，大阪府．
８．フロ－グラフの分岐数とｇｏｔｏ文の数について，京都大学数理解析研究所
研究集会，１９７５年９月，京都市．
９．（門倉敏夫氏，深沢良彰氏，杉田雅彦氏，岩田茂樹氏と共著） ＧＯＴＯ文
最小のプログラムを与えるアルゴリズム，電気学会全国大会，１９７６年．
１０．オ－トマトンとアルゴリズム，Ｃ＆Ａ （Computation and Analysis）
セミナ－年会連続講演，１９７７年７月，富山市．
１１．グラフのマッチングとフロ－グラフの分岐数，日本数学会秋季総合分科会，
１９７８年１０月．
１２．（二木厚吉氏と共著）フロ－チャ－トの木構造型記法，電子通信学会
オ－トマトンと言語研究会，１９７８年１０月，新潟市
１３．ある種のグラフの極大マッチングを与える線形時間アルゴリズム，京都
大学数理解析研究所研究集会，１９７９年２月，京都市．
１４．（二木厚吉氏と共著） 木フロ－チャ－トとその計算図式について，電子
通信学会，１９７９年．
１５．（二木厚吉氏，足立暁生氏と共著） 木フロ－チャ－トとプログラム
テキストの導出木について，情報処理学会第２０回全国大会，１９７９年．
１６．Algorithms on matching of digraphs, A Seminar in "Internat.
Congress Math." １９７８年，Helsinki-Finland.
１７．（二木厚吉氏，足立暁生氏と共著）流れ木による手続きとデ－タ型の記述，
情報処理学会ソフトウェア工学研究会，１９８０年，東京都．
１８．（二木厚吉氏，足立暁生氏と共著) An extended iteration statement
and its computability，京都大学数理解析研究所研究集会，１９８０年，
京都市．
１９．（上原実氏，吉田希代子氏と共著）事務計算の流れ木による構造的表現，
情報処理学会全国大会，１９８１年，東京都．
２０．（大沢優氏，高橋英一郎氏と共著）制限された再帰呼出しの実現， 情報
処理学会全国大会，１９８１年，東京都．
２１．（二木厚吉氏，足立暁生氏と共著） 階層的フロ－チャ－ト記述言語
ＨＩＣＨＡＲＴによるプログラムの記述，第１３回言語理論とオートマトン
シンポジウム，１９８３年８月，仙台市．
２２．（二木厚吉氏，足立暁生氏と共著） SUBSTITUTION: RECURSION と
ITERATION の間の制御構造， 日本数学会，１９８３年１０月，東京都．
２３．（郷信義氏，岡田直之氏，長田芳一氏，岸本美紀氏，高橋美智子氏と共著）
木フロ－チャ－ト記述言語ＨＩＣＨＡＲＴの処理系実現について，情報処理
学会全国大会，１９８３年１０月，名古屋市．
２４．（大川知氏と共著） 階層的フロ－チャ－ト記述言語ＨＩＣＨＡＲＴの
グラフ文法上の性質，情報処理学会全国大会，１９８４年９月，仙台市．
２５．（川畑守氏，杉田公生氏，植村憲治氏，郷信義氏と共著）ＨＩＣＨＡＲＴ
を用いた教育用プログラムデ－タベ－スシステムＨ／ＢＡＳＥ，ＣＡＩ学会
第９回研究発表大会，１９８４年９月，平塚市．
２６．（植村憲治氏と共著）Complexity of maximal path covering problems
for acyclic flowgraphs，日本数学会秋季総合分科会，１９８４年１０月，
東京都．
２７．（二木厚吉，足立暁生氏と共著） Complexity of substitutive programs，
京都大学数理解析研究所研究集会，１９８５年２月，京都市．
２８．（植村憲治氏と共著)Complexity of path covering problems for
acyclic alternate graphs， 同上．
２９．（共著）Hichart Pascal トランスレ－タ， 情報処理学会第３０回全国
大会，１９８５年５月．
３０．（共著）Hichart エデイタ，同上．
３１．（共著）Ｈーコードグラフ文法とＨｉｃｈａｒｔエデイタ， 日本ソフト
ウェア科学会構造エデイタワークショップ，１９８６年５月，相模原市．
３２．（大川知氏他と共著）Ｈｉｃｈａｒｔのグラフ文法，同上．
３３．（共著）Ｈｉｃｈａｒｔの現状，同上．
３４．（二木厚吉，足立暁生氏と共著）Complexity of substitutive programs,
Topology and Computer Science Symposium, 1986 Dec., Atami-Japan.
３５．（共著）ＨＩＣＨＡＲＴを用いた教育用プログラムデ－タベ－スシステム
Ｈ／ＢＡＳＥ （２）， ＣＡＩ学会第１２回研究発表大会，１９８７年．
３６．（共著）ＨＩＣＨＡＲＴを用いたプログラム教育環境、 ＣＡＩ学会
第１２回研究発表大会，１９８７年８月，東京都．
３７．（共著）ETA87-An extension of the Hichart processing system, 情報
処理学会全国大会，１９８７年１０月，札幌市．
３８． The complexity of substitutive programs, 電子情報通信学会
コンピュテーション研究会，１９８８年，平塚市．
３９．（共著）Ｈｉｃｈａｒｔ流れ図の描画アルゴリズム，日本ソフトウェア
科学会第５回大会，１９８８年，東京都．
４０．（共著）木構造図式の美的描画について，京都大学数理解析研究所研究
集会，１９８９年１月，京都市．
４１．（植村憲治氏、山神憲司氏と共著）有向グラフのパスカバー問題の並行計 算量、第１９回言語理論とオートマトンシンポジウム、 １９８９年７月、
新潟県大和町．
４２．（植村憲治氏、山神憲司氏と共著）有向グラフのパス被覆問題の計算量、
日本ソフトウェア科学会、１９８９年１０月、福岡市．
４３．（二木厚吉氏他と共著）交互部分グラフとパス被覆問題について、電子情 報通信学会コンピュテーション研究会，１９９０年７月，調布市．
４４．（二木厚吉氏他と共著）交互部分グラフとパス被覆問題について、第２１ 回言語とオートマトン理論シンポジウム、１９９０年７月、埼玉県秩父郡．
４５．（共著）Ｈｉｃｈａｒｔを用いた教育用プログラムデータベースシステム
：Ｈ／ＢＡＳＥ（３）、ＣＡＩ学会第１５回大会、１９９０年８月、東京都．
４６．（共著）グラフ文法とそのＣＡＩシステムへの応用，同上．
４７．（山崎浩一氏と共著）境界付きＮＬＣグラフ言語の反復補題，京都大学数 理解析研究所共同研究集会，京都市，１９９１年６月．
４８．（山崎浩一氏と共著）境界付きＮＬＣグラフ言語の標準形，京都大学数理 解析研究所研究集会，京都市，１９９２年２月．
４８．（海野浩氏他と共著）木構造図式の描画問題，情報処理学会アルゴリズム
研究会，東京都，１９９２年４月．
４９．（共著）プログラム図式とプログラム仕様書の統合的処理系の研究，東京 電機大学総合研究所研究報告会，１９９２年７月．
５０．（山崎浩一氏と共著）境界付きＮＬＣグラフ文法の生成能力について，
第２２回言語理論とオートマトン理論シンポジウム，滋賀県大津市，
１９９２年７月．
５１．（共著）Ｃ言語対応プログラム図式生成系の研究，日本ソフトウェア
科学会，１９９２年９月．
.
V．論文査読
１．Proc 5th Internat. Conf. Software Engin., 1983.
２．Proc 12th Sympos. Math. Foundation Comput. Sci., 1986.
３．情報処理学会論文誌、１９８６、１９８７、１９８８、１９８９．
他.
V．研究テ－マの説明
専攻分野は計算機数学とソフトウェア工学である．
ネットワ－ク型システムの基礎理論と応用を研究している．
研究分野は
１．オ－トマトン理論（セルオ－トマトン理論）
２．アルゴリズム理論（グラフアルゴリズム理論）
３．ソフトウェア工学（図式型プログラム言語）
４．言語理論（グラフ言語理論）
５．計算理論（プログラム理論）
に分れる．
以下で研究分野別に説明する．
１．セルオ－トマトンマトン理論の研究
（論文）［Ａ－１，Ａ－２，Ａ－３，Ａ－４，Ａ－７，Ｂ－１，
Ｂ－２］
並列写像に関する決定問題を考える事により，１次元セルオ－ト
マトンと２次元セルオ－トマトンとの本質的違いを明らかにした．
２．グラフアルゴリズム理論の研究
（論文）［Ａ－５，Ｂ－３，Ｂ－６］
グラフをpath disjoint な path に分割する問題とその計算量
を研究している（口頭発表２６）． この問題はプログラム，
デ－タ構造，システム一般の分割と表現に関係がある．
３．図式型プログラム言語の研究
（論文）［Ｂ－５，Ｂ－７，Ｂ－８，Ｂ－９，Ｂ－１２，Ｂ－１３］
グラフ型プログラミング言語であるＨＩＣＨＡＲＴ（木フロ－
チャ－ト）を作成，改良している． ＨＩＣＨＡＲＴはフロ－
チャ－ト記述システムでもある． ＨＩＣＨＡＲＴは多くの点
で独創的であり，その命令と構造はその後いくつかのグラフ型
プログラミング言語に採用され大きな影響を与えた． それら
のＨＩＣＨＡＲＴ型のプログラミング言語として ＰＡＤ，
ＦＥＳＤＤ などがる． 現在はＨＩＣＨＡＲＴの処理系を作
成中である．
なおＨＩＣＨＡＲＴはプログラムだけでなくシステム一般を記述
する事を目的としている．
４．グラフ言語理論の研究
（論文）［Ｂ－１７］
ＨＩＣＨＡＲＴを例としてグラフ言語理論を研究している．
ＨＩＣＨＡＲＴはセルオ－トマトンとしては１次元型と２次元型の
中間に位置づけられる．
５．プログラム理論の研究
（論文）［Ａ－６，Ｂ－１０，Ｂ－１１］
プログラムの基本的制御構造である反復と再帰の間に，代入（sub-
stitution） という構造が存在する事を示した． 将来はプログラ
ム分割との関係を研究する予定である．
.
業績92全体
業績92全体