仮想自由群におけるねじれ語方程式と方程式の解【JST・京大機械翻訳】

Diekert Volker; Elder Murray

プレプリント

J-GLOBAL ID：202202200417559292 整理番号：22P0273517

仮想自由群におけるねじれ語方程式と方程式の解【JST・京大機械翻訳】

Solutions to twisted word equations and equations in virtually free groups

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2017年01月12日プレプリントサーバーでの情報更新日： 2022年02月26日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

事実上自由なグループにおける問題解決方程式が,インボリューションを有する自由モノイドに関する規則的制約によって,ねじれた単語方程式を解決する問題に減少できることはよく知られている。本論文では,ねじれ単語方程式の全ての解の集合が,PSPACEにおいて仕様を計算できるEDT0L言語であることを証明する。同じ複雑性境界内で,解集合が空,有限または無限であるかどうかを決定することができた。論文の第2部では,PSPACEにおける結果を適用して,PSPACEにおいて,発電機の自然な集合に関して,標準正規形式で有限に生成された仮想自由群に対して,合理的な制約を持つ方程式の解集合のEDT0L記述を,PSPACEにおいて得た。合理的制約が固定(または「小さい」)有限モノイドに同形写像によって与えられるならば,次に,著者らのアルゴリズムをNSPACE(n ̄2logn)に実装することができ,それは準二次非決定論的空間であった。著者らの結果は,複雑性と表現力の両方に関してLohreyとS’enizerues(ICALP 2006)とDahman and Guirardel(J.of Topology 2010)による研究を一般化した。論文は,どんなコンクリート複雑性限界も与えず,これらの論文における結果は,解のサブセットのために説明され,一方,著者らの結果は,すべての解決策に関するものである。【JST・京大機械翻訳】

, , , , , , , , ,
, , , 【Automatic Indexing@JST】

流体動力学一般

, , ,

前のページに戻る