|
Abstract : |
Abstract. We study the expressive power of linear propositional temporal logic interpreted on finite sequences or words. We first give a transparent proof of the fact that a formal language is expressible in this logic if and only if its syntactic semigroup is finite and aperiodic. This gives an effective algorithm to decide whether a given rational language is expressible. Our main result states a similar condition for the "restricted " temporal logic (RTL), obtained by discarding the "until " operator. A formal language is RTL-expressible if and only if its syntactic semigroup is finite and satisfies a certain simple algebraic condition. This leads to a polynomial time algorithm to check whether the formal language accepted by an n-state deterministic automaton is RTL-expressible. Temporal logic is a particular case of modal logic. It was introduced by Pnueli [16] in connection with applications to the specification, development and verification of possibly parallel or non-deterministic processes. This logical language admits several variations, one of them being propositional linear temporal logic (PTL). It uses three connectives suggestively called "next", "eventually " and "until"., |
