도달성 문제

도달성은 몇 가지 다른 맥락에서 나타나는 근본적인 문제로, 유한 및 무한 상태의 동시 시스템, 셀룰러 오토마타 및 페트리 네트와 같은 계산 모델, 프로그램 분석, 이산 및 연속 시스템, 시간 중요 시스템, 하이브리드 시스템, 재작성 시스템, 확률적 및 파라메트릭 시스템, 개방형 시스템이다.게임으로 모델링된.^[1]

일반적으로 도달성 문제는 다음과 같이 공식화될 수 있다: 일련의 허용된 규칙이나 변환이 있는 연산(잠재적으로 무한 상태) 시스템을 주어진다면, 시스템의 특정 상태가 시스템의 주어진 초기 상태에서 도달할 수 있는지 여부를 결정한다.

도달성 문제의 변형은 최초 또는 최종 상태의 추가 제약조건, 반복적인 도달성뿐만 아니라 도달성 경로에 대한 특정 요구사항 또는 무한 게임에서의 승리 전략 분석 또는 일부 역학관계의 불가능성 분석으로 질문을 변경함으로써 발생할 수 있다.

일반적으로, 어떤 형태(축소 규칙, 방정식 시스템, 논리 공식 등)에 제시된 고정 시스템 설명의 경우 도달 가능성 문제는 고정된 초기 상태 집합에서 시작하여 주어진 목표 상태 집합에 도달할 수 있는지 확인하는 것으로 구성된다.대상 상태 집합은 명시적으로 또는 일부 암묵적 표현(예: 방정식의 시스템, 상태의 일부 순서에 관한 최소 요소 집합)을 통해 나타낼 수 있다.정교한 양적, 질적 특성은 종종 기본적인 도달 가능성 질문으로 축소될 수 있다.결정성과 복잡성 경계, 알고리즘 솔루션, 효율적인 휴리스틱스는 모두 이 맥락에서 고려해야 할 중요한 측면들이다.알고리즘 솔루션은 종종 탐색 전략의 서로 다른 조합, 상태 집합의 상징적 조작, 분해 속성 또는 선형 프로그래밍 문제로의 축소에 기초하며, 근사, 추상화, 가속 및 외삽적 휴리스틱스로부터 이익을 얻는 경우가 많다.범용 제약 해결사 및 공제 엔진에 기초한 해결책뿐만 아니라 애드혹 솔루션도 효율성과 유연성 균형을 맞추기 위해 결합되는 경우가 많다.

다양한 접근성 문제

유한 명시적 그래프

명시적으로 설명한 지향적 그래프의 도달성 문제는 NL-완전이다.레이놀드는 2008년 기사에서 지향하지 않는 그래프의 도달 가능성 문제가 LOGSpace에 있다는 것을 증명했다.^[2]

모델 확인에서 도달 가능성은 생동감 있는 속성에 해당한다.

유한 암묵 그래프

고전적 계획에서 보다 정확히 말하자면, 사람들은 행동의 설명으로부터 초기 상태로부터 국가를 얻을 수 있는지를 아는 데 관심이 있다.작용에 대한 설명은 암묵적 상태의 그래프를 정의하는데, 이것은 설명의 크기에서 지수적인 크기이다.

심볼 모델 검사에서 모델(기본 그래프)은 이진 결정도와 같은 심볼 표현을 지원하여 설명한다.

페트리 그물

페트리 네트의 도달성 문제는 분리할 수 있다.^[3]1976년 이후, 이 문제는 EXPSPACE-hard로 알려져 있다.^{[4][full citation needed]}실제로 이 문제를 얼마나 실천해야 할지에 대한 결과가 있다.^[5]2018년에는 문제가 비초상적인 것으로 나타났다.^[6]

문제 열기

이 구간은 비어 있다.추가하면 도움이 된다. (2013년 4월)

도달 가능성 문제에 대한 국제 회의(RP)

이전에 도달성 문제에 관한 워크숍으로 알려진 국제 도달성 문제 총회는 대수학적 구조, 계산적 모델, 하이브리드 시스템, 무한 게임 등에 나타나는 도달성 문제에 관심이 있는 다양한 분야와 배경의 연구자들이 한자리에 모이는 연례 학술 회의다.s, 논리 및 검증.워크숍은 서로 다른 분야에서 얻어진 결과들 사이의 간격을 메우되 공통의 수학 구조나 개념적 어려움을 공유하려고 한다.

참조