有界あいまいベクトル付加システムのための言語包含は決定可能である【JST機械翻訳】

Czerwinski Wojciech; Hofman Piotr

プレプリント

J-GLOBAL ID：202202207669263595 整理番号：22P0290645

有界あいまいベクトル付加システムのための言語包含は決定可能である【JST機械翻訳】

Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable

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

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

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

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

受容状態の集合により定義される受容条件を持つ状態を持つベクトル加法システム(VASSe)に対する言語包含および言語等価性の問題を考察した。一般的に,言語等価性の問題は一次元VASSに対してさえも決定不能であり,従って,決定可能性を得るために,制限付きサブクラスについて調べた。一方では,筆者らはk曖昧VASS(任意の自然kに対して)におけるVASSの言語包含の問題が決定可能であり,またAckermannにおいてさえも可能であることを示した。一方,言語等価性問題は決定論的VASSに対して既にAckerman困難であることを証明した。これらの2つの結果は,いくつかの可能な制限における言語包含と等価性のためのアッカーマン完全性を意味する。また,著者らの技術のいくつかは,無限状態システム,すなわち,よく構造化された遷移システムのいくつかのサブクラスにおけるはるかに広い一般性において適用することができる。【JST機械翻訳】

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

計算理論

, , ,

前のページに戻る