| | |
| | |
Stat |
Members: 3645 Articles: 2'506'133 Articles rated: 2609
26 April 2024 |
|
| | | |
|
Article overview
| |
|
ALLSAT compressed with wildcards. Part 2: All k-models of a BDD | Marcel Wild
; | Date: |
24 Mar 2017 | Abstract: | If f is a Boolean function given by a BDD then it is well known how to
calculate the number of models (i.e. bitstrings x with f(x)=1). Let |x| be the
number of 1’s in x. How to calculate the number of k-models x (i.e. having
|x|=k) is lesser known; we review a nice method due to Knuth. The main topic
however is enumeration (=generation) as opposed to counting. Again, that ALL
models can be enumerated in polynomial total time, is well known. Apparently
new is the fact that also all k-models (for any fixed k) can be enumerated in
polynomial total time. Using suitable wildcards this can be achieved in a
compressed format. | Source: | arXiv, 1703.8511 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |