The Sasakawa Africa Association is seeking three dynamic agricultural development professionals to serve as its Country Directors in Ethiopia, Mali and Uganda. SAA Country Directors (CDs) work within a matrix management system that includes a number of staff in management-related positions – the two Executive Directors (Programs and Management); the Managing Directors (MDs) of SAA and SAFE; the five Program Directors (PDs) for Crop Extension, Post-harvest Extension, Public/Private Partnerships, Human Resource Development and ME&L; and the Director of Strategic Opportunities (DSO). CDs must respond to and collaborate with all these various actors, but they report administratively and are primarily responsible to the SAA Managing Director based in Addis Ababa, Ethiopia.


The rainy and cold winter was followed by a spring season rather favorable to the culture of the vine. But, in May, violent hailstorms hit part of our vineyard. Then a magnificent but not scorching summer (important thermal gaps between day and night) brought us fruity grapes in a perfect healthy state. The end of the gorgeous season enabled us to wait for an ideal maturity calmly.


Edmonton – The Alberta Federation of Labour (AFL) and Parkland Institute released a joint study today, showing Albertans will let billions slip through their fingers if the Northern Gateway Pipeline is approved and constructed.
The study showed that if Alberta met the royalty targets in place when Peter Lougheed was Premier, the province would have $1 trillion in the Heritage Fund by 2039.
According to oil industry data generated by the Canadian Energy Research Institute (CERI), Alberta will collect an average of only 18 per cent of the revenue generated in the oil sands as royalties.
The data covers the 2012-2045 forecast period and assumes the Northern Gateway pipeline will be constructed and operational.
In the 1980s, Alberta collected 35 per cent of oil industry revenue as royalties. The target was lowered to about 25 per cent during the Klein era.
AFL Secretary-Treasurer Nancy Furlong says any discussion of the Northern Gateway pipeline should involve Albertans getting their fair share first.
"The Northern Gateway pipeline will also ship thousands of upgrading and refining jobs down the pipeline to Asia, leaving Canadians with only 104 permanent jobs, most of them in B.C. Albertans are not getting their fair share from this pipeline," adds Furlong. The Alberta Federation of Labour represents 150,000 Albertans, including 25,000 working in the oil sands and energy-related construction.
Furlong adds that Alberta's oil sands wealth could – and should – be used to build the economy in the rest of the country.
"In the Lougheed era, when the Heritage Fund was growing, it was used for loans to other provinces and for infrastructure projects. There is no reason why – if we collected anything approaching appropriate royalty rates – Alberta could not lead the country toward a greener economy.
"What we have now is not an energy strategy. It's surrender," concludes Furlong.


Curious about what coaching can offer you?
Coaching gives you the framework to explore the essence of who you are and how you can express your gifts in this lifetime. Within the coaching relationship, you can expect exponential growth and a new empowerment to live your life on purpose.
It can start simply, with organizing some aspect of your home or office. And then blossom into claiming your freedom and power to live your life in harmony with your core values.
Coaching can focus on the query, "What's Next?" And then transform into a clarity and flow that fill your days with gratitude and the certainty that you are living the life you were meant to live.
Bring your curiosity, a willingness to explore and try new things, and a positive outlook. Bring your dreams and schemes. Bring your navigational questions (Where am I and what am I supposed to be doing?). Bring your desire to reach a new, healthier level of functioning in your personal or professional life.
I bring an unswerving dedication to you and your growth. I respect you as the expert on your life. And I hold you as naturally creative, resourceful and whole.
I bring insights and powerful questions to lead you to new ways of thinking. I provide structure and accountability to support you in your success. I bring tough questions and challenges in service of your growth. I bring the parade and balloons to celebrate your courage and breakthroughs.
I am Melissa Page Deutsch, a life coach and the owner of Inner Voice, LLC. I trained with the Coaches Training Institute, the oldest and most established coaches' training program in the country. My passion is to support people like you in making authentic, powerful choices so that you can live a purposeful, fulfilling life.
As a coach, my clients find me authentic, funny, intelligent, extremely intuitive, and positive. I provide a nonjudgmental space to explore whatever's on your mind. I excel at bringing clarity to clients who feel overwhelmed by tangled thoughts. I delight in helping my clients recognize and experience their beauty and to live empowered, joyful lives.
The name Inner Voice refers to that deep reservoir of peace and wisdom that lies at the center of each of us. It also pays tribute to my 20-plus years as a speech-language pathologist. I relied on brain-based research and a warm, interpersonal style to reconnect countless people with ways to communicate more effectively with their world. As a coach, it is in this spirit that I continue to partner with clients who seek to find and lead the fullest expression of their lives.
I blend my respect for evidence-based practices with a deep appreciation for age-old traditions that bring aliveness to mind and body. I am obsessed with utilizing cutting edge research related to neural plasticity – along with insight, intuition, and humor – to help my clients develop more effective ways of thinking, acting, and living.
Melissa has presented nationally and locally on navigating mindful transitions in one's personal and professional life. She is a Certified Professional Co-Active Coach and a member of the International Coaches Federation. She holds the certificate of clinical competence from the American Speech Language Hearing Association. Melissa received a B.A. in French from Davidson College and her M.S. in Speech-Language Pathology from the University of North Carolina at Chapel Hill.
Melissa has over 20 years' experience practicing insightful and intuitive listening to help her clients find and use their best voice – both the wise, inner voice and the physical, expressive voice – to live authentically, peacefully, and joyfully. She welcomes questions and inquiries regarding speaking engagements and personal development coaching.
Melissa lives in Norfolk, Virginia, with her husband, two teenage children, and two dogs. In her spare time, she enjoys running, yoga, connecting with friends, and a really good cup of coffee.
Please contact Melissa at (757) 408-1279 or Melissa@yourinnervoice.net for inquiries or to arrange a free 30-minute sample session.


text:
Opinions of Thursday, 31 January 2019
Columnist: Jude Mensa Duncan
Nana Addo goofed; persons with disabilities are Ghanaians too
In a country where most public spaces are not disability friendly, a country where physically challenged persons do not have an enabling environment to realize their aspirations, comments by the first gentleman of the land suggesting that only people like them can't see and hear about Government's efficiency are appalling, to say the least.
President Nana Akufo-Addo yesterday, in his bid to ensure his party retains the Ayawaso West Wuogon Parliamentary seat previously occupied by the late Emmanuel Kyeremanteng Agyarko, said it was only the blind and deaf who couldn't see the promises his Government is currently fulfilling.
"We came to fix Ghana, and in these two years, it is only those who are blind or deaf who are not aware that indeed we have done something," the President said on the campaign trail.
President Nana Addo made the ableism comments on this platform during the NPPs campaign at Ayawaso West Wuogon.
The United Nations' Convention on the Rights of Persons with Disabilities reinforces the need to protect the rights of children and adults with disabilities and ensure their full and equal participation in society. The President's comment does not promote this in any way.
Mr. President, the blind and deaf are Ghanaians too.
President Nana Akufo-Addo's comment offends the over 5 million people with disabilities in Ghana. [According to the UNICEF Ghana Country Report (2000:18)]. The President's comments amount to verbal abuse and for persons with disabilities, can be as painful as physical abuse.
Verbal abuse being explained as behaviours, SPEECH and actions of parents, caregivers or other important figures (including presidents) in an individual's life that negatively impact their state of mind.
For the President to concede in September 2018 that Ghana was in trying times, it is unfortunate a Government led by him which has, so far, done very little in terms of social intervention programs for PWDs will turn around and suggest that people like them can't see the 'positive change' his government has effected.
As shocking as those statements may seem, whether or not they were deliberately aimed at ridiculing a group of people is very unfortunate and one would have hoped that the President realizing his mistake would have come out to apologize for such unsavory comments.
Granted, politicians can get a little carried away by the atmosphere at party events, but a real hallmark of statesmanship that goes beyond only occupying the Jubilee house is the ability to pull together the nation in a hope of a better country.
For a President who has built a career on the back of advocating for the rights of the marginalized and less privileged in society, he should have been the first to have condemned his own comments. Even if he missed it for one or two reasons, his loyalists who were outraged in 2016 when the NDC's Edwin Nii Lantey Vanderpuye said the President was too short to become President should, rather than blindly support the President, have come out to say; "Look Nana, we love you, we want our party to win, but a comment like this about physically challenged people is a no-no"
As a recent graduate of the University of Ghana and a volunteer at Radio Univers; I was privy to some excellent work by persons the President said couldn't see the progress his Government has brought to the country.
One of my friends back at the University of Ghana, Ebenezer Azamati, who I interviewed on numerous occasions because of his in-depth knowledge and understanding of issues, was an excellent student by all standards. One who is clearly able to assess and feel the impact of a government claiming to have delivered on its promises.
Bukari Abdul Kudus, another physically challenged student was the valedictorian of his graduating class.
There are so many of such distinguishing stories of physically-challenged people doing amazing stuff at the University. These are just but a few.
Outside we hear similar stories of how physically challenged people, given the necessary support by Government, are able to not only see but feel the relevance of their Government.
The bigger problem in all of this too is how the opposition have kept mute on this matter, partially because they are also complicit in this to some extent as some of their party members have said same or worse in the past.
A leading figure in the NDC in 2014 made some insulting comments about Ivor Greenstreet after his 'criticism-filled' solidarity message to the party during their Kumasi congress in 2014.
The bigger problem is how ridiculing the physically-challenged can potentially become a part of our political culture in the name of expediency and satisfying the masses.
The Physically-challenged are Ghanaians too, given the right support and environment they can contribute to nation building.
The President's comments are regrettable because they inhibit personal growth, affect the confidence levels of such persons, and reinforce ableism, hence making them unable to actively contribute towards national development.
No matter what your intentions are and how genuine they might seem, you can't help someone if you see them as less than human.
Treating someone as a lesser being automatically hurts them no matter what positive results might be intentioned.
In 2015, according to the Ghana Federation Of Persons With Disabilities, "People with disabilities in Ghana are often regarded as unproductive and incapable of contributing in a positive way to society, and rather seen as constituting an economic burden on the family and the society at large, which leaves them in a vicious cycle of poverty."
The President in his 2019 new year message called on all Ghanaians to join hands in building the country.
"I am looking forward very much to 2019 with a sense of hope and optimism, because our nation is certainly on the right path. This year promises to be a good one, and I encourage you to join hands with my government in building the progressive and prosperous Ghana we all want," the President said.
This I believe included Persons with disability. Although his recent statement is regrettable, there is still a chance to prove to Ghanaians that his actions won't match his words.

redpajama_set_name: RedPajamaCommonCrawl


text:
 - Adding additional default configuration files, mimicking rake behavior
 - Avoid failing for [if_service_not_running, if_command_missing] if the block returns true
 - Add verbose mode to print all commands, accessible from the dsl :
  - ```verbose_on```
  - ```verbose_off```

# 0.1.0 March 18, 2012

 - Initial DSL definitions for (see docs in [Rockit::Application]):
  - ```if_file_changed```
  - ```if_directory_changed```
  - ```service```
  - ```if_service_not_running```
  - ```command```
  - ```if_command_missing```
  - ```if_first_time```
  - ```if_string_changed```
  - ```if_string_digest_changed```

redpajama_set_name: RedPajamaGithub


I got a pair of Alvin and the Chipmunks shoes and the movie "Chipwrecked" on dvd.
Someone answer me on my wall, then i will tell u the winner.
Do u like alvin and the chipmunks cartoon or real?
54 years and they still rock!
David tumawid Trashes 'Alvin And The Chipmunks: Chipwrecked,' With Uncomfortable Jewish Comment - New York Times.
Im saying this to ALL tsipmank FANS!
I Have 1 tanong AWESOME?????
omg i have to get the 3rd cuz i have the first 2 and i have the squakual double pack!!
i pag-ibig alvin and the chipmunks 2!!!!!!!!!!!!!!!!!!!!!


Ideal for nursing or simply relaxing, this Sleigh glider and ottoman combo offers an exceptionally smooth and extra long glide motion with thick cushions and padded arms that will add class and elegance to your decor. The multiposition mechanism locks the glider in 6 different positions and makes it easier to sit in or step out of the glider. In addition, it features a reclining mechanism to maximize your comfort. There are no sharp edges, the finish is toxic free and this product meets all safety standards.


text:
Photo Credit: Courtesy of LIFEWTR
News, Social Justice
Issa Rae Talks Uplifting Black Creatives Amid New LIFEWTR Campaign: 'Don't Be One Of The Crabs In A Barrel'
The actress is using her latest brand partnership to emphasize why the racial reckonings across creative industries need to be a movement and not a moment.
by Njera Perkins
Award-winning actress, producer, writer, and advocate Issa Rae kicked off her collaboration with Pepsi brand LIFEWTR on Wednesday in a campaign aimed at uplifting diverse creators across the arts.
In a candid conversation with Blavity, the 36-year-old multi-hyphenate spoke about the importance of continuing the work that the Black Lives Matter movement protests reignited last summer. For Rae, her life's work has always showcased diverse voices and this new collaboration is just another extension of her personal mission to prioritize overlooked voices.
"It's not easy work, but you have to kind of prioritize it," she says. "Over the last year now, especially with these racial uprisings, we've seen where so many companies are falling short. This is really the time to see how much work you've been doing since and if you're truly about that life. But what I love about LIFEWTR is they've been doing this since they started. It's something that has been core to what the company is, and I can't say the same for a lot of these other industries."
A post shared by Issa Rae (@issarae)
Last year, consumers and companies across industries called out the deeply-rooted systemic issues that continue to push marginalized communities aside. As Blavity previously reported, the Insecure creator and actress herself shared how she used her time during the protests to observe "who was on the front lines" and "who was educating other people to make a difference."
Now, she herself is showing once again how supportive she is of diverse creators and being a person of action that continues to open doors for opportunity.
"I hope to set an example, but all I can do is remain optimistic and hope that also these artists that we've featured will continue to lift others up and shine a light on them as they get opportunities," she tells Blavity about the Life Unseen campaign.
Rae also says her work doesn't solely rely on corporations and big-name companies. Everyday creatives and supporters also share the responsibility to uplift one another and continue that work ourselves.
"Don't be selfish with your opportunities, [and] don't be one of the crabs in a barrel," she says. "What's meant for you will be yours, and that's something that I've told myself constantly through my own journey."
Her latest brand endeavor also acts as a vessel for her own personal mission to extend an olive brand to help her fellow creatives reach the next step in their careers.
"I've never been shy about [saying], 'Girl did you see this opportunity,' or 'Hey this is happening here, we should take advantage of it.' Because again if it's meant for me and it's mine then it's mine, and if it's meant for you it's yours, and there's no hard feelings. When one person wins we do kind of all win, there's just not any one opportunity for everyone else."
Rae has always been a champion for her own community and uses any opportunity to pay it forward to express her love for the culture. While accepting her 2021 NAACP Image Award for Outstanding Actress in a Comedy Series for Insecure, she said the honor "means the world."
"It's the only validation that matters, is Black people's validation, so I really appreciate NAACP for honoring us. It means so much," Rae declared.


text:
Q: AS3 Video Encoding at runtime with high compression (H.264?) I need to compress video image data (lets say a display object) in AS3 to a Byte Array with high compression at runtime. Framerate only needs to be around 5 but 1024x768 video needs to go to < 40 Kilobyte per Second without the quality beeing tooo bad. I wrote a custom encoder and got it to around 80-100 Kilobyte per Second for 1024*768 which still is too much and i dont see a lot of improvements to be mad to my encoder.
Using JPG or PNG Encoder gives way higher KB/s. Is there any open source way to to decode and encode video in as3 at runtime ? E.g. a H.264 as3 encoder and decoder ? Or other codecs ?
Or maybe a C# source code of h.264 encoder and decoder ? I think i could port it to as3...
EDIT: Doesnt need to be h.264, just something with good quality when running at 5 Frames/Sec and 40 Kilobyte...

A: Flash Player 11 (beta) has H.264 encoding:

H.264/AVC SW Encoding — Encode higher quality video locally using H.264 video.

Edit: Flash Player 11 is no longer beta

A: ffmpeg is the only open source encoder/decoder I know of.  I don't think it is C#.  Due to licensing and patent issues around H.264, I'd be very surprised if an open source encoder didn't get sued into oblivion.  this is why, for example, Firefox doesn't support H.264 in their HTML5 initiative.

redpajama_set_name: RedPajamaStackExchange


Hope everyone has a great and safe 4th. And don't forget to thank a Vet!
Volunteers are never "off duty".
HAPPY INDEPENDENCE DAY!!!!! If you're going to blow stuff up please be safe about it and remember go big or go home. Most important is a HUGE THANK YOU to the men and women of our military that protects our FREEDOM, both past and present.
I had a great Fourth of July.Turned 45,grilled stuff,hung out with my niecelings,had to prove that I WASN'T grilling the pet rabbits,and generally had a good time,despite the buzzkills on the Memphis City Council who didn't spring for a fireworks show on the river this year.
It's rare that I have had the day off since I started my working life but when I do,I make sure to enjoy it because while my Navy hitch was during peacetime,there were people who died protecting our freedom and securing it for others who probably will never visit the United States of America.


Mary was born in of,Ewias,Monmouthshire,England. Mary's father was Philip Herbert Earl of Pe and her mother was Susan de Vere. Her paternal grandparents were Henry Herbert Earl of Pe and Mary Sidney ~C Pembrok. She had seven brothers and two sisters, named Henry, James, James, John, Charles, Philip, William, Anne Sophia and Catherine. She died in (unmd).


Sodium and potassium excretion in normotensive and hypertensive population in Kashmir.
Title: Sodium and potassium excretion in normotensive and hypertensive population in Kashmir.
Abstract: This study observes that hypertensive subjects showed increased levels of serum sodium, calcium, phosphorus and cholesterol as compared to normotensives .Corrections between severity of blood pressure, 24 hours urinary excretion of sodium and urinary Na/K ratio were significantly positive.


yootzletootzle has not yet been in a debate.
Post a comment to yootzletootzle's profile.
yootzletootzle does not have any Debate.org friends.
yootzletootzle has not added any photo albums.
If you are logged in, you will also see green or red bullets next to each issue, which indicate whether you agree or disagree with yootzletootzle on that particular issue.
You can also click each issue to find other members that agree with yootzletootzle's position on the issue.


text:
Q: Firebird sample database(s) recomendation for learning database design and administration My Firebird installation comes with the EMPLOYEE.fdb database to get you started. I am interested in example firebird database(s) that I can use as examples of good database design and practice admnistrative tasks with. (I have firebird 2.5 installation on a Windows 7 machine.)

A: I think IBExpert have demo DB
You can also check sakila database


text:
\section{Introduction}

Decision diagrams (DDs) encode sets of values
in compact forms, such that operations on the sets can be performed on
the encoded representation, without expanding the sets into their
individual elements.  In this paper, we consider two classes of
decision diagrams: reduced ordered binary decision diagrams (BDDs)
\cite{bryant:tc86} and zero-suppressed binary decision diagrams (ZDDs)
\cite{minato:dac93,minato:book95}.  These two representations are
closely related to each other, with each achieving more compact
representations for different classes of applications.  We present
extensions to both representations, such that BDDs can take
advantage of the source of compaction provided by ZDDs, and
vice-versa.

Both BDDs and ZDDs encode sets of binary sequences of some fixed
length $n$, defining a Boolean function over $n$ variables.  We can
bound their relative sizes as follows.  Suppose for some function, we
encode it according to the different DD types.  For
function $f$, let $T(f)$ indicate the number of nodes (including leaf
nodes) in the representation of type $T$.  Let
$\msizeratio{f}{T_1}{T_2}$ denote the relative sizes when representing
$f$ using types $T_1$ and $T_2$:
\begin{displaymath}
\begin{array}{lcl}
\msizeratio{f}{T_1}{T_2} & = & \frac{T_1(f)}{T_2(f)}
\end{array}
\end{displaymath}

Comparing BDDs and ZDDs, Knuth \cite{knuth:v4a} has shown that for any
function $f$:
\begin{eqnarray}
\sizeratio{f}{BDD}{ZDD} & \leq & n/2 + o(n) \label{eqn:bdd-zdd} \\
\sizeratio{f}{ZDD}{BDD} & \leq & n/2 + o(n) \label{eqn:zdd-bdd}
\end{eqnarray}
These bound improve on the size ratios of $n$ derived by Wegener \cite{wegener:book00}.

As these bounds show, ZDDs may be significantly (a factor of $n/2$)
more compact than BDDs, or vice-versa.  Hence, it can be critical to
choose one representation over another in a given application.  Indeed,
users of DDs often switch between the two representations during a
sequence of operations in order take advantage of their different characteristics.

\begin{figure}
\begin{center}
\includegraphics[scale=0.60]{relations}
\end{center}
\caption{{\bf Size bound relations between different representations}}
\label{fig:relations}
\end{figure}

In this paper, we introduce two new representations: {\em
  chain-reduced ordered binary decision diagrams} (CBDDs), and {\em
  chain-reduced zero-suppressed binary decision diagrams} (CZDDs).
The key idea is to associate two levels with each node and to use such
nodes to encode particular classes of linear chains found in BDDs
and ZDDs.
Chain reduction can be defined in terms of a set of
reduction rules applied to BDDs and ZDDs,
giving bounds for any function $f$
\begin{eqnarray}
\sizeratio{f}{CBDD}{BDD} & \leq & 1 \label{eqn:cbdd-bdd} \\
\sizeratio{f}{CZDD}{ZDD} & \leq & 1   \label{eqn:czdd-zdd}
\end{eqnarray}
In terms of graph sizes, using chain reduction can only lead to
more compact representations.

We show bounds on the relative sizes of the representations as:
\begin{eqnarray}
\sizeratio{f}{CBDD}{CZDD} & \leq & 3 + o(1) \label{eqn:cbdd-czdd} \\
\sizeratio{f}{CZDD}{BDD} & \leq & 2 + o(1) \label{eqn:czdd-bdd}
\end{eqnarray}
These relations are summarized in the diagram of Figure
\ref{fig:relations}.  In this figure, each arc from type $T_1$ to type
$T_2$ labeled by an expression $E$ indicates that
$\msizeratio{f}{T_1}{T_2} \leq E + o(E)$. These arcs define a transitive
relation, and so we can also infer that
\begin{eqnarray}
\sizeratio{f}{CBDD}{ZDD} & \leq & 3 + o(1) \label{eqn:cbdd-zdd}
\end{eqnarray}
These results indicate that the two compressed representations
will always be within a small constant factor (2 for CZDDs and 3 for
CBDDs) of either a BDD or a ZDD representation.
While one representation may be more slightly compact than the other,
the relative advantage is bounded by a constant factor, and hence
choosing between them is less critical.

This paper defines the two compressed representations, derives the
bounds indicated in Equations \ref{eqn:cbdd-czdd}--\ref{eqn:czdd-bdd}
and presents extensions of the core BDD and ZDD algorithms to their
chained versions.  It describes an implementation based on
modifications of the CUDD BDD package \cite{somenzi:sttt01}.  It
presents some experimental results and concludes with a discussion of
the merits of chaining and possible extensions.

\section{BDDs and ZDDs}

Both BDDs and ZDDs encode sets of binary sequences of length $n$
as directed acyclic graphs with two leaf nodes, labeled
with values $\mbox{\bf 0}$ and $\mbox{\bf 1}$, which we refer to as ``leaf $\mbox{\bf 0}$'' and ``leaf $\mbox{\bf 1}$,'' respectively.
Each nonleaf node $v$ has an
associated level $l$, such that $1 \leq l \leq n$, and two outgoing
edges, labeled $\fname{lo}$ and $\fname{hi}$ to either a leaf node or a nonleaf
node.
By convention, leaf nodes have level $n+1$.
An edge from $v$ to node $u$ having level $l'$ must have $l < l'$.

\begin{figure}[tb]
\begin{center}
\begin{picture}(6,3.54)
\put(0,3.34){(A) Levelized BDD}
\put(0.04,0){\includegraphics[scale=0.70]{eg-a}}
\put(2.00,3.34){(B) BDD}
\put(2.09,0){\includegraphics[scale=0.70]{eg-b}}
\put(4.0,3.34){(C) ZDD}
\put(4.34,0){\includegraphics[scale=0.70]{eg-d}}
\end{picture}
\end{center}
\caption{{\bf Reductions in BDDs and ZDDs}.  Each reduces the representation size with with edges between nonconsecutive levels.}
\label{fig:bdd-zdd-eg}
\end{figure}

Figure \ref{fig:bdd-zdd-eg} shows three decision-diagram
representations of the set $S$, defined as:
\begin{eqnarray}
S & = & \{ 0001, 0011, 0101, 0111, 1000\}
\label{eqn:set-example}
\end{eqnarray}
The $\fname{lo}$ edge from each node is
shown as a dashed line, and the $\fname{hi}$ edge is shown as a solid line.
As a shorthand, we omit leaf $\mbox{\bf 0}$ and all branches to it.

Graph A represents $S$ as a {\em levelized binary decision diagram},
where an edge from a node with level $l$ must connect to either
leaf $\mbox{\bf 0}$ or to a node with level $l+1$.  (This is
similar to the {\em quasi-reduced} form described by Knuth
\cite{knuth:v4a}, except that he only allows edges to leaf
$\mbox{\bf 0}$ from nodes at level $n$.)  Each path from the root to
leaf $\mbox{\bf 1}$ encodes an element of set $S$.  For a
given path, the represented sequence has value 0 at position $l$ when
the path follows the $\fname{lo}$ edge from the node with level $l$ and
value 1 when the path follows the $\fname{hi}$ edge.

Graph A has nodes forming two linear chains: a {\em \textsc{don't-care}{} chain},
consisting of nodes $a$ and $b$, and an {\em \textsc{or}{} chain},
consisting of nodes $d$, $e$, and $f$.  A \textsc{don't-care}{} chain is
a series of \textsc{don't-care}{} nodes, each having
its two outgoing edges directed to the same next node.
In terms of the set of represented binary sequences, a \textsc{don't-care}{} node with level $l$
allows both values 0 and 1 at sequence position $l$.  An \textsc{or}{} chain
consists of a sequence where the outgoing $\fname{hi}$ edges for the
nodes all go the same node---in this case, leaf $\mbox{\bf 0}$.  An \textsc{or}{} chain
where all $\fname{hi}$ edges lead to value $\mbox{\bf 0}$ has only a single
path, assigning value 0 to the corresponding positions in the
represented sequence.  We will refer to this special class of \textsc{or}{} chain as a {\em \textsc{zero}{} chain}.

BDDs and ZDDs differ from each other in the interpretations they
assign to a {\em level-skipping edge}, when a node with level $l$ has
an edge to a node with level $l'$ such that $l + 1 < l'$.  For BDDs,
such an edge is considered to encode a \textsc{don't-care}{} chain.  Thus, graph B
in Figure \ref{fig:bdd-zdd-eg} shows an BDD encoding set $S$.  The
edge on the left from level 1 to level 4 is equivalent to the
\textsc{don't-care}{} chain formed by nodes $a$ and $b$ of graph A\@.  For ZDDs, a
level skipping edge encodes a \textsc{zero}{} chain.  Thus, graph C shows a
ZDD encoding set $S$.  The edge on the right from level 1 to the leaf
encodes the \textsc{zero}{} chain formed by nodes $d$, $e$, and $f$ of graph
A\@.  Whether the set is encoded as a BDD or a ZDD, one type of
linear chains remains.  Introducing chain reduction enables BDDs
and ZDDs to exploit both \textsc{don't-care}{} and \textsc{or}{} (and
therefore \textsc{zero}{}) chains to compress their representations.

\section{Chain Patterns and Reductions}

\begin{figure}
\begin{center}
\begin{picture}(6.00,4.10)
\put(0,3.90){(A) \textsc{or}{} chain}
\put(0.02,0){\includegraphics[scale=0.60]{bdd-chain-rules-a}}
\put(2.0,3.90){(B) \textsc{don't-care}{} chain}
\put(2.16,0){\includegraphics[scale=0.60]{zdd-chain-rules-a}}
\put(4.0,3.90){(C) Compressed representation}
\put(4.18,0){\includegraphics[scale=0.60]{bdd-chain-rules-b}}
\end{picture}
\end{center}
\caption{{\bf Chain patterns}.  These patterns remain after BDD reduction (A), and ZDD reduction (B), but can be represented in compressed form (C).}
\label{fig:chain-patterns}
\end{figure}

Figure \ref{fig:chain-patterns} shows the general form of \textsc{or}{} and \textsc{don't-care}{} chains, as were illustrated in the examples of Figure
\ref{fig:bdd-zdd-eg}.  These chains have
 levels ranging from $t$ to $b$, such that
$1 \leq t < b \leq n$.  Each form consists of a linear chain of nodes
followed by two nodes $f$ and $g$ with levels greater than $b$.
Nodes $f$ and $g$ are drawn as triangles to indicate that they are the
roots of two subgraphs in the representation.
In an
\textsc{or}{} chain, the $\fname{lo}$ edge from each node is directed to the next node
in the chain, and the $\fname{hi}$ edge is directed to node $g$.  The chains
eliminated by ZDDs are a special case where $g = \mbox{\bf 0}$.
In a
\textsc{don't-care}{} chain, both the $\fname{lo}$ and the $\fname{hi}$ edges are directed
toward the next node in the chain.

As was illustrated in Figure \ref{fig:bdd-zdd-eg}, having edges that
skip levels allows BDDs to compactly represent \textsc{don't-care}{} chains and ZDDs to eliminate
\textsc{or}{} chains when $g = \mbox{\bf 0}$.  The goal of chain
reduction is to allow both forms to compactly represent both types of chains.
They do so by associating two levels with each node, as indicated in
Figure \ref{fig:chain-patterns}(C).  That is, every nonleaf node has an associated pair
of levels $\lpair{t}{b}$, such that $1 \leq t \leq b \leq n$.  In a
{\em chain-reduced ordered binary decision diagram} (CBDD), such a
node encodes the \textsc{or}{} chain pattern shown in Figure
\ref{fig:chain-patterns}(A), while in a {\em chain-reduced
  zero-suppressed binary decision diagram} (CZDD), such a node encodes
the \textsc{don't-care}{} chain pattern shown in Figure
\ref{fig:chain-patterns}(B).  A node with levels $t$ and $b$ such
that $t=b$ encodes a standard node with respect to the indicated variable.

\begin{figure}
\begin{center}
\begin{picture}(6.3,3.54)
\put(0,3.34){(A) Levelized BDD}
\put(0.09,0){\includegraphics[scale=0.75]{eg-a}}
\put(2.00,3.34){(B) CBDD}
\put(2.12,0){\includegraphics[scale=0.75]{eg-c}}
\put(4.0,3.34){(C) CZDD}
\put(4.64,0){\includegraphics[scale=0.75]{eg-e}}
\end{picture}
\end{center}
\caption{{\bf Chain Reduction Examples}.  Each now reduces both chain types.}
\label{fig:bdd-zdd-reduce-eg}
\end{figure}

Figure \ref{fig:bdd-zdd-reduce-eg} shows the effect of chain
reduction, starting with the levelized graph A\@.
In the CBDD (B), a single node $f'$ replaces the \textsc{or}{} chain consisting
of nodes $d$, $e$, and $f$.  In the CZDD (C), the \textsc{don't-care}{} chain
consisting of nodes $a$ and $b$ is incorporated into node $c$ to form
node $c'$.  These new nodes are drawn in elongated form to emphasize that
they span a range of levels, but it should be emphasized that
{\em all} nodes in a chained representation have an associated pair of levels.

\section{Generating CBDDs and CZDDs}

\begin{figure}
\begin{center}
\begin{picture}(6.30,2.95)
\put(0,2.75){(A) BDD chain reduction}
\put(0.01,0){\includegraphics[scale=0.60]{bdd-chain-rules-c}}
\put(2.10,2.75){(B) ZDD chain reduction}
\put(2.29,0){\includegraphics[scale=0.60]{zdd-chain-rules-c}}
\put(4.20,2.75){(C) Compressed representation}
\put(4.43,0){\includegraphics[scale=0.60]{bdd-chain-rules-d}}
\end{picture}
\end{center}
\caption{{\bf Chain reduction cases}.  These cases define how chain reduction can be applied to BDDs (A) and ZDDs to obtain the single chain node (C).}
\label{fig:chain-reduction}
\end{figure}

As notation, let us denote a node of the form illustrated in Figure
\ref{fig:chain-patterns}(C) with the modified if-then-else notation
$\bnode{\lpair{t}{b}}{f}{g}$.  That is, the node has a range of levels
from $t$ to $b$, an outgoing $\fname{hi}$ edge to node $g$, and an outgoing
$\fname{lo}$ edge to node $f$.

A BDD representation of a function can be transformed into a CBDD as follows.
The process starts by labeling each
node having level $l$ in the BDD with the pair $\lpair{t}{b}$, such that $t = b = l$.
Then, we repeatedly apply a {\em reduction rule}, replacing any pair of nodes $u$ and $v$ of the form
$u = \bnode{\lpair{t}{m}}{v}{g}$ and $v =
\bnode{\lpair{m+1}{b}}{f}{g}$ (illustrated in Figure
\ref{fig:chain-reduction}(A))
by the single node
$\bnode{\lpair{t}{b}}{f}{g}$ (illustrated in Figure
\ref{fig:chain-reduction}(C)).
A similar process can transfrom any ZDD representation of a function
into a CZDD, using the reduction rule that a pair of nodes $u$ and $v$ of the form
$u = \bnode{\lpair{t}{m}}{v}{v}$ and $v =
\bnode{\lpair{m+1}{b}}{f}{g}$
(illustrated in Figure
\ref{fig:chain-reduction}(B))
is replaced by the single node
$\bnode{\lpair{t}{b}}{f}{g}$ (illustrated in Figure
\ref{fig:chain-reduction}(C)).
In practice, most algorithms for constructing decision diagrams
operate from the bottom up.  The reduction rules are applied as nodes are created, and so
unreduced nodes are never actually generated.

\section{Size Ratio Bounds}

These reduction rules allows us to bound the relative sizes of the
different representations, as given by Equations \ref{eqn:cbdd-czdd} and \ref{eqn:czdd-bdd}.

First, let us consider Equation
\ref{eqn:cbdd-czdd}, bounding the relative sizes of the CBDD and CZDD
representations of a function.  Consider a graph $G$ representing
function $f$ as a CZDD\@.
We can generate a CBDD representation $G'$ as follows.  $G'$ contains
a node $v'$ for each node $v$ in $G$.  However, if $v$ has levels
$\lpair{t}{b}$, then $v'$ has levels $\lpair{b}{b}$, because any
\textsc{don't-care}{} chain encoded explicitly in the CZDD is encoded implicitly
in a CBDD\@.

Consider an edge from node $u$ to node $v$ in $G$, where the nodes
have levels $\lpair{t_u}{b_u}$ and $\lpair{t_v}{b_v}$, respectively.  If $t_v
= b_u+1$, then there can be an edge directly from $u'$ to $v'$.  If $t_v
< b_u+1$, then we introduce a new node to encode the implicit zero
chain in $G$ from $u$ to $v$.  This node
has the form
$\bnode{\lpair{b_u+1}{t_v-1}}{v'}{\mbox{\bf 0}}$ and has an edge from $u'$ to it.

The size of $G'$ is bounded by the number of nodes plus the number of
edges in $G$.  Since each node in $G$ has at most two outgoing edges,
we can see that $G'$ has at most three times the number of nodes as
$G$.  Graph $G'$ may not be reduced, but it provides an upper bound on the size of a CBDD relative to that of a CZDD\@.

\begin{figure}
\begin{center}
\begin{picture}(5.0,4.75)
\put(0.00,4.50){(A) ZDD/CZDD representation}
\put(0.40,0.00){\includegraphics[scale=0.50]{cbdd-zdd-zdd}}
\put(2.50,4.50){(B) CBDD representation}
\put(2.90,0.00){\includegraphics[scale=0.50]{cbdd-zdd}}
\end{picture}
\end{center}
\caption{{\bf Worst case example for effectiveness of CBDD compression}.
The implicit \textsc{zero}{} chains in the ZDD (A) must be explicitly encoded in the CBDD (B), increasing its size by a factor of 3.}
\label{fig:cbdd-zdd}
\end{figure}

This bound it tight---Figure \ref{fig:cbdd-zdd} illustrates the
representations for a family of functions, parameterized by a value
$k$ ($k=3$ in the example), such that the function is defined over
$3k+2$ variables.  The ZDD and CZDD representations are identical (A),
having $2k+3$ nodes (including both leaf nodes.)  The CBDD
representation has $6k+2$ nodes (B).  We can see in this example that
the CBDD requires nodes (shown in gray) to encode the \textsc{zero}{} chains that
are implicit in the ZDD\@.  To construct the graphs for different
values of $k$, the graph pattern enclosed in the diagonal boxes can
be replicated as many times as are needed.

Second, let us consider Equation \ref{eqn:czdd-bdd}, bounding the
relative sizes of the CZDD and BDD representations of a function.
Consider a graph $G$ representing function $f$ as a BDD\@.  We can
construct its representation $G'$ as a CZDD\@.  Consider each edge $G$
from node $u$, having level $l_u$ to node $v$, having level $l_v$.
Let $r = \fname{lo}(v)$ and $s = \fname{hi}(v)$.  $G'$ has a node $w_{uv}$ of
the form $\bnode{\lpair{l_u+1}{l_v}}{w_{vr}}{w_{vs}}$.  That is,
$w_{uv}$ encodes any \textsc{don't-care}{} chain between $u$ and $v$, and it
has edges to the nodes generated to encode the edges between $v$
and its two children.  The size of $G'$ is bounded by the number
of edges in $G$, which is at most twice the number of nodes.

\begin{figure}
\begin{center}
\begin{picture}(5.0,3.30)
\put(0.00,3.05){(A) BDD representation}
\put(0.40,0.00){\includegraphics[scale=0.50]{czdd-bdd-bdd}}
\put(2.50,3.05){(B) CZDD representation}
\put(2.90,0.00){\includegraphics[scale=0.50]{czdd-bdd}}
\end{picture}
\end{center}
\caption{{\bf Worst case example for effectiveness of CZDD compression}.
The nodes in the BDD (A) must be duplicated to encode the incoming \textsc{don't-care}{} chains (B), increasing the size by a factor of 2.}
\label{fig:czdd-bdd}
\end{figure}

This bound it also tight---Figure \ref{fig:czdd-bdd} illustrates the
representations for a family of functions, parameterized by a value
$k$ ($k=3$ in the example), such that the function is defined over
$2k+1$ variables.  The BDD representations (A) has
$2k+3$ nodes (including both leaf nodes.)  The CZDD
representation has $4k+3$ nodes (B).  We can see that most of the nodes in the BDD must be duplicated: once with no incoming \textsc{don't-care}{} chain, and once with a chain of length one.
To construct the graphs for different
values of $k$, the graph pattern enclosed in the diagonal boxes can
be replicated as many times as are needed.

As can be seen in Figure \ref{fig:relations}, these bounds contain an
asymmetry between BDDs and ZDDs and their compressed forms.  The bound
of 3 holds between CBDDs and CZDDs, and hence by transitivity between
CBDDs and ZDDs, while the bound of 2 holds only between CZDDs and
BDDs.  The general form of the \textsc{or}{} chain (Figure
\ref{fig:chain-patterns}(A)), where $g$ is something other than
$\mbox{\bf 0}$, cannot be directly encoded with CZDD nodes.

\section{Operating on CBDDs and CZDDs}

The \opname{apply}{} algorithms for decision diagrams operate by
recursively expanding a set of argument decision diagrams according to
a Shannon expansion of the represented functions \cite{bryant:tc86,bryant:hmc17}.  These algorithms
allow functions to be combined according to standard binary Boolean
operations, such as $\opname{and}$, $\opname{or}$, and $\opname{xor}$, as well as by the
if-then-else operation $\opname{ITE}$\@.

As notation, consider a step
that expands
$k$ argument nodes $\{v_i | 1 \leq i \leq k\}$ where $v_i = \bnode{\lpair{t_i}{b_i}}{f_i}{g_i}$.
For example, operations $\opname{and}$, $\opname{or}$, and $\opname{xor}$ use the \opname{apply}{} algorithm with
$k=2$, while ternary operations, such as $\opname{ITE}$ use $k=3$.
A step can be summarized as follows:
\begin{enumerate}
\item If one of the terminal cases apply, then return the result.
\item If the computed cache contains an entry for this combination of
  operation and arguments, then return the previously computed result.
\item Recursively compute the result:
\begin{enumerate}
\item Choose splitting level(s) based on the levels of the
  arguments.
\item Generate $\fname{hi}$ and $\fname{lo}$ cofactors for each argument.
\item Recursively compute the $\fname{hi}$ and $\fname{lo}$ values of the result using the
  \opname{apply}{} algorithm with the $\fname{hi}$ cofactors and the $\fname{lo}$ cofactors, respectively.
\item Determine the result node parameters based on the computed $\fname{hi}$
  and $\fname{lo}$ cofactors and the splitting level(s).
\item Either reuse an existing node or create a new one with the
  desired level(s) and $\fname{hi}$ and $\fname{lo}$ children.
\end{enumerate}
\item Store an entry in the computed cache.
\item Return the computed value.
\end{enumerate}
In generalizing from conventional BDDs and ZDDs to their chained
versions, we need only modify 3(a) (splitting), 3(b) (cofactoring),
and 3(d) (combining) in this sequence, considering the two levels for each node.

For CBDDs, we define the splitting levels $t$ and $b$ as:
\begin{eqnarray}
t & = & \min_{1 \leq i \leq k} t_i \label{eqn:bdd-split} \\
b & = & \min_{1 \leq i \leq k} \left \{
\begin{array}{ll}
b_i, & t_i = t \\
t_i, & t_i = n+1 \\
t_i - 1, & {\rm else} \end{array}
\right . \nonumber
\end{eqnarray}

We then define the two cofactors for each
argument node $v_i$, denoted
$\fname{lo}(v_i, \lpair{b}{t})$ and $\fname{hi}(v_i, \lpair{b}{t})$, according to the
following table:
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\makebox[0.75in]{Case} & \makebox[0.75in]{Condition}
   & \makebox[1.0in]{$\fname{lo}(v_i, \lpair{b}{t})$} & \makebox[1.0in]{$\fname{hi}(v_i, \lpair{b}{t})$} \\
\hline
1 & $b < t_i$ & $v_i$ & $v_i$ \\
2 & $b = b_i$ & $f_i$ & $g_i$ \\
3 & $t_i \leq b < b_i$ & $\bnode{\lpair{b+1}{b_i}}{f_i}{g_i}$ & $g_i$\\
\hline
\end{tabular}
\end{center}

These three cases can be explained as follows:
\begin{description}
\item[Case 1:] Splitting spans levels less than the top level of
  $v_i$.  Since level-skipping edges encode \textsc{don't-care}{} chains, both cofactors equal the original node.
\item[Case 2:] Splitting spans the same levels as node $v_i$.  The
  cofactors are therefore the nodes given by the outgoing edges.
\item[Case 3:] Splitting spans a subset of the levels covered by
  node $v_i$.  We construct a new node spanning the
  remaining part of the encoded \textsc{or}{} chain for the $\fname{lo}$ cofactor and
  have $g_i$ as the $\fname{hi}$ cofactor.
\end{description}

Recursive application of the \opname{apply}{} operation on the cofactors
generates a pair of nodes $u_{0}$ and $u_{1}$.
Using the variable levels $t$ and
$b$ defined in Equation \ref{eqn:bdd-split}, these are
combined to form a result node $u$, defined as follows:

\begin{eqnarray}
u & = &  \left  \{
\begin{array}{lll}
u_{0}, & u_{0} = u_{1} & {\rm Case~1}\\
\bnode{\lpair{t}{b'}}{w_{0}}{u_{1}}, & u_{0} =
\bnode{\lpair{b+1,b'}}{w_{0}}{u_{1}} & {\rm Case~2}\\
\bnode{\lpair{t}{b}}{u_{0}}{u_{1}}, & {\rm else} & {\rm Case~3} \label{eqn:bdd-form} \\
\end{array}
\right .
\end{eqnarray}

These three cases can be explained as follows:
\begin{description}
\item[Case 1:] The $\fname{hi}$ and $\fname{lo}$ cofactors are identical, and so
  the don't-care reduction rule can be applied.
\item[Case 2:] Chain compression can be applied to create a node that
  absorbs the $\fname{lo}$ cofactor.
\item[Case 3:] No special rules apply.
\end{description}

Similar rules hold for applying operations to CZDDs, although there
are important differences, due to the different interpretations of
level-skipping edges.

We define the splitting levels $t$ and $b$ as:
\begin{eqnarray}
t & = & \min_{1 \leq i \leq k} t_i \label{eqn:zdd-split} \\
b & = & \min_{1 \leq i \leq k} \left \{
\begin{array}{ll}
b_i, & t_i = t \\
n+1, & v_i = \mbox{\bf 0}\\
t, & {\rm else}
\end{array}
\right . \nonumber
\end{eqnarray}

The cofactors for
argument node $v_i$
are defined according to the following table:
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\makebox[0.75in]{Case} &\makebox[0.75in]{Condition} & \makebox[1.0in]{$\fname{lo}(v_i, \lpair{b}{t})$} & \makebox[1.0in]{$\fname{hi}(v_i, \lpair{b}{t})$} \\
\hline
1 & $b < t_i$ & $v_i$ & $\mbox{\bf 0}$ \\
2 & $b = b_i$ & $f_i$ & $g_i$ \\
3 & $t_i \leq b < b_i$ & $\znode{\lpair{b+1}{b_i}}{f_i}{g_i}$ & $\znode{\lpair{b+1}{b_i}}{f_i}{g_i}$ \\
\hline
\end{tabular}
\end{center}

These three cases can be explained as follows:
\begin{description}
\item[Case 1:] The splitting spans levels less than the top level of
  $v_i$.  Since level-skipping edges encode \textsc{zero}{} chains, the $\fname{lo}$
  cofactor equals the original node and the $\fname{hi}$ cofactor equals
  leaf $\mbox{\bf 0}$.
\item[Case 2:] The splitting spans the same levels as node $v_i$.  The
  cofactors are therefore the nodes given by the outgoing edges.
\item[Case 3:] The splitting spans a subset of the levels covered by
  node $v_i$.  We construct a new node spanning the
  remaining part of the encoded \textsc{don't-care}{} chain for both cofactors.
\end{description}

Recursive application of the \opname{apply}{} operation on the cofactors
generates a pair of nodes $u_{0}$ and $u_{1}$.
Using the variable ranges $t$ and
$b$ defined in Equation \ref{eqn:zdd-split}, these are
combined to form a result node $u$, defined as follows:

\begin{eqnarray}
u & = &  \left  \{
\begin{array}{lll}
u_{0}, & u_{1} = \mbox{\bf 0} \; {\rm and} \; t = b  & {\rm Case~1}\\
\bnode{\lpair{t}{b-1}}{u_{0}}{u_{0}}, & u_{1} = \mbox{\bf 0} \; {\rm and} \; t < b  & {\rm Case~2}\\
\bnode{\lpair{t}{b'}}{w_{0}}{w_{1}}, & u_{0} = u_{1} =
\bnode{\lpair{b+1,b'}}{w_{0}}{w_{1}}  & {\rm Case~3}\\
\bnode{\lpair{t}{b}}{u_{0}}{u_{1}}, & {\rm else}  & {\rm Case~4} \label{eqn:zdd-form} \\
\end{array}
\right .
\end{eqnarray}

These four cases can be explained as follows:
\begin{description}
\item[Case 1:] The zero-suppression rule can be applied to return a
  direct pointer to $u_0$
\item[Case 2:] The zero-suppression rule can be applied, but we must
  construct a node encoding the \textsc{don't-care}{} chain between levels $t$
  and $b-1$.
\item[Case 3:] Chain compression can be applied to create a node that
  absorbs the $\fname{lo}$ cofactor.
\item[Case 4:] No special rule applies.
\end{description}

\section{Implementation}

We implemented both CBDDs and CZDDs by modifying version 3.0.0 of the CUDD
BDD package \cite{somenzi:sttt01}.  When compiled for 64-bit
execution, CUDD stores a 32-bit field {\tt index} in each node, where
this index is translated into a level according to the variable
ordering.  For our implementation, we split this field into two 16-bit
fields {\tt index} and {\tt bindex} to (indirectly) encode the top and
bottom levels of the node.  Thus, there was no storage penalty for the
generalization to a chained form.

Incorporating chaining required modifications to many parts of the
code, including how node keys are generated for the unique table and
computed cache, how reductions are performed, and how Boolean
operations are applied to functions.  In addition, many of the
commonly used functions, such as computing the number of satisfying
solutions to a function, computing its support, and enumerating a
minterm representation of a function required modifications.

CUDD uses complement edges when representing BDDs
\cite{brace:dac90,minato:dac90}.  Complement edges can potentially
reduce the size of a BDD by a factor of two, invalidating the size
ratio bounds derived in Equations \ref{eqn:bdd-zdd}--\ref{eqn:zdd-bdd}
and \ref{eqn:cbdd-czdd}--\ref{eqn:czdd-bdd}.  For the experimental
results presented in the following section, we therefore use a
representation based on CUDD's support for {\em Algebraic Decision
  Diagrams} (ADDs) \cite{bahar-iccad93}.  ADDs generalize BDDs by
allowing arbitrary leaf values.  Restricting the leaf values to 0 and
1 yields conventional BDDs without complement edges.  We revisit the
use of complement edges in Section \ref{sect:complement}.

\section{Experimental Results}

We chose three different categories of benchmarks to compare the performance
of BDDs, ZDDs, and their chained versions.  One set of benchmarks
evaluated the ability of DDs to represent information in compact form,
a second to evaluate their ability to solve combinatorial
problems, and a third to represent typical digital logic functions.
All experiments were performed on a 4.2~GHz Intel Core i7 processor with 32~GB of memory
running the OS~X operating system.

\subsection{Encoding a Dictionary}

\begin{figure}
\begin{center}
\begin{tabular}{|l|r|rr|rr|}
\hline
\multicolumn{1}{|c|}{}	& \multicolumn{1}{|c|}{Words} &
\multicolumn{1}{|c}{Radix} & \multicolumn{1}{c|}{Length} &
\multicolumn{1}{|c}{One-hot variables}	& \multicolumn{1}{c|}{Binary variables} \\
\hline
Compact word list	&  235,886 	&  54 	&  24 	&  1,296 	&  144  \\
ASCII word list	&  235,886 	&  129 	&  24 	&  3,096 	&  192  \\
Compact password list	&  979,247 	&  80 	&  32 	&  2,560 	&  192  \\
ASCII password list	&  979,247 	&  129 	&  32 	&  4,128 	&  256  \\
\hline
\end{tabular}
\end{center}
\caption{Characteristics of Dictionary Benchmarks}
\label{fig:dict:properties}
\end{figure}

As others have observed \cite{knuth:v4a}, a list of words can be
encoded as a function mapping strings in some alphabet to either 1
(included in list) or 0 (not included in list.)  Strings can further
be encoded as binary sequences by encoding each symbol as a sequence
of bits, allowing the list to be represented as a Boolean function.
We consider two possible encodings of the symbols, defining the {\em
  radix} $r$ to be the number of possible symbols.  A {\em one-hot}
encoding (also referred to as a ``1-of-N'' encoding) requires $r$ bits
per symbol.  Each symbol is assigned a unique position, and the symbol
is represented with a one in this position and zeros in the rest.  A
{\em binary} encoding requires $\lceil \log_2 r \rceil$ bits per
symbol.  Each symbol is assigned a unique binary pattern, and the
symbol is represented by this pattern.  Lists consisting of words with
multiple lengths can be encoded by introducing a special ``null''
symbol to terminate each word.

Figure \ref{fig:dict:properties} shows the characteristics of eight
benchmarks derived from two word lists to allow comparisons of
different encoding techniques and representations.  The first list is the
file {\tt /usr/share/dict/words} found on Macintosh systems.  It is
derived from the word list used by the original Unix spell checker.
It contains 235,886 words with lengths ranging from one to 24 symbols,
and where the symbols consist of lower- and upper-case letters plus
hyphen.  We consider two resulting symbol sets: a {\em compact} form,
consisting of just the symbols found in the words plus a null symbol
(54 total), and an {\em ASCII} form, consisting of all 128 ASCII
characters plus a null symbol.

The second word list is from an online list of words employed by
password crackers.  It consists of 979,247 words ranging in length
from one to 32 symbols, and where the symbols include 79 possible
characters.  Again, we consider both a compact form and an ASCII form.

As Figure \ref{fig:dict:properties} shows, the choice of one-hot
vs.~binary encoding has a major effect on the number of Boolean
variables required to encode the words.  With a one-hot encoding, the
number of variables ranges between 1,296 and 4,128, while
it ranges between 144 and 256 with a binary representation.

To generate DD encodings of a word list, we first constructed a trie
representation the words and then generated Boolean formulas via a
depth-first traversal of the trie.

\begin{figure}
\begin{center}
\begin{tabular}{|l|rrr|rr|}
\cline{2-6}
\multicolumn{1}{l|}{{\bf One-hot}} &
\multicolumn{3}{|c|}{Node counts} &
\multicolumn{2}{|c|}{Ratios} \\
\cline{2-6}
\multicolumn{1}{c|}{} &
\multicolumn{1}{|c}{BDD} & \multicolumn{1}{c}{CBDD}	&
\multicolumn{1}{c|}{(C)ZDD} &
\multicolumn{1}{|c}{BDD:CBDD}	& \multicolumn{1}{c|}{CBDD:CZDD} \\
\hline
Compact word list	&  9,701,439 	&  626,070 	&  297,681 	& 15.50	& 2.10	\\
ASCII word list	&  23,161,501 	&  626,071 	&  297,681 	& 37.00	& 2.10	\\
Compact password list	&  49,231,085 	&  2,321,572 	&  1,130,729  	& 21.21	& 2.05	\\
ASCII password list	&  79,014,931 	&  2,321,792 	&  1,130,729  	& 34.03	& 2.05	\\
\hline
\multicolumn{6}{c}{} \\
\cline{2-6}
\multicolumn{1}{l|}{{\bf Binary}} &
\multicolumn{3}{|c|}{Node counts} &
\multicolumn{2}{|c|}{Ratios} \\
\cline{2-6}
\multicolumn{1}{c|}{} &
\multicolumn{1}{|c}{BDD} & \multicolumn{1}{c}{CBDD}	&
\multicolumn{1}{c|}{(C)ZDD} &
\multicolumn{1}{|c}{BDD:CBDD}	& \multicolumn{1}{c|}{CBDD:CZDD} \\
\hline
Compact word list	&  1,117,454 	&  1,007,868 	&  723,542 	& 1.11	& 1.39\\
ASCII word list	&  1,464,773 	&  1,277,640 	&  851,580 	& 1.15	& 1.50\\
Compact password list	&  4,422,292 	&  3,597,474 	&  2,506,088 	&   1.23	& 1.44	\\
ASCII password list	&  4,943,940 	&  4,307,614 	&  2,875,612 	&   1.15	& 1.50	\\
\hline
\end{tabular}
\end{center}
\caption{Node counts and ratios of node counts for dictionary benchmarks}
\label{fig:dict:counts}
\end{figure}

Figure \ref{fig:dict:counts} shows the number of nodes required to
represent word lists as Boolean functions, according to the different
lists, encodings, and DD types.  The entry labeled ``(C)ZDD'' gives the node counts for both ZDDs and CZDDs.
These are identical, because
there were no \textsc{don't-care}{} chains for these functions.
The two columns on the right show the ratios
between the different DD types.  Concentrating first on one-hot
encodings, we see that the chain compression of CBDDs reduces the size
compared to BDDs by large factors (15.50--34.03).  Compared to ZDDs,
representing the lists by CBDDs incurs some penalty (2.05--2.10), but
less than the worst-case penalty of 3.
Increasing the radix from a compact form to the full
ASCII character set causes a significant increase in BDD size, but
this effect is eliminated by using the zero suppression capabilities
of CBDDs, ZDDs, and CZDDs.

Using a binary encoding of the symbols reduces the variances between
the different encodings and DD types.  CBDDs provide only a small
benefit (1.11--1.23) over BDDs, and CBDDs are within a factor of 1.50
of ZDDs.  Again, chaining of ZDDs provides no benefit.  Observe that
for both lists, the most efficient representation is to use either
ZDDs or CZDDs with a one-hot encoding.  The next best is to use CBDDs
with a one-hot encoding, and all three of these are insensitive to
changes in radix.  These cases demonstrate the ability of ZDDS (and
CZDDs) to use very large, sparse encodings of values.  By using
chaining, CBDDs can also take advantage of this property.

\begin{figure}
\begin{center}
\begin{tabular}{|l|rrr|rrr|}
\cline{2-7}
\multicolumn{1}{l|}{{\bf One-hot}} &
\multicolumn{3}{|c|}{Operations} &
\multicolumn{3}{|c|}{Time (secs.)} \\
\cline{2-7}
\multicolumn{1}{c}{} &
\multicolumn{1}{|c}{ZDD} & \multicolumn{1}{c}{CZDD}	&
\multicolumn{1}{c|}{Ratio} &
\multicolumn{1}{|c}{ZDD} & \multicolumn{1}{c}{CZDD}	&
\multicolumn{1}{c|}{Ratio} \\
\hline
Compact word list &  142,227,877  &  12,097,435  & 1.38 & 48.78 & 15.04 & 3.24 \\
ASCII word list &  375,195,184  &  28,574,814  & 13.13 & 173.56 & 21.84 & 7.95 \\
Compact password list &  806,017,001  &  62,785,274  & 12.84 & 713.15 & 46.73 & 15.26 \\
ASCII password list &  1,383,534,557  &  104,059,626  & 13.30 & 658.21 & 57.81 & 11.39 \\
\hline
\multicolumn{7}{c}{} \\
\cline{2-7}
\multicolumn{1}{l|}{{\bf Binary}} &
\multicolumn{3}{|c|}{Operations} &
\multicolumn{3}{|c|}{Time (secs.)} \\
\cline{2-7}
\multicolumn{1}{c}{} &
\multicolumn{1}{|c}{ZDD} & \multicolumn{1}{c}{CZDD}	&
\multicolumn{1}{c|}{Ratio} &
\multicolumn{1}{|c}{ZDD} & \multicolumn{1}{c}{CZDD}	&
\multicolumn{1}{c|}{Ratio} \\
\hline
Compact word list &  15,701,738  &  1,826,171  & 8.60 &  13.11 & 9.70 & 1.35 \\
ASCII word list &  20,921,746  &  2,139,574  & 9.78 & 14.40 & 10.20 & 1.41 \\
Compact password list &  66,489,058  &  7,499,615  & 8.87 & 52.52 & 30.62 & 1.72 \\
ASCII password list &  75,556,080  &  7,936,321  & 9.52 &  50.77 & 30.33 & 1.67 \\
\hline
\end{tabular}
\end{center}
\caption{Impact of chaining on effort required to generate DD representations of word lists.}
\label{fig:dict:effort}
\end{figure}

Although the final node counts for the benchmarks indicate no
advantage of chaining for ZDDs, statistics characterizing the effort
required to derive the functions show a significant benefit.
Figure \ref{fig:dict:effort} indicates the total number of
operations and the total time required for generating ZDD and CZDD
representations of the benchmarks.  The operations are computed as the
number of times the program checks for an entry in the operation
cache (step 2 in the description of the \opname{apply}{} algorithm).
There are many operational factors that can
affect the number of operations, including the program's policies for
operation caching and garbage collection.  Nevertheless, it is some
indication of the amount of activity required to generate the DDs.  We
can see that chaining reduces the number of operations by factors of
8.87--13.30.  The time required depends on many attributes of the DD
package and the system hardware and software.  Here we see that
chaining improves the execution time by factors of 1.35--15.26.

With unchained ZDDs, many of the intermediate functions have large
\textsc{don't-care}{} chains.  For example, the ZDD representation of the function
$x$, for variable $x$, requires $n+2$ nodes---one for the variable,
$n-1$ for the \textsc{don't-care}{} chains before and after the variable, and two
leaf nodes.  With chaining, this function reduces to just four nodes:
the upper \textsc{don't-care}{} chain is incorporated into the node for the
variable, and a second node encodes the lower chain.  Our dictionary
benchmarks have as many as 4,000 variables, and so some of the
intermediate DDs can be 1,000 times more compact due to
chaining.

\subsection{The 15-Queens Problem}

A second set of benchmarks involved encoding all possible solutions to
the $n$-queens problem.  This problem attempts to place $n$ queens on
a $n\times n$ chessboard in such a way that no two queens can attack
each other.  For our benchmark we chose $n = 15$ to stay within the
memory limit of the processor being used.  Once a DD representation
has been generated for all possible solutions, it is easy to then
compute useful properties, such as the number of solutions.

Once again, there are two choices for encoding the positions of queens
on the board.  A {\em one-hot} encoding uses a Boolean variable for
each square.  A {\em binary} encoding uses $\lceil \log_2 n \rceil = 4$ variables for
each row, encoding the position of the queen within the row.

The Boolean formulas  must then impose the following constraints:
\begin{description}
\item[{\bf ROW}:] No two squares in the same row are occupied.  There
  are $n$ such constraints.  A binary encoding already imposes this constraint.
\item[{\bf COL}:] No two squares in the same column are occupied.
  There are $n$ such constraints.
\item[{\bf DIAG}:] No two squares in the same diagonal from upper left
  to lower right are occupied.  There are $2n-1$ such constraints.
\item[{\bf OFF-DIAG}:] No two squares in the same diagonal from upper
  right to lower left are occupied.  There are $2n-1$ such constraints.
\end{description}
Our most successful approach worked from the bottom row to the top.
At each level, it generated formulas for each column, diagonal, and
off-diagonal expressing whether it was occupied in the rows at or
below this one, based on the formulas for the level below and the
variables for the present row.

We considered two ways of ordering the variables for the different
rows.  The {\em top-down} ordering listed the variables according to
the row numbers 1 through 15.  The {\em center-first} ordering listed
variables according to the row number sequence
$8,9,7,10,6,11,5,12,4,13,3,14,2,15,1$.  Our hope in using this sequence
was that ordering the center rows first would reduce the DD
representation size.  This proved not to be the case, but the
resulting node counts are instructive.

\begin{figure}
\begin{center}
\begin{tabular}{|ll|rrr|rr|}
\cline{3-7}
\multicolumn{2}{l|}{{\bf One-hot}} &
\multicolumn{3}{|c|}{Node counts} &
\multicolumn{2}{|c|}{Ratios} \\
\hline
\multicolumn{1}{|c}{Ordering} & \multicolumn{1}{c|}{Graph(s)} &
\multicolumn{1}{|c}{BDD} & \multicolumn{1}{c}{CBDD}	&
\multicolumn{1}{c|}{CZDD} &
\multicolumn{1}{|c}{BDD:CBDD}	& \multicolumn{1}{c|}{CBDD:CZDD} \\
\hline
Top-down & Final &  51,889,029  &  10,529,738  &  4,796,504  & 4.93 & 2.20  \\
Top-down & Peak &  165,977,497  &  39,591,936  &  18,625,659  & 4.19 & 2.13  \\
Center-first & Final &  65,104,658  &  12,628,086  &  5,749,613  & 5.16 & 2.20  \\
Center-first & Peak &  175,907,712  &  42,045,602  &  19,434,105  & 4.18 & 2.16  \\
\hline
\multicolumn{6}{c}{} \\
\cline{3-7}
\multicolumn{2}{l|}{{\bf Binary}} &
\multicolumn{3}{|c|}{Node counts} &
\multicolumn{2}{|c|}{Ratios} \\
\hline
\multicolumn{1}{|c}{Ordering} & \multicolumn{1}{c|}{Graph(s)} &
\multicolumn{1}{|c}{BDD} & \multicolumn{1}{c}{CBDD}	&
\multicolumn{1}{c|}{CZDD} &
\multicolumn{1}{|c}{BDD:CBDD}	& \multicolumn{1}{c|}{CBDD:CZDD} \\
\hline
Top-down & Final &  13,683,076  &  11,431,403  &  7,383,739  & 1.20 & 1.55  \\
Top-down & Peak &  43,954,472  &  38,898,146  &  26,682,980  & 1.13 & 1.46  \\
Center-first & Final &  17,121,947  &  14,185,276  &  9,054,115  & 1.21 & 1.57  \\
Center-first & Peak &  46,618,943  &  41,362,659  &  28,195,596  & 1.13 & 1.47  \\
\hline
\end{tabular}
\end{center}
\caption{Node counts and ratios of node counts for 15-queens benchmarks}
\label{fig:queens:counts}
\end{figure}

Figure \ref{fig:queens:counts} shows the node counts for the different
benchmarks.  It shows both the size of the final function representing
all solutions to the 15-queens problem, as well as the peak size,
computed as the maximum across all rows of the combined size of the
functions that are maintained to express the constraints imposed by
the row and those below it.  For both the top-down and the center-first benchmarks, this maximum
was reached after completing row 3.
Typically the peak
size was around three times larger than the final size.

For a one-hot encoding, we can see that CBDDs achieve factors of
4.18--5.16 compaction over BDDs, and they come within a factor of
2.20 of CZDDs.  For a binary encoding, the levels of compaction are
much less compelling (1.13--1.20), as is the advantage of CZDDs over
BDDs.  It is worth noting that the combination of a one-hot encoding
and chaining gives lower peak and final sizes than BDDs with a binary encoding.

\begin{figure}
\begin{center}
\begin{tabular}{|ll|rr|r|}
\cline{3-5}
\multicolumn{2}{l|}{{\bf One-hot}} &
\multicolumn{2}{|c|}{Node counts} &
\multicolumn{1}{|c|}{Ratios} \\
\hline
\multicolumn{1}{|c}{Ordering} & \multicolumn{1}{c|}{Graph(s)} &
\multicolumn{1}{|c}{ZDD} & \multicolumn{1}{c|}{CZDD}	&
\multicolumn{1}{|c|}{ZDD:CZDD} \\
\hline
Top-down & Final &  4,796,504  &  4,796,504  & 1.00  \\
Top-down & Peak &  18,632,019  &  18,625,659  & 1.00  \\
Center-first & Final &  5,749,613  &  5,749,613  & 1.00  \\
Center-first & Peak &  73,975,637  &  19,434,105  & 3.81  \\
\hline
\multicolumn{5}{c}{} \\
\cline{3-5}
\multicolumn{2}{l|}{{\bf Binary}} &
\multicolumn{2}{|c|}{Node counts} &
\multicolumn{1}{|c|}{Ratios} \\
\hline
\multicolumn{1}{|c}{Ordering} & \multicolumn{1}{c|}{Graph(s)} &
\multicolumn{1}{|c}{ZDD} & \multicolumn{1}{c|}{CZDD}	&
\multicolumn{1}{|c|}{ZDD:CZDD} \\
\hline
Top-down & Final &  7,383,739  &  7,383,739  & 1.00  \\
Top-down & Peak &  26,684,315  &  26,682,980  & 1.00  \\
Center-first & Final &  9,054,115  &  9,054,115  & 1.00  \\
Center-first & Peak &  33,739,362  &  28,195,596  & 1.20 \\
\hline
\end{tabular}
\end{center}
\caption{Effect of chaining for ZDD representations of 15-queens benchmarks}
\label{fig:queens:zdd}
\end{figure}

Figure \ref{fig:queens:zdd} compares the sizes of the ZDD and CZDD
representations of the 15-queens functions.  We can see that the final
sizes are identical---there are no \textsc{don't-care}{} chains in the functions
encoding problem solutions.  For the top-down ordering, CZDDs also
offer only a small advantage for the peak requirement.  For the
center-first ordering, especially with a one-hot encoding, however, we
can see that CZDDs are significantly (3.81$\times$) more compact.  As
the construction for row 3 completes, the variables that will encode
the constraints for rows 2 and 5 remain unconstrained, yielding many
\textsc{don't-care}{} chains.  Once again, this phenomenon is much smaller with a
binary encoding.  In the end, the center-first variable ordering does
not outperform the more obvious, top-down ordering, but it was
beneficial to be able to test it.  By using chaining, CZDDs can
mitigate the risk of trying a nonoptimal variable order.

By way of comparison, Kunkle, Slavici, and Cooperman
\cite{kunkle:pasco10} also used the $n$-queens problem to test their
BDD implementation performed on a cluster of 64 machines.  They used a
one-hot encoding, but generated the formula by forming a conjunction
of all of the constraints on each single position on the board,
requiring $n^2$ constraints, each with up to $4n-4$ terms, requiring a
total of $\theta(n^3)$ Boolean operations.  In constructing a representation
of the 15-queens problem, their program reached a peak of 917,859,646
nodes, a factor of 5.5 times greater than our peak.  Our row-by-row
constraint generation requires only $\theta(n^2)$ Boolean operations, and it
significantly reduces the peak memory requirement.  Minato
described a third approach for generating constraints for the $n$-queens problem, but his
method also requires $\theta(n^3)$ operations \cite{minato:book95}.

\subsection{Digital Circuits}

\begin{figure}
\begin{center}
\begin{tabular}{|l|rrr|rr|}
\cline{2-6}
\multicolumn{1}{c|}{} &
\multicolumn{3}{|c|}{Node counts} &
\multicolumn{2}{|c|}{Ratios} \\
\hline
\multicolumn{1}{|c|}{Circuit} &
\multicolumn{1}{|c}{BDD} & \multicolumn{1}{c}{ZDD}	&
\multicolumn{1}{c|}{CZDD} &
\multicolumn{1}{|c}{ZDD:BDD}	& \multicolumn{1}{c|}{CZDD:BDD} \\
\hline
c432	&	 31,321 	&	 48,224 	&	 41,637 	&	1.54	&	1.33 \\
c499	&	 49,061 	&	 49,983 	&	 48,878 	&	1.02	&	1.00 \\
c880	&	 23,221 	&	 52,436 	&	 32,075 	&	2.26	&	1.38 \\
c1908	&	 17,391 	&	 18,292 	&	 17,017 	&	1.05	&	0.98 \\
c2670	&	 67,832 	&	 261,736 	&	 85,900 	&	3.86	&	1.27 \\
c3540	&	 3,345,341 	&	 4,181,847 	&	 3,538,982 	&	1.25	&	1.06 \\
c5315	&	 636,305 	&	 898,912 	&	 681,440 	&	1.41	&	1.07 \\
c6288	&	 48,181,908 	&	 48,331,495 	&	 48,329,117 	&	1.00	&	1.00 \\
c7552   &        4,537          &        37,689         &        4,774          &       8.31    &       1.05 \\
\hline
\end{tabular}
\end{center}
\caption{Node counts and ratios of node counts for digital circuit benchmarks}
\label{fig:circuits:counts}
\end{figure}

BDDs are commonly used in digital circuit design automation, for such
tasks as verification, test generation, and circuit synthesis.  There
ability to represent functions typically found in digital circuits has
been widely studied.  It is natural to study the suitability of
ZDDs, as well as chained versions of BDDs and ZDDs for these applications.

\hyphenation{ISCAS}

We selected the circuits from the ISCAS~'85 benchmark
suite \cite{brglez:iscas85}.  These were originally developed as
benchmarks for test generation, but they have also been widely used as
benchmarks for BDDs \cite{fujita:iccad88,malik:iccad88}.  We generated
variable orderings for all but last two benchmarks by traversing the
circuit graphs, using the fanin heuristic of \cite{malik:iccad88}.
Circuit c6288 implements a $16 \times 16$ multiplier.  For this
circuit, the ordering of inputs listed in the file provided a feasible
variable ordering, while the one generated by traversing the circuit
exceeded the memory limits of our machine.  For c7552, neither the
ordering in the file, nor that provided by traversing the graph,
generated a feasible order.  Instead, we manually generated an
ordering based on our analysis of a reverse-engineered version of the
circuit described in \cite{hansen:ieeedt99}.

Figure \ref{fig:circuits:counts} presents data on the sizes of the DDs
to represent all of the circuit outputs.  We do not present any data
for CBDDs, since these were all close in size to BDDs.  We
can see that the ZDD representations for these circuits are always
larger than the BDD representations, by factors ranging up to 8.31.
Using CZDDs mitigates that effect, yielding a maximum size ratio of
1.38.

Circuit c6288 has historical interest.  Integer multiplication is
known to be intractable for BDDs regardless of variable ordering
\cite{bryant:tc91}.  As a result, this benchmark was long considered
out of reach for a BDD representation and therefore typically omitted
from many benchmark comparisons.  With a modern machine, the benchmark
is achievable, requiring a peak of around 16~GB to represent the data
structures. On the other hand, we see that these functions contain
very few \textsc{don't-care}{} or \textsc{or}{} chains, and hence all four DD types
require around 48 million nodes to represent them.

\subsection{Observations}

These experiments, while not comprehensive, demonstrate that
chaining can allow BDDs to make use of large, sparse encodings, one of
the main strengths of ZDDs.  They also indicate that CZDDs may be the
best choice overall.  They have all of the advantages of ZDDs, while
avoiding the risk of intermediate functions growing excessively large
due to \textsc{don't-care}{} chains.  They are guaranteed to stay within a factor
of 2$\times$ of BDDs.  Even for digital circuit functions, we found
this bound to be conservative---all of the benchmarks stayed within a
factor of 1.4$\times$.

Experienced ZDD users take steps to avoid \textsc{don't-care}{} chains, for
example, by implementing special algorithms that operate directly on
ZDDs, rather than expressing a computation as a sequence of Boolean
operations \cite{knuth:v4a,yoneda:fmcad96}.  By using chaining, CZDDs reduce the cost of these chains,
enabling users to express their computations at the more abstract
level of Boolean expressions, rather than implementing special
algorithms.

\section{Complement Edges}
\label{sect:complement}

As mentioned earlier, CUDD uses complement edges in its representation
of BDDs, and
hence our experiments showed the results for ADDs.  We also
implemented CBDDs with complement edges by modifying
CUDD's implementation of BDDs.
The standard rules for deciding how to
canonicalize complement edges \cite{brace:dac90} can be used without modification with
CBDDs.
Interestingly, these rules imply that there are no \textsc{zero}{}
chains in our CBDDs, because the canonicalization forbids having a
$\fname{hi}$ pointer to leaf $\mbox{\bf 0}$.  Instead, such chains are represented by
chain nodes with the $\fname{hi}$ edges pointing to leaf $\mbox{\bf 1}$, and with
their incoming edges complemented.  Although Minato's original paper
on ZDDs \cite{minato:dac90} includes a set of conventions for using
complement edges with ZDDs, these are not implemented in CUDD\@.
Thus, we did not attempt this feature in our implementation.

\begin{figure}
\begin{center}
\begin{tabular}{|l|rr|r|}
\cline{2-3}
\multicolumn{1}{c|}{} & \multicolumn{2}{|c|}{Complement edges} &
\multicolumn{1}{|c}{} \\
\hline
\multicolumn{1}{|c|}{Metric} &
\multicolumn{1}{|c}{No} &
\multicolumn{1}{c|}{Yes} &
\multicolumn{1}{|c|}{Ratio} \\
\hline
Final size	&	 48,177,349 	&	 41,417,996 	&	1.16	\\
Operations	&	 675,645,812 	&	 272,783,843 	&	2.48	\\
Time (secs.)	&	1757	&	280	&	6.27	\\
\hline
\end{tabular}
\end{center}
\caption{Benefits of complement edges for CBDD representations of c6288 benchmark.}
\label{fig:complement}
\end{figure}

Figure \ref{fig:complement} illustrates the impact of complement edges
for CBDDs, based on the c6288 benchmark.  Similar results hold without
chaining.  As can be seen, although complement edges can potentially
yield a 2$\times$ reduction in the number of nodes, the actual
reduction is much smaller (1.16).  However, it can greatly affect the
number of operations required (2.48$\times$), since complement edges
enable complementing a function in a single step, rather than
traversing the graph. (The circuit consists mostly of \opname{nor}
gates, each requiring a complement operation.) The impact on time
(6.27$\times$) is even greater, since the large number of complement
operations pollutes the operation cache.

\section{Further Work}

Our modifications to CUDD to support chaining were only sufficient to
evaluate the basic concepts.  Fully integrating these changes into
such a complex software would require significantly more effort.
Perhaps the most challenging would be to implement dynamic variable
ordering \cite{rudell:iccad93}.  The same basic principles of dynamic
variable ordering hold for both CBDDs and CZDDs.  An exchange of
variables at levels $l$ and $l+1$ could be performed without modifying
any of the nodes with levels less than $l$ and without modifying any
external node pointers.  Special consideration must be given to nodes
with levels $\lpair{t}{b}$, such that either $t = l+1$ or $b = l$.
Many low-level details and heuristics of the
implementation would need to be altered to enable dynamic variable
ordering to work well.

\section{Acknowledgements}

This work has benefitted from conversations with Shin-Ichi Minato and Ofer Strichman.

\input{cdd-arxiv.bbl}

\end{document}

redpajama_set_name: RedPajamaArXiv


On rare occasion, the abandonment and disuse of a historic building can have a silver lining. In the case of the Balancing Rock Patrol Point at a remote site overlooking the North Fork of the Clearwater River on the Nez Perce-Clearwater National Forest, the fact that it had been forgotten by the agency may have ? in part ? contributed to its ultimate rehabilitation. This patrol point ? distinguished from a lookout at which fires would be spotted and reported ? would have likely served as temporary shelter between destinations on the forest separated by some distance. It was constructed in approximately 1935 as a standard L-6 plan Forest Service structure. It may have served an intermittent use until the mid-1950s when, like other nearby administrative sites, it was abandoned and forgotten allowing it to escape a wave of demolitions carried out by the agency. Upon ?rediscovery? by the Forest Service in the 1970s, plans for renovation began. As early as the mid-80s, a new door was constructed but never installed. Finally, in 2014, Jerry Branning and Tom Wolf, volunteers with the Forest Fire Lookout Association began a careful restoration. Over the course of 21 days, these volunteers installed a new roof, crafted new steps, built new shutters, constructed new shutter supports, and applied a new coat of paint. They installed the ?new? door built 30 years earlier. An estimated 300 hours of work at a site that necessitated packing in every piece of material resulted in a spectacular transformation. Abandonment may have allowed Balancing Rock?s eventual restoration, but let?s not assume that?s the best method for preservation. Luckily, this project and the incredible dedication of Jerry and Tom have allowed this forest landmark a new lease on life. Preservation Idaho is pleased to recognize this project with a 2015 Orchid Award for Excellence in Historic Preservation.


text:
Home>alumni
Giving a little can go a long way – Monthly donor and IHPME alumnus on why he chooses to give back
Jatinder Bains and his family have one particular tradition that they stick to when it comes to donating to a worthy cause. If someone or something has made an impact in their lives, in any way, they are compelled to… Read more about Giving a little can go a long way – Monthly donor and IHPME alumnus on why he chooses to give back
Giving back – alumni return as mentors to support growth and networking in Master of Health Informatics program
A new initiative launched by IHPME's Master of Health Informatics (MHI) program invites former alumni to return as mentors and enhance the teaching and learning experience of students in the health informatics field. "15% of our graduates responded almost immediately… Read more about Giving back – alumni return as mentors to support growth and networking in Master of Health Informatics program
An ambassador for IHPME, alumna and health care leader Lee Fairclough wins U of T Arbor Award
On October 10, University of Toronto President Meric Gertler presented over 100 volunteers with the U of T Arbor Award, a prize given to individuals who are exemplary in their dedication and service to the community. IHPME alumnus Lee Fairclough… Read more about An ambassador for IHPME, alumna and health care leader Lee Fairclough wins U of T Arbor Award
IHPME HSR Mentorship Program, One Year On
For IHPME alumni the urge to give back to the community that supported them through their graduate school years is as strong as ever. To encourage this connection, the IHPME Graduate Student Union launched a Mentorship Program directed at HSR… Read more about IHPME HSR Mentorship Program, One Year On
MHSc Graduate Wins Robert Wood Johnson Award
The 2017 Robert Wood Johnson award winner from the University of Toronto, is recent MHSc graduate Craig Thompson, who was presented with the award at a reception hosted by the Canadian College of Health Leaders (CCHL) on June 12 in… Read more about MHSc Graduate Wins Robert Wood Johnson Award


4. Shoot a frill pick into the ceiling at Huey's. This cheeky Memphis tradition combines award-winning food with an innate desire to blow sharp objects through straws. Oh, and it's not as easy as it looks.
Thanks to everyone who helped us celebrate St. Patrick's Day RIGHT this year! Here's a peak at our day. See all photos here on our Facebook page.


text:
Ships of the World
The world shipping fleet has changed more rapidly during the last fifty years than at any time in history. For centuries, the most ships were powered only by the wind and ship design changed relatively little: a seafarer from 1500 would have been able to adapt quite easily to life on board a ship in 1800. During the 19th century, however, the technological changes of the industrial revolution began to transform shipping, just as they had already changed life on land.
By 1900 steamships and diesel powered vessels were becoming more and important, but it was not until the 1930s that the days of commercial sail finally came to an end. By 1950 the largest ships in the world fleet were passenger ships ? just as they had been since the boom in Transatlantic travel and emigration in the 19th century - especially those designed for premium routes such as that from Europe to North America, where speed was essential and luxury an important selling point. Most ships in the fleet were small cargo ships, of around 10,000 gross tons and oil tankers of about the same size.
By the end of the century everything had changed. The huge passenger liners that had once dominated the oceans had nearly all gone, put out of business by airlines that could travel in hours distances that took ships days to cover. People still travelled by sea, but they did so on cruise ships for recreation or on short sea crossing, often in roll-on/roll-off ships designed to carry vehicles as well as people. The biggest ships in the world were oil tankers and bulk carriers. There were still thousands of dry cargo ships, but they were far more specialised than in the past. These different ships used in world trade are described in detail under three categories, namely, Containerships, General Cargoes and Bulk Carriers and Tankers and Passenger Ships.
Safety Regulations for Different Types of Ships
World Fleet Today
As at December 2010, today's world fleet of propelled sea-going merchant ships of no less than 100 GT comprises 103,392 ships of 958 million GT with an average age of 21 years; they are registered in over 150 nations and manned by 1.5 million seafarers of virtually every nationality.
General Cargoes and Bulk Carriers
Tankers and Passenger Ships


text:
The Sino-Indian Border War: 1962-2012
Austin Bay
Posted: Nov 21, 2012 12:01 AM
Majid Rafizadeh
In Iran, a Burning Statue Reveals Opposition's Rapid Rise
On Nov. 21, 1962, as the Indian Army continued a chaotic retreat from its high altitude positions in the Himalayan Mountains, Communist China's victorious forces halted their advance and implemented a unilateral ceasefire.
That ceasefire stopped combat operations in what we now call the 1962 Sino-Indian Border War.
That mid-20th century war, however, isn't ancient history. In fact, as East Asian and Southeast Asian maritime border quarrels escalate from rhetorical sparring to naval confrontations, the war has a frightening contemporary resonance. China is involved in the most contentious maritime border disagreements. China claims roughly 80 percent of the South China Sea and its seabed's potentially enormous mineral wealth. China's southern neighbors, particularly Vietnam and the Philippines, deny China's broad assertion of sovereignty. In September 2012, a hot-blooded, and quite senior, Chinese general said his country should prepare for war with Japan over a string of islets China calls the Diaoyus and Japan the Senkakus.
China's naval buildup and its maritime claims have drawn American media attention, but it is in the high Himalayas, in some of the world's most forbidding mountainous terrain, where Asia's nuclear-armed giants collide. Indeed, in the edgy Asia of 2012, China and India, two competitive military and economic powers with global influence, remain locked in a frozen war over a disputed border.
Optimists argue that, except for an alleged skirmish or two in the late 1960s, the fact that the Sino-Indian ceasefire has remained in effect for 50 years indicates stability. However, a ceasefire is not a negotiated, signed and ratified peace treaty. Hardline nationalists in Beijing and New Delhi continue to use different names for the disputed territory. The Chinese refer to the region as Southern Tibet. Indians call it the northern frontier of what is now Arunachal Pradesh state.
"Frozen conflict" is diplomatic slang for an unsettled but relatively localized conflict where the antagonists remain "frozen" in their political positions and neither side has the military resources or diplomatic influence to resolve the conflict on its terms. Divided Cyprus is one example. The Korean War and the Israeli-Palestinian conflict are frozen conflicts with regional and international dimensions.
Frozen conflicts may have the veneer of stability, but they are, in reality, slow wars waged by diplomatic, economic and cultural means, or hot wars on simmer, awaiting re-ignition.
Frozen war applies to the Sino-Indian conflict at a literal level. With the Himalayas as the 1962 battlefield and the still-disputed border winding over glacier and snowfields, Cold War-era gallows humorists described the Sino-Indian conflict as "the coldest war." China prepared for its 1962 attack by acclimating its assault troops to the high altitudes (14,000 feet) and training them for mountain infantry operations. China also timed its offensive to take advantage of the looming Himalayan winter. Launching the surprise attack in October meant any Indian counter-stroke would have to wait for the spring thaws.
In 1962 the war didn't quite fit the East Bloc-West Bloc paradigm. China was a nominal Soviet Russian ally. India, however, was no Western ally. India's leaders resented Great Britain and suspected the U.S. favored its rival, Pakistan. However, a Cold War echo followed the conflict: a nuclear arms race. In 1964, China detonated a nuclear device. Geo-strategists knew India would respond. India went nuclear in 1974.
The 1962 defeat still troubles the Indian military. Indian veterans of the war call it a humiliation that still stings. Several recent articles written by Indian defense analysts and a retired general or two have debated the Indian government's failure to use the Indian Air Force to stop the Chinese attack and strike Chinese support installations inside Tibet. After reading them, I was left with the distinct impression that any future Himalayan war won't be confined to border passes and garrison outposts.
Given China's and India's technological prowess, air could turn to space. In April 2012, India test-fired its new Agni intercontinental ballistic missile. If you think Pakistan was the primary audience, think again. Indian Air Force fighter-bombers already have Karachi within range. The Agni puts Beijing in the bull's-eye.
Why the Media Is About to Run Away From the Texas Synagogue
Hostage Story
Matt Vespa


Текст: Friends Season 1 Episode 16 17 "The One with Two Parts"
Friends Season 1 Episode 16 17 "The One with Two Parts"
been postdating your Friday numbers.
-lt throws my WENUS out of whack.
Weekly Estimated Net Usage Statistics.
to do anything to hurt your WENUS.
I'll take "ldiots in the Workplace"
and I'm pretty much unemployable.
Urkel in Spanish is Urkel.


text:
Dallas Startup Edition Collective to be Acquired by Men's Custom Retailer
Entrepreneur Matt Alexander will join the local company as the president and CEO of the digital division.
By Danielle Abril Published in Business & Economy October 20, 2016 7:00 am
Matt Alexander joins Raja Ratan as the two grow Q Fifty One, a Dallas menswear retailer.
After nearly four years building his Dallas fashion e-commerce company Edition Collective, Matt Alexander has found a buyer. Dallas-based men's retailer Q Fifty One on Monday approved the purchase of Alexander's startup in a cash-and-equity deal.
Financial terms of the deal were not disclosed. Q Fifty One, which owns and operates Q Clothier and Rye 51 across Dallas, Houston, Atlanta, and Oklahoma City, has appointed Alexander as the president and CEO of the newly formed division Q Fifty One Digital. The company, which employs 45 people and operates its main office out of Uptown, will also receive a list of the startup's customers and Edition Collective's intellectual property, including its iOS mobile app. Edition Collective is the umbrella company for Foremost, formerly Need, and Imprint. Foremost and Imprint, as it exists today, will shut down.
Alexander and Edition Collective's assets will help the mostly brick-and-mortar store also specialize in e-commerce. Alexander will serve as a relatively autonomous unit under the brand. He will start off with a team of five people.
"We're doing eight figures now, with profitability in the seven figures," said Raja Ratan, CEO of Q Fifty One, who self-funded the company with help from his brother and a $150,000 bank loan in 2003. "All of it is without Web. We just feel its time to bring that experience online."
Q Fifty One, which Ratan said has been profitable since its first month in business, prides itself in personalizing the shopping experience with assigned clothiers who deliver a purchase options to the customer, whether its at one of its stores or at the customer's home or workplace. Alexander is expected build on existing customer relationships and expand to new ones by creating a community and story around the brand and products, much like he did with his Edition Collective brands.
"This is an opportunity to take something that has grown so quickly and make it a household name," Alexander said one day after the agreement was signed, calling the acquisition a perfect fit. Alexander is "coming in to try to significantly bolster" the brand by taking it into the digital world.
The development came after a rough patch for Edition Collective, which had to cut 60 percent of its team in July and got locked out of its headquarters at Alto 211 in downtown Dallas. Alexander called the cut a difficult decision that was necessary to keep the company cash-flow positive. He credited the lockout to a misunderstanding.
"We had a difficult summer, but we didn't fall," he said, adding that most of the difficulties dissipated. "Our business wasn't a bad business. It was underfunded."
But shortly thereafter, the market began to change, he said. E-commerce companies Jet.com and Dollar Shave Club were both acquired in billion-dollar deals, making investors more interested in e-commerce startups. So Alexander set out to raise his next round of funding. In the process, he learned that there were new buyers looking to pickup e-commerce companies like his and received a couple of offers. The offer from Q Fifty One began with Alexander's lawyer Kevin Vela of Vela Wood, who suggested he meet with Ratan.
The two founders were already familiar with each other, as Alexander previously did business with Ratan in 2013, when he curated items Q Fifty One. The chemistry and alignment of the two brands' goals were clear, and the two began working out the details for acquisition.
Ratan says 99 percent of Q Fifty One's business comes from brick-and-mortar stores, even though the company has a website. With Alexander's expertise, Ratan expects to see a major change.
"The impact will be significant," he said, declining to release any specific projects, "both to the top line and the bottom line."
Meanwhile, Alexander says there is no guarantee for success, given the hot-and-cold nature of retail, only new opportunities. But the decision does raise an interesting question about the maturing Dallas startup community: Can a company start here, get funded, sustain itself, and also find a big exit without ever leaving the market?
"A lot of companies our age are starting to ask themselves fundamental questions," Alexander said. "What Dallas probably needs is a company with a truly lofty idea that's not [dependent] on revenue up front–something really ostentatious and ambitious."
White Rock Lake Still Isn't Getting Dredged
By Tim Rogers
DFW Restaurant Week 2019 is Coming
By Catherine Downes
Why Emma Fuhrmann Got In Trouble For Posting a Photo of a Sunset
By Zac Crain
Sugar Daddy's Cakery to Appear on Netflix's Sugar Rush
NYT Magazine Presents an Unflattering Portrayal of the Dallas Zoo's Elephant Habitat
By Shawn Shinneman
Our D CEO Weekly newsletter helps you stay up to speed with breaking news, interviews with industry leaders, and market insights from the editors of D CEO.
More from D CEO
D CEO Healthcare
D CEO Real Estate
Dallas 500
Dallas Pride
Dallas Pride Parade 2012
Staci Parks
Ghosts of Dallas: Dallas Theological Seminary, 1948
Jason Heid


AFC Bournemouth reached the FA Youth Cup fourth round for the first time since 1997 with a big 3-0 win over Hull City.
An own goal and strikes from Jaidon Anthony and Jake Scrimshaw secured Alan Connell's men passage at Vitality Stadium.
The last time the club reached the fourth round, current under-21s boss Carl Fletcher was the captain, playing alongside James Hayter.
The next round will see the under-18s face Tottenham Hotspur or Preston North End at Vitality Stadium.
Click through the best photos of an excellent night under the lights for the youth team.


text:
Gilbertiodendron robynsianum est une espèce de plantes de la famille des Fabaceae.

Publication originale
 Bulletin du Jardin Botanique de l'État à Bruxelles 27: 577. 1957.

Notes et références

Liens externes

Fabaceae
Espèce d'Angiospermes (nom scientifique)

redpajama_set_name: RedPajamaWikipedia


In this study, a novel control strategy based on Distributed Space Vector Modulation is proposed considering to improve dynamic performance of Z Source Inverter (ZSI) while obstructing high voltage stresses on inverter switches and high loss. Distributed space vector modulation lets ZSI output voltage to be controlled by Z source capacitor voltage with a simple equation. Therefore, only one voltage feedback is enough to control inverter output voltage. Furthermore, no zero state is utilized in the proposed control strategy so an additional control loop for modulation index is no longer needed. Flexible modulation index lets work with flexible dc line voltage and it makes it possible to limit voltage stresses across inverter switches so ZSI has low cost switches and also high efficiency. Moreover, the proposed control method has been investigated for both resistive and inductive loads due to ZSI load power factor depended characteristics. Effectiveness of the suggested control method is verified with Matlab/Simulink simulations considering sudden changes both in dc source and load level.
dc-ac power converters; inverters; power conditioning; power system dynamics; linear feedback control systems.
M. Mosa, O. Ellabban, A. Kouzou, A. R. Haitham, J. Rodriguez, "Model Predictive Control Applied for Quasi-Z-Source Inverter", in Applied Power Electronics Conference and Exposition, Long Beach, 2013, pp. 165-169. [Online] Available: http://dx.doi.org/10.1109/APEC.2013.6520202.