From: Stefan Decker ([email protected])
Date: 02/18/03
Hi, a comment to the Lloyd-Topor discussion: the worst-case complexity of Lloyd-Topor is exponential (in the number of "<->" (equivalences) used). The reason is that "<->" is transformed into two implications: "A<->B" => "A->B" and "A<-B". So each equivalence doubles the number of formulas which needs to be transformed, which results in the exponential complexity. However, the number of equivalences in a formula is usually small, so this behavior is not a real problem. Not taking equivalences into account, Lloyd-Topor behaves nicely: the time complexity is linear in the length of the formula. Best, Stefan -- http://www.isi.edu/~stefan
This archive was generated by hypermail 2.1.4 : 02/18/03 EST