Generalized Quine-McCluskey
- From: sashaDOTmal <sashaPUNKTmal@xxxxxxxxxx>
- Date: Tue, 25 Sep 2007 13:49:31 +0200
Dear all,
I'm looking for the generalization of the Quine-McCluskey algorithm in
case the underlying domain is not two-valued but d-valued (d is a
natural number).
More precise below.
Let x1,...,xn be n variables with range {1,...,d}. At atomic proposition
is "xi in A" for some 1<=i<=n and a subset A of {1,...,d}. A formula is
a boolean combination of atomic propositions. An implicant of a formula
f is a conjunction of atomic propositions that implies f. A prime
implicant g of f is an implicant of f so that there is no other
implicant f' of f so that g implies f'.
Decision problem: given a formula, find its all prime implicants.
Combinatorial question: give a sharp upper bound on the number of prime
implicants of a formula.
Any help, references, ideas are appreciated.
Thanks a lot
Sasha
.
- Prev by Date: Re: Godel, self-reference, and framework/object confusion
- Next by Date: Re: Equivalence of N and R?
- Previous by thread: Jack Tuszynski
- Next by thread: Re: michael lalonde .
- Index(es):
Relevant Pages
|
