On tseitin formulas, read-once branching programs and treewidth
From MaRDI portal
Publication:2043884
DOI10.1007/s00224-020-10007-8OpenAlexW2954150872MaRDI QIDQ2043884
Ludmila Glinskih, Dmitry Itsykson
Publication date: 3 August 2021
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-020-10007-8
Artificial intelligence (68Txx) Theory of computing (68Qxx) Proof theory and constructive mathematics (03Fxx)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the read-once property of branching programs and CNFs of bounded treewidth
- Satisfiability, branch-width and Tseitin tautologies
- Graph minors. V. Excluding a planar graph
- Quickly excluding a planar graph
- Cops-robber games and the resolution of Tseitin formulas
- Tree-width, path-width, and cutwidth
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- On Tseitin formulas, read-once branching programs and treewidth
- Excluded Grid Theorem
- Polynomial Bounds for the Grid-Minor Theorem
- Hard examples for resolution
- Branching Programs and Binary Decision Diagrams
- On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables
- Search Problems in the Decision Tree Model
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
- Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
- Treewidth in Verification: Local vs. Global
- Principles and Practice of Constraint Programming – CP 2004
