일부 선형 시간 논리를 충족하도록 데이터 스트림을 적용하기 위해 LTL(변형)을 표현하는 방법

Question

선형 시간 논리 (LTL)은 다음 용도로 사용됩니다. 시스템 검증.제 경우에는 이번에 LTL을 사용하여 데이터 스트림에 제약을 적용할 수 있는지 알아보기 위해 시간을 투자하고 있습니다.일반화는 이제 충분합니다. 간단한 예를 들어보겠습니다.

운영자 까지 표현에서 u Until v LTL에서는 이벤트를 의미합니다. u ~까지 v, 이는 일반적인 공식이다. 무한한 수 신호 추적을 만족시킬 수 있습니다.여기에서 정의를 확인하세요.4페이지

좋다:

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

제 경우에는 데이터 스트림을 수신하는 시스템에 공식과 같은 LTL을 적용하고 싶습니다.다시 동일한 연산자인 Until을 사용하겠습니다.

두 개의 입력 신호, 즉 상수 u에 대한 신호와 상수 v에 대한 신호가 있다고 가정해 보겠습니다.

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

이러한 입력을 받는 스트림 프로세서는 "UNTIL*" 노드인 경우 다음을 출력합니다.

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

내가 차별화하는 이유 까지 별표가 있는 것은 질문의 요점입니다. "u UNTIL* v"는 v가 두 번째 스트림에 나타나자마자 출력으로 사용되는 경우에만 참입니다. 이는 주어진 우리의 "u UNTIL* v"를 만족하는 하나의 단일 추적입니다. 입력 신호. 이 제약조건을 어떻게 표현하나요?!LTL은 이 "제약 조건 적용 메커니즘"에 대해 매우 일반적인 것으로 보입니다.

메모:양해해 주시기 바랍니다. 저는 컴퓨터 과학자도 아니고 수학자도 아닙니다. 저는 새로운 것을 배우려고 노력하는 평범한 프로그래머입니다.

Answer 1

이것은 흥미로운 질문입니다.

이는 직접적인 LTL(선형 시간 논리) 질문이 아니라 입력 스트림을 가져와 주어진 LTL 속성을 충족하기 위해 다소 최소한의 방식으로 수정하는 알고리즘이나 도구가 있는지에 대한 질문입니다.

원하는 작업이 완료되었는지 또는 완료되었는지 여부는 스트림에 허용된 수정 사항이 정확히 무엇인지에 따라 달라집니다.귀하의 예에서는 어떤 의미에서 두 개의 스트림을 리믹스하고 있습니다.LTL은 모든 문자가 당시 TRUE인 여러 명제를 가질 수 있는 알파벳을 통해 정의됩니다.따라서 귀하의 예에서는 u와 v 스트림을 함께 혼합하여 다음을 얻을 수 있습니다.

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

이는 LTL 공식도 만족했을 것입니다.리믹스 방식이 출력 스트림의 명제가 항상 입력 스트림에 설정된 명제의 하위 집합인 경우 다음을 사용할 수 있습니다. 반응성 합성 스트림 혼합/고정을 수행하는 변환기를 얻습니다.그러나 이는 모든 출력 스트림에 대해 실제로 믹스를 수행할 수 있는 방법이 있는 경우에만 작동합니다.

혼합/고정에 대한 정량적 개념이 있는 경우 정량적 합성은 일부 결과를 얻을 수 있는 연구 분야일 수 있습니다.그러나 해당 영역의 결과가 적용 가능한지 확인하려면 정확한 스트림 수정 최적화 기준에 대한 설명이 필요합니다.