[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Automake::Conditional::simplify (Quine-McCluskey)

From: Alexandre Duret-Lutz
Subject: Re: Automake::Conditional::simplify (Quine-McCluskey)
Date: Mon, 18 Nov 2002 22:54:55 +0100
User-agent: Gnus/5.090008 (Oort Gnus v0.08) Emacs/20.7 (i386-debian-linux-gnu)

>>> "Raja" == Raja R Harinath <address@hidden> writes:


 >> BTW, I wonder if it's even possible to use so much conditionals
 >> in Automake.  

 Raja> Exactly.  I don't think it's worth it.  

Ok, for now I'll just change simplify() to return the input
as-is when this happens.


 >> Calling A::CS::permutations with 25 conditionals seems somewhat
 >> memory-consuming.  (Maybe it could help -- not in worst cases -- to
 >> always call A::CS::simplify before A::CS::invert)

 Raja> And, you could switch to a more compact representation for
 Raja> A::Conditional: move %var_rank and @rank_var from A::CS::simplify
 Raja> into A::Conditional, and represent conditionals directly as bitsets.

This sounds like a good idea.  However to do this we really need
a bitset implementation (because %var_rank and @rank_var would
apply to the whole project, instead of just one ConditionalSet).


 Raja> If you really want to worry about scalability, A::CS::invert would be
 Raja> better written as a product-of-sums to sum-of-products converter,
 Raja> rather than explicitly enumerating every truth-value candidate.

Indeed.  I'll do this.

 >> 2002-11-17  Alexandre Duret-Lutz  <address@hidden>
 >> * lib/Automake/ (simplify): New method.
 >> (string): Call string for each Conditional.
 >> * (variable_not_always_defined_in_cond): Return
 >> a simplified ConditionalSet.
 >> (macro_define, require_variables): Adjust.
 >> * tests/ (TEST): Add library3.test.
 >> * tests/library3.test: New file.
 >> * tests/pluseq9.test: Adjust.

While writing test cases, I've found a formula which is not
correctly simplified.
   A_FALSE or (A_TRUE and B_TRUE) 
is output as-is, although it could be simplified to 

It's my understanding that Quine-McCluskey's algorithm wouldn't
accept such input.  It only takes input products involving all
variables.  (I might as well be wrong: I've just read a few
slides found on the Internet after you mentioned that name.)
So one solution would be to transform this into
   (A_FALSE and B_TRUE) or (A_FALSE or B_TRUE) or (A_TRUE and B_TRUE)
and things would work.
However in the general case this is memory consuming just 
like A::CS::permutations().

Avoiding these "permutations" is why we have and additional loop,
"filter-out implied terms", after the combination step.  
It transforms
   F or (F and G) 
(where F and G are products of variables)

Maybe we should have a similar transformation, 
*before* the combination step, to transform
   F or ((not F) and G)
   F or G or ((not F) and G)
(not removing the last and-term, so it can be 
used in other combinations).

The question is how to match `(not F) and G'.
First, `not F' is a sum: NF1 or NF2 or ... or NFn
So given F we should look if we have the following n 
Conditionals before we can add G:
   NF1 and G
   NF2 and G
   NFn and G
Searching for these doesn't seem easy because we don't know G.

Second, `not F', means calling invert() for all Conditional in
the ConditionalSet.  Ouch.

At worst we could do this when F involves only one variable
(then it's easy to match `(not F) and G'), and ignore the other

Any thoughts?
Alexandre Duret-Lutz

reply via email to

[Prev in Thread] Current Thread [Next in Thread]