Tesis doctoral de Jose Gaintzarain Ibarmia
In this thesis we propose a new approach to deductionmethods for temporal logic. Our proposalis based on an inductive definition of eventualities that is different from the usual one. On thebasis of this non-customary inductive definition for eventualities, we first provide dual systemsof tableaux and sequents for propositional linear-time temporal logic (pltl). Then, we adaptthe deductive approach introduced by means of these dual tableau and sequent systems to theresolution framework and we present a clausal temporal resolution method for pltl. Finally,we make use of this new clausal temporal resolutionmethod for establishing logical foundationsfor declarative temporal logic programming languages.The key element in the deduction systems for temporal logic is to deal with eventualitiesand ¿hidden¿ invariants that may prevent the fulfillment of eventualities. Different ways ofaddressing this issue can be found in the works on deduction systems for temporal logic.Traditional tableau systems for temporal logic generate an auxiliary graph in a first pass.Then, in a second pass, unsatisfiable nodes are pruned. In particular, the second pass mustcheck whether the eventualities are fulfilled. The one-pass tableau calculus introduced by s.Schwendimann requires an additional handling of information in order to detect cyclic branchesthat contain unfulfilled eventualities. Regarding traditional sequent calculi for temporal logic,the issue of eventualities and hidden invariants is tackled by making use of a kind of inferencerules (mainly, invariant-based rules or infinitary rules) that complicates their automation.A remarkable consequence of using either a two-pass approach based on auxiliary graphs or aone-pass approach that requires an additional handling of information in the tableau framework,and either invariant-based rules or infinitary rules in the sequent framework, is that temporallogic fails to carry out the classical correspondence between tableaux and sequents. In this thesis,we first provide a one-pass tableau method ttm that instead of a graph obtains a cyclictree to decide whether a set of pltl-formulas is satisfiable. In ttm tableaux are classical-like.For unsatisfiable sets of formulas, ttm produces tableaux whose leaves contain a formula andits negation. In the case of satisfiable sets of formulas, ttm builds tableaux where each fullyexpanded open branch characterizes a collection of models for the set of formulas in the root.The tableau method ttm is complete and yields a decision procedure for pltl. This tableaumethod is directly associated to a one-sided sequent calculus called ttc. Since ttm is free fromall the structural rules that hinder the mechanization of deduction, e.G. Weakening and contraction,then the resulting sequent calculus ttc is also free from this kind of structural rules. Inparticular, ttc is free of any kind of cut, including invariant-based cut. From the deductionsystem ttc, we obtain a two-sided sequent calculus gtc that preserves all these good freenessproperties and is finitary, sound and complete for pltl. Therefore, we show that the classicalcorrespondence between tableaux and sequent calculi can be extended to temporal logic.The most fruitful approach in the literature on resolution methods for temporal logic, whichwas started with the seminal paper of m. Fisher, deals with pltl and requires to generate invariantsfor performing resolution on eventualities. In this thesis, we present a new approachto resolution for pltl. The main novelty of our approach is that we do not generate invariantsfor performing resolution on eventualities. Our method is based on the dual methods oftableaux and sequents for pltl mentioned above. Our resolution method involves translationinto a clausal normal form that is a direct extension of classical cnf. We first show that anypltl-formula can be transformed into this clausal normal form. Then, we present our temporalresolution method, called trs-resolution, that extends classical propositional resolution.Finally, we prove that trs-resolution is sound and complete. In fact, it finishes for any inputformula deciding its satisfiability, hence it gives rise to a new decision procedure for pltl.In the field of temporal logic programming, the declarative proposals that provide a completenessresult do not allow eventualities, whereas the proposals that follow the imperative futureapproach either restrict the use of eventualities or deal with them by calculating an upper boundbased on the small model property for pltl. In the latter, when the length of a derivationreaches the upper bound, the derivation is given up and backtracking is used to try another possiblederivation. In this thesis we present a declarative propositional temporal logic programminglanguage, called tedilog, that is a combination of the temporal and disjunctive paradigms inlogic programming. We establish the logical foundations of our proposal by formally definingoperational and logical semantics for tedilog and by proving their equivalence. Since tedilogis, syntactically, a sublanguage of pltl, the logical semantics of tedilog is supported bypltl logical consequence. The operational semantics of tedilog is based on trs-resolution.Tedilog allows both eventualities and always-formulas to occur in clause heads and also inclause bodies. To the best of our knowledge, tedilog is the first declarative temporal logicprogramming language that achieves this high degree of expressiveness.Since the tableau method presented in this thesis is able to detect that the fulfillment ofan eventuality is prevented by a hidden invariant without checking for it by means of an extraprocess, since our finitary sequent calculi do not include invariant-based rules and since ourresolution method dispenses with invariant generation, we say that our deduction methods areinvariant-free.
Datos académicos de la tesis doctoral «Invariant-free deduction systems for temporal logic«
- Título de la tesis: Invariant-free deduction systems for temporal logic
- Autor: Jose Gaintzarain Ibarmia
- Universidad: País vasco/euskal herriko unibertsitatea
- Fecha de lectura de la tesis: 13/07/2012
Dirección y tribunal
- Director de la tesis
- Francisca Lucio Carrasco
- Tribunal
- Presidente del tribunal: fernando Orejas valdés
- stephan Merz — (vocal)
- María Alpuente frasnedo (vocal)
- ernesto Pimentel sanchez (vocal)