The Experts below are selected from a list of 222 Experts worldwide ranked by ideXlab platform

Richard Mckinley - One of the best experts on this subject based on the ideXlab platform.

  • A sequent calculus demonstration of Herbrand's theorem
    arXiv: Logic, 2010
    Co-Authors: Richard Mckinley
    Abstract:

    Herbrand's theorem is often presented as a corollary of Gentzen's sharpened Hauptsatz for the classical sequent calculus. However, the midsequent gives Herbrand's theorem directly only for Formulae in Prenex Normal Form. In the Handbook of Proof Theory, Buss claims to give a proof of the full statement of the theorem, using sequent calculus methods to show completeness of a calculus of Herbrand proofs, but as we demonstrate there is a flaw in the proof. In this note we give a correct demonstration of Herbrand's theorem in its full generality, as a corollary of the full cut-elimination theorem for LK. The major difficulty is to show that, if there is an Herbrand proof of the premiss of a contraction rule, there is an Herbrand proof of its conclusion. We solve this problem by showing the admissibility of a deep contraction rule.

  • A sequent calculus demonstration of Herbrand’s Theorem
    2010
    Co-Authors: Richard Mckinley
    Abstract:

    Herbrand’s theorem is often presented as a corollary of Gentzen’s sharpened Hauptsatz for the classical sequent calculus. However, the midsequent gives Herbrand’s theorem directly only for Formulae in Prenex Normal Form. In the Handbook of Proof Theory, Buss claims to give a proof of the full statement of the theorem, using sequent calculus methods to show completeness of a calculus of Herbrand proofs, but as we demonstrate there is a flaw in the proof. In this note we give a correct demonstration of Herbrand’s theorem in its full generality, as a corollary of the full cut-elimination theorem for LK. The major difficulty is to show that, if there is an Herbrand proof of the premiss of a contraction rule, there is an Herbrand proof of its conclusion. We solve this problem by showing the admissibility of a deep contraction rule.

  • A sequent calculus demonstration of Herbrand’s Theorem
    2008
    Co-Authors: Richard Mckinley
    Abstract:

    Abstract. Herbrand’s theorem is now often dismissed as a corollary of Gentzen’s sharpened Hauptsatz for LK. However, the midsequent gives Herbrand’s theorem only for Formulae in Prenex Normal Form. In the Handbook of Proof Theory, Buss claims to give a proof of the full statement of the theorem, using sequent calculus methods, but as we demonstrate there is a flaw in the proof. In this note we give a correct demonstration of Herbrand’s theorem in its full generality, by means of the sequent calculus.

Zhao Bin - One of the best experts on this subject based on the ideXlab platform.

Moshe Y Vardi - One of the best experts on this subject based on the ideXlab platform.

  • Reasoning about Strategies: on the Satisfiability Problem
    Logical Methods in Computer Science, 2017
    Co-Authors: Fabio Mogavero, Aniello Murano, Giuseppe Perelli, Moshe Y Vardi
    Abstract:

    Strategy Logic (SL, for short) has been introduced by Mogavero, Murano, and Vardi as a useful Formalism for reasoning explicitly about strategies, as first-order objects, in multi-agent concurrent games. This logic turns out to be very powerful, subsuming all major previously studied modal logics for strategic reasoning, including ATL, ATL*, and the like. Unfortunately, due to its high expressiveness, SL has a non-elementarily decidable model-checking problem and the satisfiability question is undecidable, specifically Sigma_1^1. In order to obtain a decidable sublogic, we introduce and study here One-Goal Strategy Logic (SL[1G], for short). This is a syntactic fragment of SL, strictly subsuming ATL*, which encompasses Formulas in Prenex Normal Form having a single temporal goal at a time, for every strategy quantification of agents. We prove that, unlike SL, SL[1G] has the bounded tree-model property and its satisfiability problem is decidable in 2ExpTime, thus not harder than the one for ATL*.

  • reasoning about strategies on the model checking problem
    ACM Transactions on Computational Logic, 2014
    Co-Authors: Fabio Mogavero, Aniello Murano, Giuseppe Perelli, Moshe Y Vardi
    Abstract:

    In open systems verification, to Formally check for reliability, one needs an appropriate Formalism to model the interaction between agents and express the correctness of the system no matter how the environment behaves. An important contribution in this context is given by modal logics for strategic ability, in the setting of multiagent games, such as A tl , A tl *, and the like. Recently, Chatterjee, Henzinger, and Piterman introduced Strategy Logic, which we denote here by CHP-S l , with the aim of getting a powerful framework for reasoning explicitly about strategies. CHP-S l is obtained by using first-order quantifications over strategies and has been investigated in the very specific setting of two-agents turned-based games, where a nonelementary model-checking algorithm has been provided. While CHP-S l is a very expressive logic, we claim that it does not fully capture the strategic aspects of multiagent systems. In this article, we introduce and study a more general strategy logic, denoted S l , for reasoning about strategies in multiagent concurrent games. As a key aspect, strategies in S l are not intrinsically glued to a specific agent, but an explicit binding operator allows an agent to bind to a strategy variable. This allows agents to share strategies or reuse one previously adopted. We prove that S l strictly includes CHP-S l , while maintaining a decidable model-checking problem. In particular, the algorithm we propose is computationally not harder than the best one known for CHP-S l . Moreover, we prove that such a problem for S l is N on E lementary . This negative result has spurred us to investigate syntactic fragments of S l , strictly subsuming A tl *, with the hope of obtaining an elementary model-checking problem. Among others, we introduce and study the sublogics S l [ ng ], S l [ bg ], and S l [1 g ]. They encompass Formulas in a special Prenex Normal Form having, respectively, nested temporal goals, Boolean combinations of goals, and, a single goal at a time. Intuitively, for a goal, we mean a sequence of bindings, one for each agent, followed by an L tl Formula. We prove that the model-checking problem for S l [1 g ] is 2E xp T ime - complete , thus not harder than the one for A tl *. In contrast, S l [ ng ] turns out to be N on E lementary -hard, strengthening the corresponding result for S l . Regarding S l [ bg ], we show that it includes CHP-S l and its model-checking is decidable with a 2E xp T ime lower-bound. It is worth enlightening that to achieve the positive results about S l [1 g ], we introduce a fundamental property of the semantics of this logic, called behavioral, which allows to strongly simplify the reasoning about strategies. Indeed, in a nonbehavioral logic such as S l [ bg ] and the subsuming ones, to satisfy a Formula, one has to take into account that a move of an agent, at a given moment of a play, may depend on the moves taken by any agent in another counterfactual play.

  • 3 4 5 6
    2013
    Co-Authors: Fabio Mogavero, Aniello Murano, Moshe Y Vardi
    Abstract:

    Abstract—Strategy Logic (SL, for short) has been recently introduced by Mogavero, Murano, and Vardi as a useful Formalism for reasoning explicitly about strategies, as firstorder objects, in multi-agent concurrent games. This logic turns to be very powerful, subsuming all major previously studied modal logics for strategic reasoning, including ATL, ATL ∗ , and the like. Unfortunately, due to its expressiveness, SL has a nonelementarily decidable model-checking problem and a highly undecidable satisfiability problem, specifically, Σ 1 1-HARD. In order to obtain a decidable sublogic, we introduce and study here One-Goal Strategy Logic (SL[1G], for short). This logic is a syntactic fragment of SL, strictly subsuming ATL ∗ , which encompasses Formulas in Prenex Normal Form having a single temporal goal at a time, for every strategy quantification of agents. SL[1G] is known to have an elementarily decidable model-checking problem. Here we prove that, unlike SL, it has the bounded tree-model property and its satisfiability problem is decidable in 2EXPTIME, thus not harder than the one for ATL ∗. I

  • What Makes ATL ∗ Decidable? A Decidable Fragment of Strategy Logic
    2013
    Co-Authors: Fabio Mogavero, Aniello Murano, Moshe Y Vardi
    Abstract:

    Abstract Strategy Logic (SL, for short) has been recently introduced by Mogavero, Murano, and Vardi as a Formalism for reasoning explicitly about strategies, as first-order objects, in multi-agent concurrent games. This logic turns out to be very powerful, strictly subsuming all major previously studied modal logics for strategic reasoning, including ATL, ATL ∗ , and the like. The price that one has to pay for the expressiveness of SL is the lack of important model-theoretic properties and an increased complexity of decision problems. In particular, SL does not have the bounded-tree model property and the related satisfiability problem is highly undecidable while for ATL ∗ it is 2EXPTIME-COMPLETE. An obvious question that arises is then what makes ATL ∗ decidable. Understanding this should enable us to identify decidable fragments of SL. We focus, in this work, on the limitation of ATL ∗ to allow only one temporal goal for each strategic assertion and study the fragment of SL with the same restriction. Specifically, we introduce and study the syntactic fragment One-Goal Strategy Logic (SL[1G], for short), which consists of Formulas in Prenex Normal Form having a single temporal goal at a time for every strategy quantification of agents. We show that SL[1G] is strictly more expressive than ATL ∗. Our main result is that SL[1G] has the bounded tree-model property and its satisfiability problem is 2EXPTIME-COMPLETE, as it is for ATL ∗.

  • A Decidable Fragment of Strategy Logic
    arXiv: Logic in Computer Science, 2012
    Co-Authors: Fabio Mogavero, Aniello Murano, Giuseppe Perelli, Moshe Y Vardi
    Abstract:

    Strategy Logic (SL, for short) has been recently introduced by Mogavero, Murano, and Vardi as a useful Formalism for reasoning explicitly about strategies, as first-order objects, in multi-agent concurrent games. This logic turns to be very powerful, subsuming all major previously studied modal logics for strategic reasoning, including ATL, ATL*, and the like. Unfortunately, due to its expressiveness, SL has a non-elementarily decidable model-checking problem and a highly undecidable satisfiability problem, specifically, $\Sigma_{1}^{1}$-Hard. In order to obtain a decidable sublogic, we introduce and study here One-Goal Strategy Logic (SL[1G], for short). This logic is a syntactic fragment of SL, strictly subsuming ATL*, which encompasses Formulas in Prenex Normal Form having a single temporal goal at a time, for every strategy quantification of agents. SL[1G] is known to have an elementarily decidable model-checking problem. Here we prove that, unlike SL, it has the bounded tree-model property and its satisfiability problem is decidable in 2ExpTime, thus not harder than the one for ATL*.

Linda Lawton - One of the best experts on this subject based on the ideXlab platform.

  • Decidability of the AE-theory of the lattice of $${\varPi }_1^0$$ Π 1
    Archive for Mathematical Logic, 2018
    Co-Authors: Linda Lawton
    Abstract:

    An AE-sentence is a sentence in Prenex Normal Form with all universal quantifiers preceding all existential quantifiers, and the AE-theory of a structure is the set of all AE-sentences true in the structure. We show that the AE-theory of $$(\mathscr {L}({\varPi }_1^0), \cap , \cup , 0, 1)$$ ( L ( Π 1 0 ) , ∩ , ∪ , 0 , 1 ) is decidable by giving a procedure which, for any AE-sentence in the language, determines the truth or falsity of the sentence in our structure.

  • Decidability of the AE-theory of the lattice of $${\varPi }_1^0$$ classes
    Archive for Mathematical Logic, 2017
    Co-Authors: Linda Lawton
    Abstract:

    An AE-sentence is a sentence in Prenex Normal Form with all universal quantifiers preceding all existential quantifiers, and the AE-theory of a structure is the set of all AE-sentences true in the structure. We show that the AE-theory of \((\mathscr {L}({\varPi }_1^0), \cap , \cup , 0, 1)\) is decidable by giving a procedure which, for any AE-sentence in the language, determines the truth or falsity of the sentence in our structure.

Wiesław Szwast - One of the best experts on this subject based on the ideXlab platform.