Generalized Quine-McCluskey
- From: sashaDOTmal <sashaPUNKTmal@xxxxxxxxxx>
- Date: Tue, 25 Sep 2007 13:49:54 +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: Data structure behind Google Suggest
- Next by Date: Mathematical models for loop calculations
- Previous by thread: Data structure behind Google Suggest
- Next by thread: Re: Generalized Quine-McCluskey
- Index(es):
Relevant Pages
|
