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

[Raja R Harinath]

Hi,

Alexandre Duret-Lutz <address@hidden> writes:

> 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

I don't see this as a major problem.  AFAI can tell, the net effect is
that the number of terms is the same, though some of them are longer
than necessary.  That's close enough for government work :-)

The corresponding Makefile.am code is different

  if A
    if B
      foo = 1
    endif
  else
    foo = 2
  endif

vs.

  if !A
    foo = 2
  endif
  if B
    foo = 1
  endif

Consider A == false and B == true.  What should be the value of 'foo'?
It's not clear to me in the second variant.

> 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.)

Yes.  However, the net effect, it seems to me, is that some of the
terms are longer than necessary, since we sometimes don't allow a
term to notice that it could form a larger sub-cube by overlapping
with an already covered sub-cube.

It may all be for the best :-)  Given

  if !A
    if !B
      foo = 1
    endif
  endif
  bar = $(foo)

I don't see the 

  foo not defined in A_TRUE or B_TRUE

any better than

  foo not defined in A_TRUE or A_FALSE B_TRUE

> 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().

This is already happening right now, since 'simplify' is applied to the
output of 'inverse'.

> 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)

This is totally different.  These are redundant, since the sub-cube of
FG is completely covered by the sub-cube of F.

In the case of 

  F or ((not F) and G)

The sub-cube F'G can be combined with the sub-cube FG to form subcube
G.  FG is part of sub-cube F.  These terms are not redundant.

> Any thoughts?

Things are quite OK right now, if you ask me :-)

- Hari
-- 
Raja R Harinath ------------------------------ address@hidden