---
title: "LTLf and LDLf Synthesis under Partial Observability"
authors:
  - "Giuseppe De Giacomo"
  - "Moshe Y. Vardi"
doi: ""
url: "https://ijcai.org/proceedings/2016/152"
pdf: "https://ijcai.org/proceedings/2016/0152.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "1044-1049"
track: ""
keywords:
---

# LTLf and LDLf Synthesis under Partial Observability

Giuseppe De Giacomo, Moshe Y. Vardi

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 1044-1049.

## Abstract

In this paper, we study synthesis under partial observability for logical specifications over finite traces expressed in LTLf/LDLf. This form of synthesis can be seen as a generalization of planning under partial observability in nondeterministic domains, which is known to be 2EXPTIME-complete. We start by showing that the usual belief-state construction used in planning under partial observability works also for general LTLf/LDLf synthesis, though with a jump in computational complexity from 2EXPTIME to 3EXPTIME. Then we show that the belief-state construction can be avoided in favor of a direct automata construction which exploits projection to hide unobservable propositions. This allow us to prove that the problem remains 2EXPTIME-complete. The new synthesis technique proposed is effective and readily implementable.