Taming Strategy Logic: Non-Recurrent Fragments

Strategy Logic ([Formula presented] for short) is one of the prominent languages for reasoning about the strategic abilities of agents in a multi-agent setting. This logic extends [Formula presented] with first-order quantifiers over the agent strategies and encompasses other formalisms, such as [Formula presented] and [Formula presented]. The model-checking problem for [Formula presented] and several of its fragments has been extensively studied. On the other hand, the picture is much less clear on the satisfiability front, where the problem is undecidable for the full logic. In this work, we study two fragments of One-Goal [Formula presented], where the nesting of sentences within temporal operators is constrained. We show that the satisfiability problem for these two logics, and for the corresponding fragments of [Formula presented] and [Formula presented], is in [Formula presented] and [Formula presented], respectively.