Hilbert's tenth problem and computability theory

令和4年度は前年度に引き続き，より広く「代数学と計算論の相互関係」という観点から，群の語の問題と形式言語理論の関係について研究を進めた．特に「語の問題が文脈自由言語であるような群は実質的自由群である」というMuller-Schupp定理の一般化を目指す方向で研究を進めた．正則言語や文脈自由言語などの基本的な言語クラスを含む形式言語クラスのうち，特に群オートマトンと呼ばれる概念によって定義される言語クラスに着目した.既存の言語クラスのいくつかは群オートマトンを用いて特徴付けられることが知られているので，これを用いて「語の問題が特定の形式言語クラスに属する群はどのようなものか」という従来のMuller-Schupp型の条件を「語の問題がGオートマトンで認識されるような群Hはどのようなものか」という条件に一般化した問いを考えた.これにより問題が「1つの群と1つの言語クラスの関係」から「2つ群の間の形式言語理論的な関係」へと帰着され，より代数的な考察を行うことが可能となった.この問題に関する既知の結果として，特に「群Gが自由アーベル群Z^nのとき，語の問題があるGオートマトンで受理される群Hは実質的自由アーベル群である」というElder-Kambites-Ostheimerの定理が知られていた．令和4年度の研究の成果として，彼らの定理のより単純かつ純粋に組合せ論的な証明を与えることができた．この結果は令和5年6月に行われる国際会議に論文として投稿し受理され，発表予定である．

令和4年度は前年度に引き続き，より広く「代数学と計算論の相互関係」という観点から，群の語の問題と形式言語理論の関係について研究を進めた．特に「語の問題が文脈自由言語であるような群は実質的自由群である」というMuller-Schupp定理の一般化を目指す方向で研究を進めた．正則言語や文脈自由言語などの基本的な言語クラスを含む形式言語クラスのうち，特に群オートマトンと呼ばれる概念によって定義される言語クラスに着目した.既存の言語クラスのいくつかは群オートマトンを用いて特徴付けられることが知られているので，これを用いて「語の問題が特定の形式言語クラスに属する群はどのようなものか」という従来のMuller-Schupp型の条件を「語の問題がGオートマトンで認識されるような群Hはどのようなものか」という条件に一般化した問いを考えた.これにより問題が「1つの群と1つの言語クラスの関係」から「2つ群の間の形式言語理論的な関係」へと帰着され，より代数的な考察を行うことが可能となった.この問題に関する既知の結果として，特に「群Gが自由アーベル群Z^nのとき，語の問題があるGオートマトンで受理される群Hは実質的自由アーベル群である」というElder-Kambites-Ostheimerの定理が知られていた．令和4年度の研究の成果として，彼らの定理のより単純かつ純粋に組合せ論的な証明を与えることができた．この結果は令和5年6月に行われる国際会議に論文として投稿し受理され，発表予定である．