We develop a conceptually clear, intuitive, and feasible decision procedure for testing satisfi?ability in the full multi-agent epistemic logic CMAEL(CD) with operators for common and distributed knowledge for all coalitions of agents mentioned in the language. To that end, we introduce Hintikka structures for CMAEL(CD) and prove that satisfiability in such structures is equivalent to satis?fiability in standard models. Using that result, we design an incremental tableau-building procedure that eventually constructs a satisfying Hintikka structure for every satisfi?able input set of formulae of CMAEL(CD) and closes for every unsatisfi?able input set of formulae.
Several tableau-based methods for satisfiability-checking for modal logics with fixpoint-definable operators have been developed and published over the past 30 years, all going back to the tableau-based decision methods developed for the Propositional Dynamic Logic in @cite_21 , for the branching-time temporal logics in @cite_43 and in [Section 5] EmHal85 and @cite_18 . In terms of handling eventualities arising from the fixed-point operators our tableau method follows more closely on the incremental tableaux for the linear time temporal logic in @cite_27 and for in [Section 7] EmHal85 .
@cite_43 @cite_18 @cite_21 @cite_27
2000138546 1612453857 1997716585 1539868891
A temporal logic is defined which contains both linear and branching operators. The underlying model is the tree of all possible computations. The following metatheoretical results are proven: 1) an exponential decision procedure for satisfiability; 2) a finite model property; 3) the completeness of an axiomatization. Publisher Summary This chapter discusses temporal and modal logic. The chapter describes a multiaxis classification of systems of temporal logic. The chapter describes the framework of linear temporal logic. In both its propositional and first-order forms, linear temporal logic has been widely employed in the specification and verification of programs. The chapter describes the competing framework of branching temporal logic, which has seen wide use. It also explains how temporal logic structures can be used to model concurrent programs using non-determinism and fairness. The chapter also discusses other modal and temporal logics in computer science. The chapter describes the formal syntax and semantics of Propositional Linear Temporal Logic (PLTL). The chapter also describes the formal syntax and semantics for two representative systems of propositional branching-time temporal logics. Abstract We give an algorithm for “before-after” reasoning about action. The algorithm decides satisfiability and validity of formulas of propositional dynamic logic, a recently developed logic of change of state that subsumes the zero-order component of most other action-oriented logics. The algorithm requires time at most proportional to an exponentially growing function of the length (number of occurrences of variables and connectives) of the input. Fischer and Ladner have shown that that every algorithm for this problem must take exponential time, making this algorithm optimal to within a polynomial. Application areas include program verification, program synthesis, and discourse analysis. The algorithm is based on the method of semantic tableaux, appropriately generalized to dynamic logic. A formal treatment of the generalization, called Hintikka structures , is developed.