(SI)-EQLTL conversion tool


Enter an LTL formula:

Explanation

Define a formula using lowercase names for the propositional symbols, for instance:
	[](p U q)
The formula expresses a negative (undesired) property of a system.

When you type a <Return> in the entry box above, the formula is translated into an equivalent never-claim that can be used with the Spin model checker to verify properties of a distributed system. The automaton is displayed here in both textual and graphical format. (Note: the trivial automaton, which accepts every word is not displayed and is instead denoted by the claim never{ accept_all: skip} whereas the trivial automaton that accepts no words will be denoted by nothing displayed at all, and no never claim.)

The logic used here is (SI)-EQLTL, which is an extension of LTL that allows the expression of all (stutter-invariant) omega-regular languages (see Kousha Etessami, CAV99). Note that in order to take advantage of partial order reduction in Spin you need to specify properties that are stutter-invariant, and must therefore confine yourself to SI-EQLTL (as described below).

With this logic, in addition to the ordinary LTL properties currently used in Spin, you can prefix your LTL formula with existential quantification of propositional variables. There are two forms of accepted quantification of propositions. The first form is ordinary quantification which does not maintain stutter-invariance (only stutter-closure), while the second is a stutter-invariant version of the first, based on the notion of "harmoneous extension". Note that to preserve stutter-invariance the "Next" operator, X, should be avoided (although the language permits it).

Thus, only one of the two following quantification prefixes is allowed:

	{E p q .. }
meaning "there exists propositions p , q , etc." where phi is an LTL formula as defined below. This form of quantification is not stutter-invariant.
 	{E_h p q ..}
meaning "there exists harmoneous propositions p, q". Harmoneous here means that if the truth value of un-quantified propositions remains the same from one state to the next, then so must the value of the harmoneous quantified

The LTL formulas themselves are defined with the operators and connectives below. Note that we include also weak until and its dual, which are not used in Spin's conversion algorithm.

Accepted temporal logic operators are:

	[]  Always (no space between [ and ])
	<>  Eventually (no space between < and >)
	U   (Strong) Until
	V   The Dual of Until: (p V q) == !(!p U !q)
	W   Weak Until
	M   The Dual of Weak Until:  (p M q) == !(!p W !q)
	X   Next
Use spaces to separate each operator from its operands. Note that use of the Next operator may violate stutter invariance. All operators are left-associative (including U , V, W, and M).

Boolean Operators:

	&&  Logical And (alternative form: /\, no spaces)
	!   Logical Negation
	||  Logical Or  (alternative form: \/, no spaces)
	->  Logical Implication
Boolean Predicates:
	true, false
	any name that starts with a lowercase letter
Precedence:

Sorted in order from least to greatest, the operator precedences are:

	-> , ||,  &&
	M , W,  U,  V,  <> , [] 
	X , !
Examples:
	[] p
	!( <> !q )
	p U q
	p U ([] (q U r))
	{E p q} []((p -> q) && (q -> p) && (p -> X !q) && (!p -> X q) && (p -> a))
	{E_h q} []<> (p -> (p U q)) && [](q U !q)

For all questions: kousha@research.bell-labs.com