いくつかの線形時間論理を満たすためにデータのストリームを強制するためのLTL（バリアント）を表現する方法

Question

線形時間論理（LTL）はシステム検証に使用されます。私の場合、私はしばらくの間、私はデータのストリームに対する制約を強制するためにLTLを使用することの実現可能性を確認するために、いつか投資しています。十分な一般性、簡単な例を取りましょう：

LTLの式u Until vでは、uまでイベントv、それは一般式であり、信号トレースの無限数の数が満たすことができます。ここでの定義を参照してください。 Page4

のようなもの：

u,u,u,v,v,v,...
u,u,u,u,u,u,...
u,v,v,v,v,v,...

.

私の場合は、データのストリームを受信したシステムにLTLを適用したいです。もう一度同じオペレーターを服用しましょう。

定数Uのための2つの入力信号、1つは定数vのためのものと1つの入力信号を持っているとしましょう。

u,u,u,u,u,u,...
 , , , ,v,v,...

.

これらの入力を取っているストリームプロセッサは、それが「まで*」ノードである場合、出力されます。

u,u,u,u,v,v,...

.

がアスタリスクでが区別する理由は、質問の全点です.Vが2番目のストリームに表示されるとすぐにVが出力されたときに "Uまで" uが叶います。 、入力信号を考えると、「Uまで* v」を満たすことは1つのシングルトレースです。 この制約を表現する方法！ LTLはこの「制約施行メカニズム」にとって非常に一般的に見えます。

注：私と一緒に耐えてください、私はコンピュータの科学者でも数学者でもありません、私は新しいことを学びようとする平均的なプログラマーです。

Answer 1

これは面白い質問です。

LTL（リニアの時間論理）の質問ではありません。 >

あなたが望むか行われたかどうかは、ストリームに対する許容されている変更が正確にどのような変更であるかによって異なります。あなたの例では、あなたはある意味で、2つのストリームをリミックスしています。 LTLは、あらゆる文字が同時に真の複数の命題を持つことができるアルファベットの上で定義されていることに注意してください。それであなたの例では、あなたはuとvのストリームを一緒に混ぜたばかりの：

u,u,u,u,{u,v},{u,v},....

.

これはLTLの式を満たしていたでしょう。あなたがリミックスする方法が、出力ストリーム内の命題が常に入力ストリームに設定されている命題のサブセットであることである場合は、 Reactive Synthesis を使用してストリームミキシングを行うトランスデューサを取得できます。 /修正。ただし、これはすべての出力ストリームに対して実際にミックスを実行する方法である場合にのみ機能します。

混合/固定の定量的な概念がある場合は、定量的合成はいくつかの結果を有する可能性がある研究分野であり得る。しかし、その領域からの結果のいずれかが適用可能かどうかを確認するには、正確なストリーム変更最適化基準の説明が必要です。