パラメータ化された複雑な規則的な言語の包含

私は古典的な問題REGULAR LANGUAGE INCLUSIONに興味があります。正規表現$ E $が与えられれば、$
L(E)$で正規表現に関連付けられていることを示します。 (正規表現は固定されたアルファベット$ Sigma
$で、演算子、Kleene-starと連結子を伴います。)

Input: Two regular expressions $E_1$ and $E_2$
Question: Is it true that $L(E_1)subseteq L(E_2)$?

通常の言語の包含はPSPACE完全であると知られている[1]。

これを解決する古典的な方法(PSPACE)は、$ A_1 $と$ E_2 $に関連付けられたNFAs $ A_1 $と$ E_2
$を構築して、$ A_2 $からDFA $ D_2 $を作成し、DFA $に補完しますD_2 ^ C $を作成し、最後に$
L(E_1)$と$ L(E_2)^ C $の交点に対応する$ A_1 $と$ D_2 ^ C $から交点オートマトン$ A_P
$を構築する。今、$ L(E_1) subseteq L(E_2)$は、$ A_P
$に受け入れ可能なパスがない場合にのみ$です。

もし私が間違っていないならば、$ E_2
$が固定言語であるとき、多項式時間で全過程を行うことができます。唯一の指数関数的なブローアップは$ A_2 $を$ D_2
$に変換するからです。さらに問題は、$ E_2 $の長さである$ | E_2 |
$によってパラメータ化されたときのFPTです。

これは私の疑問を動機づけます:

質問: $ E_1 $が固定式である場合、REGULAR LANGUAGE
INCLUSIONの複雑さは?それはPSPACE完全なままですか?

[1] L. J. StockmeyerおよびA. R.
Meyer。指数関数時間を必要とする単語の問題:暫定的な報告。第5回ACM理論計算シンポジウム、STOC’73、pp.1-9。

Remark: Being a non-expert in the field, I find [1]
(and related papers of that time) quite unreadable, and couldn’t
find another proof of the PSPACE-completeness – any pointer to a
modern proof, such as in a book, is very welcome! Also, the authors
seem to allow squaring in their regular expressions, which is
nowadays rather non-standard, I believe.)

ベストアンサー

言語の普遍性の特別な場合(すべての言葉が受け入れられますか?)は、正規表現やNFAの場合はPSPACE完全です。それはあなたの質問に答える:言語の普遍性は$
E_1 = Sigma ^ * $に対応しているので、問題は一般的に固定$ E_1
$であってもPSPACE-completeを維持する。

伝統的な普遍性のために現代的に読みやすいPSPACE硬度証明を見つけることは実際には難しいです。証明書を再構築するための簡単な証明方式があります:


多項式空間$ p(n)$を使ってアルファベット$ Sigma $上のチューリングマシン$ M $を考えてみましょう。
Sigma ^ * $は$ M $の入力語です。 $ M $が$ w $を受け入れない場合にのみ、すべての単語を受け入れる正規表現$
e $を作成します。

言語$ L_M $を$ $ C_0 $ C_1 $ dots $ C_f
$$の形式の単語で構成します。ここで、各$ C_i $は、正確に$ p(n)の長さの$ M $の構成です。 $ C_0
$はテープ上に$ w $を持つ初期構成であり、$ C_f $は受け入れられ、$ C_i 〜C_ {i + 1} $は$ M
$の有効な遷移です。 $ L_M $の単語は、$ M $の受け入れ実行を表します。

$ L_Mの定義違反を探して、$ L_M $にない単語を$ e $が正確に受け入れるように、アルファベット$ Sigma
‘= Sigma cup { $ } $に$ e $を作成します$。 $ e_i $は、違う種類の違反を探す$ e_1
+ e_2 + dots + e_k $と大きな違いがあります。例えば、$$ e_1 =( Sigma ‘)^ * $(
Sigma ^ {

$( Sigma ‘)^ * $$は、各$ C_i $のサイズが正確に$
p(n)$であるという事実の違反を探します。最も難しいのは、$ C_i $と$ C_ {i + 1}
$の間の違反を推測することです。式は$ C_i $のローカルパターンと$ C_ {i + 1} $の画像を比較できます。
sigma ‘)^ {p(n)} t’ $ここで、$ t $と$ t
‘$はローカルパターンの式です。これにより、ローカルパターン上の$ M
$の遷移関数の違反、またはこのパターン以外のアイデンティティの違反を推測することができます。最後に、$ L(e) neq(
Sigma ‘)^ * text {L_M neq emptyset text {$ M
$が受け入れられる場合に限り} w $$したがって、任意のPSPACE問題を(多項式的に)正規表現の普遍性に還元しました。
私はいくつかの詳細を除外しましたが、これはあなたに完全な証明を作ることを可能にするはずです。


もちろん、Michael Weharがコメントで指摘したように、$ E_1
$の他の人にとって、問題はより簡単になる可能性があります。この問題の複雑さの分類は、このペーパーで広く研究されています。
[1]同値、封じ込め、およびカバー。等価問題の結果の要約をこの回答に見ることができます(NP完全なケースが存在します)

四角形に対するあなたの発言について:正規表現の二乗を許可することは、包含と普遍性の問題をEXPSPACE-complete
[2]にします。これは、$
p(n)$の二項分解を使って対数サイズの式で表すことができるので、上記の証明スキームで見ることができることに注意してください。式の多項式の大きさを保ちながら指数関数的な$
p(n)$まで上げることができます。

[1] 正規言語および文脈自由言語の等価性、封じ込め、およびカバー問題について Harry
B.Hunt、Daniel J.Rosenkrantz、Thomas G.Szymanski。
コンピュータとシステム科学のジャーナル。 第12巻、第2版、1976年4月、第222-268頁

[2] 二乗法を用いた正規表現の等価問題は指数関数的空間を必要とする。 Meyer、A.R.およびL.
Stockmeyer。第13回スイッチングとオートマトン理論に関するIEEEシンポジウム、1972年10月、pp.125-129

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です