1,721,023 research outputs found
Taming Strategy Logic: Non-Recurrent Fragments
Full text linkStrategy 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
SCHEDE 22-26 IN SCHICCHI R. E RAIMONDO F. M. SCHEDE PER IL CENSIMENTO DEGLI ALBERI MONUMENTALI DI SICILIA
No full text
Solving Mean-Payoff Games via Quasi Dominions
Full text linkWe propose a novel algorithm for the solution of mean-payoff games that merges together two seemingly unrelated concepts introduced in the context of parity games, small progress measures and quasi dominions. We show that the integration of the two notions can be highly beneficial and significantly speeds up convergence to the problem solution. Experiments show that the resulting algorithm performs orders of magnitude better than the asymptotically-best solution algorithm currently known, without sacrificing on the worst-case complexity
Taming Strategy Logic: Non-Recurrent Fragments
Full text linkStrategy Logic (SL for short) is one of the prominent languages for reasoning about the strategic abilities of agents in a multi-agent setting. This logic extends LTL with first-order quantifiers over the agent strategies and encompasses other formalisms, such as ATL* and CTL*. The model-checking problem for SL and several of its fragments have 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 SL, where the nesting of sentences within temporal operators is constrained. We show that the satisfiability problem for these logics, and for the corresponding fragments of ATL* and CTL*, is ExpSpace and PSpace-complete, respectively
Binding Forms in First-Order Logic
Full text linkAiming to pinpoint the reasons behind the decidability of some complex extensions of modal logic, we propose a new classification criterion for sentences of first-order logic, which is based on the kind of binding forms admitted in their expressions, i.e., on the way the arguments of a relation can be bound to a variable. In particular, we describe a hierarchy of four fragments focused on the Boolean combinations of these forms, showing that the less expressive one is already incomparable with several first-order limitations proposed in the literature, as the guarded and unary negation fragments. We also prove, via a novel model-theoretic technique, that our logic enjoys the finite-model property, Craig's interpolation, and Beth's definability. Furthermore, the associated model-checking and satisfiability problems are solvable in PTime and Sigma_3^P, respectively
Priority Promotion with Parysian flair
Full text linkWe develop an algorithm that combines the advantages of Priority Promotion, that is one of the leading approaches to solving large parity games in practice, with the quasi-polynomial time guarantees offered by Parys' algorithm. Hybridising these algorithms sounds both natural and difficult, as they both generalise the classic recursive algorithm in different ways that appear to be irreconcilable: while the promotion transcends the call structure, the guarantees change on each level. We show that an interface that respects both is not only effective, but also efficient
- …
