A Moderately Exponential Time Algorithm for k-IBDD Satisfiability

DOI10.1007/978-3-319-21840-3_46zbMath1392.68390OpenAlexW2408681863MaRDI QIDQ3449853

Junichi Teruyama, Atsuki Nagao, Kazuhisa Seto

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21840-3_46

zbMATH Keywords

satisfiabilityindexed binary decision diagrammoderately exponential timeordered binary decision diagram

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Data structures (68P05)

Related Items (3)

Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

Cites Work

• Unnamed Item
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Mining circuit lower bound proofs for meta-algorithms
• Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Algorithms and Computation
• STACS 2004

This page was built for publication: A Moderately Exponential Time Algorithm for k-IBDD Satisfiability