From LTL and Limit-Deterministic Büchi Automata to Deterministic Parity Automata
arXiv:1701.06103 · doi:10.1007/978-3-662-54577-5_25
Abstract
Controller synthesis for general linear temporal logic (LTL) objectives is a challenging task. The standard approach involves translating the LTL objective into a deterministic parity automaton (DPA) by means of the Safra-Piterman construction. One of the challenges is the size of the DPA, which often grows very fast in practice, and can reach double exponential size in the length of the LTL formula. In this paper we describe a single exponential translation from limit-deterministic Büchi automata (LDBA) to DPA, and show that it can be concatenated with a recent efficient translation from LTL to LDBA to yield a double exponential, \enquote{Safraless} LTL-to-DPA construction. We also report on an implementation, a comparison with the SPOT library, and performance on several sets of formulas, including instances from the 2016 SyntComp competition.
References in corpus (2)
Cited by in corpus (6)
- Practical Synthesis of Reactive Systems from LTL Specifications via Parity Games
- One Theorem to Rule Them All: A Unified Translation of LTL into ω-Automata
- From LTL and Limit-Deterministic Büchi Automata to Deterministic Parity Automata
- New Optimizations and Heuristics for Determinization of Büchi Automata
- Learning Optimal Strategies for Temporal Tasks in Stochastic Games
- How Concise are Chains of co-Büchi Automata?