arXiv:2510.10189v3 cs.LO

시간적 계획 문제의 해결 불가능성에 대한 형식 검증된 인증

Formally Verified Certification of Unsolvability of Temporal Planning Problems

David Wang, Mohammad Abdulaziz

제출 2026-11-17

한국어 초록

우리는 시간적 계획의 해결 불가능성을 인증하는 접근법을 제시한다. 이 접근법은 계획 문제를 시간 오토마타 네트워크로 인코딩한 뒤, 해당 네트워크에 효율적인 모델 검사기를 적용하고, 이어서 인증서 검사기로 모델 검사기의 출력을 인증하는 방식에 기반한다. 우리의 접근법은 인증의 신뢰성을 우선시한다. 즉, 증명 보조기 Isabelle/HOL을 사용하여 시간 오토마타로의 인코딩 구현을 형식적으로 검증하고, Isabelle/HOL에서 형식 검증된 기존 인증서 검사기를 사용하여 모델 검사 결과를 인증한다.

원문 초록

We present an approach to unsolvability certification of temporal planning. Our approach is based on encoding the planning problem into a network of timed automata, and then using an efficient model checker on the network followed by a certificate checker to certify the output of the model checker. Our approach prioritises trustworthiness of the certification: we formally verify our implementation of the encoding to timed automata using the theorem prover Isabelle/HOL and we use an existing certificate checker (also formally verified in Isabelle/HOL) to certify the model checking result.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2510.10189v3제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.