Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Structure of Conjugated Dienes01:16

Structure of Conjugated Dienes

6.6K
Introduction
Conjugated dienes are compounds characterized by the presence of alternating double and single bonds. In a conjugated system like 1,3-butadiene, the unhybridized 2p orbital on each carbon overlaps continuously, allowing the π electrons to be delocalized across the entire molecule. In contrast, this type of overlap does not occur in cumulated and isolated dienes, such as 2,3-pentadiene and 1,4-pentadiene, respectively. Instead, the π electrons remain localized between the double...
6.6K
Assembly of Signaling Complexes01:30

Assembly of Signaling Complexes

6.4K
Multiprotein signaling complexes are formed in a dynamic process involving protein-protein interactions at the cytoplasmic domain of transmembrane receptors or enzymatic and non-enzymatic proteins associated with the receptor. These complexes ensure the activation and propagation of intracellular signals that regulate cell functions.
Interaction domains in cell signaling
Interaction domains recognize exposed features of their binding partners containing post-translationally modified sequences,...
6.4K
Block Diagram Reduction01:22

Block Diagram Reduction

455
The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
455
Cis-regulatory Sequences02:02

Cis-regulatory Sequences

11.5K
Cis-regulatory sequences are short fragments of non-coding DNA that are present on the same chromosomes as the genes that they regulate. These fragments serve as binding sites for transcriptional regulators, proteins that are responsible for controlling gene transcription and differential gene expression across cell types in eukaryotes. Cis-regulatory sequences can be close to the gene of interest or thousands of bases away in the DNA sequence; however, those sequences that are further away are...
11.5K
Cis-regulatory Sequences02:02

Cis-regulatory Sequences

3.9K
3.9K
Methods of Documentation V: CBE01:23

Methods of Documentation V: CBE

1.3K
Charting by Exception, or CBE, is a method of documentation used in healthcare, particularly in nursing, that focuses on documenting only significant or abnormal findings rather than recording every detail. This approach aims to streamline the documentation process, improve efficiency, and ensure that healthcare providers can quickly identify deviations from normalcy in patient assessments.
In CBE, healthcare professionals establish predefined standards of practice that define what constitutes...
1.3K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Long-Distance Q-Resolution with Dependency Schemes.

Journal of automated reasoning·2019
Same journal

FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees.

Theory of computing systems·2026
Same journal

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths.

Theory of computing systems·2026
Same journal

The Ground-Set-Cost Budgeted Maximum Coverage Problem.

Theory of computing systems·2025
Same journal

Rudin-Shapiro Sums Via Automata Theory and Logic.

Theory of computing systems·2025
Same journal

Prediction and MDL for infinite sequences.

Theory of computing systems·2024
Same journal

On Polynomial Recursive Sequences.

Theory of computing systems·2024
See all related articles

Related Experiment Video

Updated: Dec 29, 2025

Hierarchical and Programmable One-Pot Oligosaccharide Synthesis
09:56

Hierarchical and Programmable One-Pot Oligosaccharide Synthesis

Published on: September 6, 2019

7.2K

On Compiling Structured CNFs to OBDDs.

Simone Bova1, Friedrich Slivovsky1

  • 1Institute of Computer Graphics and Algorithms, TU Wien, 1040 Vienna, Austria.

Theory of Computing Systems
|February 7, 2020
PubMed
Summary
This summary is machine-generated.

We show that variable convex CNF formulas have polynomial Ordered Binary Decision Diagram (OBDD) size. Conversely, we establish an exponential lower bound for OBDD representations of certain bounded-degree CNF formulas.

Keywords:
Conjunctive normal formExpander graphsKnowledge compilationOrdered binary decision diagram

More Related Videos

Author Spotlight: Alignment of Synchronized Time-Series Data Using the Characterizing Loss of Cell Cycle Synchrony Model for Cross-Experiment Comparisons
07:59

Author Spotlight: Alignment of Synchronized Time-Series Data Using the Characterizing Loss of Cell Cycle Synchrony Model for Cross-Experiment Comparisons

Published on: June 9, 2023

1.8K
Design and Synthesis of a Reconfigurable DNA Accordion Rack
07:44

Design and Synthesis of a Reconfigurable DNA Accordion Rack

Published on: August 15, 2018

7.4K

Related Experiment Videos

Last Updated: Dec 29, 2025

Hierarchical and Programmable One-Pot Oligosaccharide Synthesis
09:56

Hierarchical and Programmable One-Pot Oligosaccharide Synthesis

Published on: September 6, 2019

7.2K
Author Spotlight: Alignment of Synchronized Time-Series Data Using the Characterizing Loss of Cell Cycle Synchrony Model for Cross-Experiment Comparisons
07:59

Author Spotlight: Alignment of Synchronized Time-Series Data Using the Characterizing Loss of Cell Cycle Synchrony Model for Cross-Experiment Comparisons

Published on: June 9, 2023

1.8K
Design and Synthesis of a Reconfigurable DNA Accordion Rack
07:44

Design and Synthesis of a Reconfigurable DNA Accordion Rack

Published on: August 15, 2018

7.4K

Area of Science:

  • Computer Science
  • Logic in Computer Science
  • Computational Complexity

Background:

  • Ordered Binary Decision Diagrams (OBDDs) are crucial for representing Boolean functions.
  • Understanding the size of OBDD representations for different classes of CNF formulas is key to efficient computation.

Purpose of the Study:

  • To analyze the OBDD representation size for structurally characterized classes of CNF formulas.
  • To identify conditions that guarantee polynomial OBDD size and establish lower bounds for others.

Main Methods:

  • Introducing and utilizing the 'few subterms' property to identify classes with polynomial OBDD size.
  • Leveraging the combinatorial properties of expander graphs to prove exponential lower bounds.

Main Results:

  • Variable convex CNF formulas are shown to have polynomial OBDD size.
  • An exponential lower bound on OBDD size is proven for a family of CNF formulas with bounded-degree incidence graphs.

Conclusions:

  • The 'few subterms' property is a sufficient condition for polynomial OBDD size in CNF formulas.
  • Structural properties of incidence graphs, such as convexity and bounded degree, significantly impact OBDD representation size.