アナトール・スリセンコ
アナトール・スリセンコ (スリセンコ) (ロシア語: Анатоль Олесьевич Слисенко)
生まれる（1941年8月15日）1941年8月15日
ソビエト連邦
母校サンクトペテルブルク国立大学
科学者としてのキャリア
フィールドコンピュータサイエンス数学
機関ステクロフ数学研究所、サンクトペテルブルク国立大学、レニングラード、ソ連科学アカデミー情報科学・オートメーション研究所、パリ東クレテイユ、ヴァル＝ド＝マルヌ大学、レニングラード工科大学
博士課程の指導教員ニコライ・アレクサンドロヴィッチ・シャニン
博士課程の学生ドミトリー・グリゴリエフ

アナトール・スリセンコ（旧音訳：Slisenko、ロシア語：Анатоль Олесьевич Слисенко）は、ソビエト連邦、ロシア、フランスの数学者、コンピュータ科学者であり、1941年8月15日にシベリアで生まれた。彼の父[ 1 ]はシベリアで軍事地形学連隊の指揮官を務めていた。1950年に両親はレニングラードに移住した。

研究

出典: [ 2 ]

1958年、AOスリセンコはレニングラード（現サンクトペテルブルク）国立大学数学・力学学部に入学した。[ 3 ]そこでニコライ・シャニン の指導の下、 構成的数学（再帰解析）[4] の研究を開始した。 [ 5 ] 1963年に大学を卒業した後、ソ連科学アカデミー・ステクロフ数学研究所（現在は若干名称が異なる）のレニングラード部門の研究員となった。[ 6 ] 1967年に構成的数学の博士論文を発表し、指導教官はニコライ・シャニンであった。1981年にモスクワのステクロフ数学研究所で理学博士論文を発表した。

1963年から1966年にかけて彼は構成的数学の研究を続け、同時に古典的な命題論理における自動定理証明のためのシャニンのアルゴリズムの開発と実装に参加した。[ 7 ]

それから彼は徐々にアルゴリズムと計算複雑性の研究を始めました。

論文[ 8 ]では、個々の問題の「計算」複雑さをどのように定義するかについて議論しており、このトピックはその後のエントロピー収束に関する論文に影響を与えた。

[ 9 ]において、彼は多ヘッド・チューリングマシンによる回文認識問題に予想外の解決策を提示した。すなわち、1本のテープを持つ6ヘッド・チューリングマシンが回文をリアルタイムで認識できることを証明したのである。当時、これは不可能だと広く予想されていた。彼の非常に長い証明は、後に ツヴィ・ガリルによって簡略化された。ガリルは、 [ 9 ]執筆時には知られていなかったいくつかの新しい結果を用いた（ [ 10 ]も参照）。

Slissenko のもう一つの主要な成果は、様々な文字列照合問題 (コンパクトな形式ですべての周期性を見つけることも含む) を解くリアルタイムアルゴリズムであった。[ 11 ]このアルゴリズムは、長さが時間計算量の対数で制限されるレジスタを持つランダムアクセスマシンである LRAM (アドレスマシン) として形式化することができ、[ 12 ]で導入され、 [ 13 ] でも説明されている。[ 11 ]このモデルでは、長さの制限がなければ非現実的に高速なアルゴリズムを生み出す可能性のある乗算を含むさまざまな演算を使用することができる。その上、LRAM は非常に密な時間計算量の階層を持っている。

1981年から1992年にかけて、スリセンコはロシア科学アカデミーのサンクトペテルブルク情報科学・自動化研究所の研究室長を務めた。[ 14 ]彼はそこで応用研究に取り組んだが、当時はソビエト連邦が苦悩していた時期であり、この分野では注目すべき論文は発表されていなかった。

[ 15 ]において彼はグラフ文法のクラス（[ 16 ]ではスリセンコ（Slissenko）文法と呼ばれる）を導入した。この文法は、ハミルトン閉路の存在を多項式時間で判定できるグラフを生成する。これらの文法によって生成されるグラフは、木幅が制限されている。

論文[ 17 ]は彼が推論システムの品質を評価するためにエントロピーを導入した最初の論文であった。

1993年から2009年まで、パリ東クレテイユ大学[ 18 ]（UPEC：Université Paris-Est-Créteil、旧称パリ第12大学）理工学部情報科学科の教授を務めた。マルコフ決定過程の複雑性[ 19 ] 、半代数的障害やその他の障害物の中で最短経路を構築するアルゴリズム、および時間制限システムの検証に関する研究を行った。

論文[ 20 ]では、3次元空間で斜めの直線に接する最短経路を構築し、既知の未解決問題を解決する多時間アルゴリズムについて説明しています。

確率演算子を用いたかなり強力なロジックのモデル検査アルゴリズムが開発された。[ 21 ]これはこの種のロジックの最初の成果であった。

時間モデルに関する検証の様々なトピックが研究された。[ 22 ]では、ハードリアルタイムシステムの仕様記述のための強力な論理であるFOTL（First Order Timed Logic）が導入され、決定可能クラスが提示された。より一般的な決定可能クラスは[ 23 ]で研究された。

アルゴリズムのエントロピー収束は[ 24 ]で導入され、知識ベースの評価に適用されました。[ 25 ]

[ 26 ]では、P≠NP問題をわずかに再定式化することで、実用上は興味深いまま、算術から独立しているためP≠NPであることがわかる、と彼は指摘した。

スリセンコは多くの会議、特に1983年にポーランドのワルシャワで開催された国際数学者会議に招待講演した。 [ 27 ]

彼はニコライ・シャニン、S.マスロフ、G.ミンツ、V.オレフコフ[ 28 ]と自動定理証明について共同研究を行い、D.ボーキエ、ディマ・グリゴリエフ、D.ブラーゴ、A.ラビノビッチ[ 29 ]らとはアルゴリズムに関する様々なテーマで共同研究を行った。[ 30 ] [ 31 ]

教育と組織活動

アオスリセンコは1981年から1987年までレニングラード工科大学[ 32 ]の非常勤教授を務め、1988年から1992年にはレニングラード国立大学[ 3 ]の数学・力学学部の非常勤教授で、自身が創設を主導したコンピュータサイエンス学科の学科長を務めた（この学科の学生チームはACM国際大学対抗プログラミングコンテストで4回世界チャンピオンになった）。1993年から2009年までパリ東クレテイユ大学[ 18 ]の理工学部情報科学科の教授を務めた。2009年以降は同大学の名誉教授である。

彼はまた、1997 年から 2007 年までアルゴリズム複雑性および論理研究所 (LACL) の所長 (ある意味では創設者) を務めていました。これらすべての役職において、彼はカリキュラムと研究の近代化に貢献しました。

1967年、スリセンコはグリゴリー・ツェイチン（1936–2022）およびロバート・I・フリードソン（1942–2018）とともに、 計算複雑性に関するレニングラード・セミナー[ 26 ]を組織しました。このセミナーは当初レニングラード国立大学で開催され、その後ステクロフ数学研究所レニングラード部門で開催されました（当時、スリセンコが正式な責任者に就任しました）。このセミナーはソ連におけるこの分野の発展に重要な役割を果たしました。このセミナーは1992年まで活動しましたが、ソ連（およびその研究システム）の崩壊後、参加者の大部分はソ連を離れ、米国、フランス、英国で仕事を見つけました。

ソ連のコンピュータ科学に関する歴史的情報は、 [ 26 ] [ 33 ]に記載されており、いくつかのコメントは[ 34 ]に記載されています。

参考文献

  1. ^ Oles' Vasilyevitch Slissenko. In : EIDolgov, SVSergeyev. 赤軍軍事地形図作成者. ロシア連邦軍地形図サービス. モスクワ 2005年, 487-489ページ (ロシア語). http://militera.org/books/pdf/enc/dolgov_sergeev01.pdf
  2. ^ボーキエ、D.;グリゴリエフ、D.マティアセビッチ、ユウ。 （2003年）。 「AOスリセンコの伝記」。理論的なコンピューターサイエンス。303 : 3-5 .
  3. ^ a b「サンクトペテルブルク国立大学数学・力学学部」math.spbu.ru。
  4. ^ A. スリセンコ (Slissenko). 双対行列上の算術演算に関するアルゴリズム上の問題について. ソビエト数学ドクラディ, 152(2), 1963. ロシア語原文: ソビエト数学アカデミー紀要SSSR, 152(2):292–295, 1963.
  5. ^ブリッジズ、ダグラス; パルムグレン、エリック; 石原一 (2022年3月12日). ザルタ、エドワード・N.; ノーデルマン、ウリ (編).スタンフォード哲学百科事典. スタンフォード大学形而上学研究室 – スタンフォード哲学百科事典経由.
  6. ^「研究所の歴史 | ロシア科学アカデミー・ステクロフ数学研究所サンクトペテルブルク部門」www.pdmi.ras.ru。
  7. ^ N. Shanin, G. Davydov, S. Maslov, G. Mints, V. Orevkov, A. Slissenko (Slissenko). 命題論理における自然論理演繹の機械探索アルゴリズム．J. Siekmann, G. Wrightson編著，*The Automation of Reasoning I: Classical Papers on Computational Logic 1957–1966*，424–483ページ．Springer-Verlag, 1983（ロシア語原著はNauka, Leningrad, 1965, 39ページ）．
  8. ^ A. スリセンコ。定理証明アルゴリズムの最適化の問題に対する有限アプローチ。 J. of ソビエト数学、10(4):597–603、1978。ロシア語の原文: Zapiski Nauchnykh Seminorov LOMI、49:123-130、1975。
  9. ^ a b A. Slisenko. 入力付きマルチヘッドチューリングマシンによる対称述語の認識. Proc. Steklov Inst. of Mathematics, 129:25–208, 1976. ロシア語原文：Trudy Matematicheskogo Instituta Akademii Nauk SSSR, 129:30–202, 1973.
  10. ^ A. Slisenko. チューリングマシンにおける回文のリアルタイム認識可能性の簡略化された証明. J. of Soviet Mathematics, 15(1):68–77, 1981. ロシア語原文：Zapiski Nauchnykh Seminarov LOMI, 68:123–139, 1977.
  11. ^ a b A. Slissenko. 周期性の検出とリアルタイム文字列マッチング. J. of Soviet Mathematics, 22(3):1316–1386, 1983. ロシア語原文: Zapiski Nauchnykh SeminarovnLOMI, 105:62–173, 1981.
  12. ^ A. Slissenko. ストレージのアドレス構成に基づく計算モデル. ソビエト数学研究におけるAIと自動化に関するシンポジウム議事録, キエフ, 94–96ページ. サイバネティクス研究所, キエフ, 1978年 (ロシア語).
  13. ^ A. Slissenko. 計算理論の計算量問題. ロシア数学概論, 36(6):23–125, 1981. ロシア語原文: Uspekhi Matem. Nauk, 36(2):21–103, 1981.
  14. ^ “メイン - SPIRAS” . www.spiiras.nw.ru。
  15. ^ Slisenko, A. (1982). 「困難な問題の多項式時間サブクラスを記述するためのツールとしての文脈自由文法」.情報処理レター. 14 (2): 52– 56. doi : 10.1016/0020-0190(82)90086-2 .
  16. ^ A. Habel, Hyperedge replacement: grammars and languages, Lecture Notes in Computer Science, Vol. 643, Springer, Berlin, 1992
  17. ^ Slissenko, A. (1991). 「知識処理システムの情報品質の尺度について」.情報科学. 57– 58: 389– 402. doi : 10.1016/0020-0255(91)90089-D .
  18. ^ a b「UPEC 」。UPEC 。
  19. ^ Burago, D.; de Rougemont, M.; Slissenko, A. (1996). 「部分観測マルコフ決定過程の複雑性について」 . Theoret. Comput. Sci . 157 (1): 161– 183. doi : 10.1016/0304-3975(95)00158-1 .
  20. ^ Burago, D.; Grigoriev, D.; Slissenko, A. (2004). 「斜線問題の最短経路を1/イプシロンの二重対数時間で近似する」.理論計算機科学. 315 ( 2–3 ): 371–404 .
  21. ^ Beauquier, D.; Rabinovich, A.; Slissenko, A. (2006). 「決定可能なモデル検査を備えた確率論理」. Journal of Logic and Computation . 16 (4): 461– 487.
  22. ^ Beauquier, D.; Slissenko, A. (2002). 「時間付きアルゴリズムの仕様記述のための第一階述語論理：基本的性質と決定可能クラス」Annals of Pure and Applied Logic . 113 ( 1–3 ): 13– 52.
  23. ^ Beauquier, D.; Slissenko, A. (2006). 「第一階タイムドロジックにおける周期性に基づく決定可能クラス」Annals of Pure and Applied Logic . 139 ( 1–3 ): 43– 73.
  24. ^ A. Slissenko. アルゴリズムのエントロピー収束について. A. Blass, P. Cgielski, N. Dershowitz, M. Droste, B. Finkbeiner編, Fields of Logic and Computation III. Lecture Notes in Computer Science, vol 12180, 291–304ページ. Springer, Cham, 2020.
  25. ^ A. Slissenko. 情報と知識の関連付け. K. Meer, A. Rabinovich, E. Ravve, A. Villaveces編著『モデル理論、コンピュータサイエンス、グラフ多項式』Trends in Mathematics, 515–523ページ. Birkhäuser Cham, 2025. ISBN978-3-031-86318-9 (ハードカバー), ISBN978-3-031-86319-6 (電子書籍).
  26. ^ a b c A. Slissenko. サンクトペテルブルク/レニングラード（1961-1998）：論理から複雑性へ、そしてさらにその先へ、『理論計算機科学における人々とアイデア』、Springer Verlag、274-313ページ、1998年。ISBN 981-4021-13-X
  27. ^ A. Slissenko. 効果的なアルゴリズムを考案するための言語学的考察. Proc. Intern. Congress of Mathematicians, August 16–24, 1983, Waszawa, 347–357ページ. ICM, Waszawa, 1984.
  28. ^ 「ウラジミール・オレフコフ | ロシア科学アカデミー・ステクロフ数学研究所サンクトペテルブルク部門」www.pdmi.ras.ru。
  29. ^ “アレクサンダー・ラビノビッチ教授” .テルアビブ大学。
  30. ^ "anatol_pub.html " . www.lacl.fr.
  31. ^ “Персоналии: Слисенко Анатоль Олесьевич” . www.mathnet.ru。
  32. ^ 「ピョートル大帝サンクトペテルブルク工科大学」 2025年2月13日 – Wikipediaより。
  33. ^ A. スリセンコ. 旧ソ連における理論計算機科学研究の近年の動向. RAIRO, Technique et science informatique, 12(1):9–​​28, 1993.
  34. ^ A. Slissenko. 計算の情報構造の分析に向けて. The IFCoLog Journal of Logic and its Applications, 4(4):1457–1476, 2017. また、College Publications発行のStudies in Logicシリーズ第70巻、277-299ページにも掲載されている。
「 https://en.wikipedia.org/w/index.php?title=Anatol_Slissenko&oldid=1313482898」から取得