Controller synthesis for MDPs and Frequency LTL$\setminus$GU

Vojtech Forejt, Jan Krcál, Jan Kretínský

Abstract

Quantitative extensions of temporal logics have recently attracted significant attention. In this work, we study frequency LTL (fLTL), an extension of LTL which allows to speak about frequencies of events along an execution. Such an extension is particularly useful for probabilistic systems that often cannot fulfil strict qualitative guarantees on the behaviour. It has been recently shown that controller synthesis for Markov decision processes and fLTL is decidable when all the bounds on frequencies are 1. As a step towards a complete quantitative solution, we show that the problem is decidable for the fragment fLTL\GU, where U does not occur in the scope of G (but still F can). Our solution is based on a novel translation of such quantitative formulae into equivalent deterministic automata.

Introduction

In the formal verification and control of stochastic systems, Linear Temporal Logic (LTL) has long served as the standard for specifying system requirements. However, LTL is inherently qualitative; it can specify that an event must "eventually" occur or "always" hold, but it cannot express how often an event should occur over a long-run execution. For real-world systems—such as autonomous robots or server clusters—requirements are often quantitative: "failures should occur in less than 0.1% of steps" or "the system should remain in an idle state at least 20% of the time."

Frequency LTL (fLTL) was developed to bridge this gap by allowing specifications regarding the long-run frequency of events. While expressive, fLTL introduces significant mathematical complexity, often leading to undecidability in controller synthesis. This paper presents a breakthrough for a specific, powerful fragment of the logic: fLTL\GU.

The fLTL\GU Fragment

The primary challenge in synthesizing controllers for frequency-based properties is the interaction between temporal operators. The authors identify the "Until" ($U$) operator as a primary source of complexity when nested within a "Globally" ($G$) or frequency operator. By restricting the logic to the fLTL\GU fragment—where $U$ cannot occur within the scope of $G$—the authors define a subset of the logic that remains highly expressive for practical applications while remaining mathematically tractable.

Methodology: Master-Slave Automata

The core contribution of this work is a novel translation of fLTL\GU formulas into Deterministic Generalized Rabin Mean-payoff Automata (DGRMA). This is achieved through a "Master-Slave" architecture:

  1. The Master Automaton: This component tracks the high-level progress of the formula’s temporal structure.
  2. Slave Automata: These monitor specific infinitary properties, such as whether a sub-formula is satisfied with a required frequency.

Crucially, for the fLTL\GU fragment, these slave automata are acyclic. This ensures that the number of "tokens" used to track satisfied instances of a property remains bounded, allowing the state space to remain finite. This represents the first successful translation of a quantitative logic into equivalent deterministic automata, a prerequisite for effective controller synthesis in Markov Decision Processes (MDPs).

Synthesis via Multi-Objective Optimization

Once the deterministic automaton is constructed, the synthesis problem is transformed into a product analysis between the MDP and the DGRMA. The goal is to find a strategy (a controller) that satisfies the frequency bounds.

Because frequencies on infinite paths may not converge to a single value, the framework explicitly accounts for both the limit inferior (the minimum long-run frequency) and the limit superior (the maximum long-run frequency). The authors solve this as a multi-objective mean-payoff problem, utilizing linear constraints—analogous to Kirchhoff’s laws—to balance various rewards and satisfy Rabin acceptance conditions simultaneously.

Key Results and Complexity

The research establishes several landmark results for the field:

  • Decidability: The controller synthesis problem for MDPs against fLTL\GU is proven to be decidable.
  • Complexity Class: The algorithm operates in doubly exponential time ($2^{2^{O(n)}}$) relative to the formula size. Notably, this matches the complexity of standard LTL synthesis, implying that the transition from qualitative to quantitative specifications does not necessarily incur a higher theoretical complexity cost.
  • Optimization for Connected MDPs: For MDPs that are strongly connected, the existence of a winning strategy can be verified in polynomial time once the automaton is built.

Conclusion and Future Work

This work provides a robust framework for managing quantitative requirements in stochastic environments. While the $\setminus GU$ restriction limits the use of nested "Until" operators within frequency bounds, it provides a necessary foundation for future expansions. Future research aims to extend the master-slave architecture to the full fLTL logic by addressing the challenges posed by cyclic slave automata and unbounded state spaces.

Summary updated

Abstract

Quantitative extensions of temporal logics have recently attracted significant attention. In this work, we study frequency LTL (fLTL), an extension of LTL which allows to speak about frequencies of events along an execution. Such an extension is particularly useful for probabilistic systems that often cannot fulfil strict qualitative guarantees on the behaviour. It has been recently shown that controller synthesis for Markov decision processes and fLTL is decidable when all the bounds on frequencies are 1. As a step towards a complete quantitative solution, we show that the problem is decidable for the fragment fLTL$\setminus$GU, where U does not occur in the scope of G (but still F can). Our solution is based on a novel translation of such quantitative formulae into equivalent deterministic automata.
BibTeX
@inproceedings{forejt2015controller,
  author = {Vojtech Forejt and Jan Krcál and Jan Kretínský},
  title = {{Controller synthesis for MDPs and Frequency LTL$\textbackslash\{\}setminus$GU}},
  booktitle = {LPAR},
  year = {2015},
  doi = {10.1007/978-3-662-48899-7\_12},
}
Figure