共同研究・競争的資金等の研究課題

2020年4月 - 2023年3月

一般のHilbertの第10問題と計算可能性理論

日本学術振興会  科学研究費助成事業 特別研究員奨励費  特別研究員奨励費

課題番号
20J23039
体系的課題番号
JP20J23039
配分額
(総額)
2,500,000円
(直接経費)
2,500,000円
(間接経費)
0円

令和3年度は前年度に引き続き,より広く「代数学と計算論の関係」という観点から,群の語の問題と形式言語理論の関係について,Muller-Schuppの定理の一般化を目指す方向で研究を進めた.文脈自由言語を含む数多の形式言語クラスのうち,特に群を用いて定義される群オートマトンと呼ばれる概念によって定義される言語クラスに着目した.既存の言語クラスのいくつかは群オートマトンを用いて特徴付けられることが知られているので,これを用いて「群の語の問題が特定の形式言語クラスに属する」という従来のMuller-Schupp型の条件を「群Hの語の問題がGオートマトンで認識される」という条件に一般化した問いを考えた.これにより問題が「1つの群と1つの言語クラスの関係」から「2つ群の間の形式言語理論的な関係」へと帰着され,より代数的な考察を行うことが可能となった.
この問題について,Kambitesによる決定性群オートマトンに関する結果の別証明を与えた.また,群の語の問題のモノイド準同型による逆像が再び群の語の問題となることや,群の語の問題と正規言語の共通部分が群の語の問題になるときの2つの群の関係の完全な特徴付けを得ることができた.この内容は論文にまとめ,論文雑誌に投稿する予定である.

リンク情報
URL
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20J23039/
KAKEN
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20J23039
ID情報
  • 課題番号 : 20J23039
  • 体系的課題番号 : JP20J23039

この研究課題の成果一覧

論文

  1

MISC

  1

講演・口頭発表等

  7