Generalized Quine-McCluskey
- From: sashaDOTmal <sashaPUNKTmal@xxxxxxxxxx>
- Date: Tue, 25 Sep 2007 13:48:57 +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: Two results of set geometry
- Next by Date: Re: Two results of set geometry
- Previous by thread: Differential Geometry - Isometric Surfaces
- Next by thread: How to represent matrix ring GF(2^m)
- Index(es):
Relevant Pages
|
