arXiv:2608.02454v1 cs.AI

유한 추적 기법을 활용한 무한 추적 목표: LTL의 LTLf+ 변환

Infinite Trace Objectives with Finite Trace Techniques: Translating LTL to LTLf+

Christoph Weinhuber, Maximilian Prokop, Giuseppe De Giacomo, Moshe Y. Vardi

제출 2026-08-03

한국어 초록

선형 시제 논리(LTL)는 반응형 합성부터 마르코프 결정 과정(MDP)에서의 확률적 계획 수립 및 강화학습에 이르기까지, 인공지능(AI) 분야에서 시제적으로 확장된 목표를 명세하는 데 가장 널리 채택되는 언어 중 하나입니다. 전통적으로 이러한 문제를 해결하려면 LTL 명세를 무한 단어에 대한 비결정적 오토마타로 변환한 다음 이를 결정화해야 하는데, 이 단계는 이론적으로나 실무적으로 악명 높을 정도로 어렵습니다. 최근 연구에서는 유한 추적 논리인 LTLf를 무한 추적으로 확장한 LTLf+를 도입했습니다. LTLf+는 LTL과 동일한 표현력을 가지면서도 기반 논리인 LTLf의 핵심적 이점 대부분을 유지합니다. LTLf+에서의 추론 대부분은 유한 단어에 대한 유한 오토마타를 기반으로 하며, 이는 표준 최소 표현뿐만 아니라 효율적인 결정화 절차도 갖추고 있습니다. 본 연구에서는 LTL에서 LTLf+로의 최초 변환 기법을 제시합니다. 먼저 LTL 공식을 Manna-Pnueli 계층 구조의 구문 반응성 프래그먼트로 정규화하여 LTLf+의 일반적인 프래그먼트 기반 형태를 생성합니다. 그런 다음 해당 프래그먼트의 각 개별 구성 요소에 대한 선형 변환을 제시합니다. 이 변환의 결과로, LTLf+를 위해 개발된 점점 확장되는 기법들을 현재 LTL로 정식화된 수많은 AI 문제에 적용할 수 있게 되었습니다. 나아가 LTL에서 LTLf+를 거쳐 오토마타에 이르는 파이프라인이 여전히 이중 지수(doubly exponential) 복잡도를 유지하므로, 점근적 비용 증가가 발생하지 않음을 보입니다.

원문 초록

Linear Temporal Logic (LTL) is one of the most widely adopted languages for specifying temporal extended objectives in AI, with applications ranging from reactive synthesis to stochastic planning in Markov decision processes and reinforcement learning. Traditionally, solving any of these problems requires translating the LTL specification to a nondeterministic automata on infinite words and then determinizing it, a step that is notoriously difficult in theory and in practice. Recent work has introduced LTLf+, which lifts the finite-trace logic LTLf to infinite traces. LTLf+ has the same expressive power as LTL, yet it retains most of the crucial advantages of its base logic LTLf. Most reasoning in LTLf+ rests on finite automata on finite words, for which we have not only a canonical minimal representation but also an efficient determinization procedure. In this work we present the first translation from LTL to LTLf+. We first normalize an LTL formula into the syntactic reactivity fragment of the Manna-Pnueli hierarchy, to create the general fragment-based shape of LTLf+. We then present linear translations for each individual component of that fragment. As a consequence of this translation, the expanding body of techniques developed for LTLf+ now becomes available to many AI problems currently formulated in LTL. We further show that this comes at no asymptotic cost, as the pipeline from LTL to automaton via LTLf+ remains doubly exponential.

제출 이력

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

  1. arXiv:2608.02454v1제출 시각 미확인

함께 살펴볼 논문

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

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

토론

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