[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/ConditionalSet.pm (simplify): New method.
>> (string): Call string for each Conditional.
>> * automake.in (variable_not_always_defined_in_cond): Return
>> a simplified ConditionalSet.
>> (macro_define, require_variables): Adjust.
>> * tests/Makefile.am (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
A_FALSE or B_TRUE
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)
into
F
(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)
into
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
cases.
Any thoughts?
--
Alexandre Duret-Lutz
- Automake::Conditional::simplify (Quine-McCluskey), Alexandre Duret-Lutz, 2002/11/16
- Re: Automake::Conditional::simplify (Quine-McCluskey), Raja R Harinath, 2002/11/16
- Automake::Conditional::invert, Alexandre Duret-Lutz, 2002/11/19
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/19
- Re: Automake::Conditional::invert, Alexandre Duret-Lutz, 2002/11/20
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/20
- Re: Automake::Conditional::invert, Alexandre Duret-Lutz, 2002/11/20
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/20
- FYI: make_conditional_string, Alexandre Duret-Lutz, 2002/11/21
FYI: simplify variable_not_always_defined_in_cond, Alexandre Duret-Lutz, 2002/11/20