Title :
A complete proof systems for QPTL
Author :
Kesten, Yonit ; Pnueli, Amir
Author_Institution :
Dept. of Comput. Sci., Weizmann Inst. of Sci., Rehovot, Israel
Abstract :
The paper presents an axiomatic system for quantified propositional temporal logic (QPTL), which is propositional temporal logic equipped with quantification over propositions (boolean variables). The advantages of this extended temporal logic is that its expressive power is strictly higher than that of the unquantified version (PTL) and is equal to that of SIS, as well as that of ω-automata. Another important application of QPTL is its use for formulating and verifying refinement relations between reactive systems. In fact, the completeness proof is based on the reduction of a QPTL formula into a Buchi automaton, and performing equivalence transformations on this automata, formally justifying these transformations
Keywords :
automata theory; temporal logic; theorem proving; Buchi automaton; QPTL; automata; boolean variables; complete proof systems; propositional temporal logic; quantified propositional temporal logic; Automata; Boolean functions; Computational modeling; Computer science; Counting circuits; Logic;
Conference_Titel :
Logic in Computer Science, 1995. LICS '95. Proceedings., Tenth Annual IEEE Symposium on
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-7050-9
DOI :
10.1109/LICS.1995.523239