Satisfiability algorithm for syntactic read-\(k\)-times branching programs
type: Item
instance of: scholarly article
title: Satisfiability algorithm for syntactic read-\(k\)-times branching programs
zbMATH Open document ID: 1506.68039
author: Atsuki Nagao
author: Kazuhisa Seto
author: Junichi Teruyama
published in: Theory of Computing Systems
publication date: 2021-06-11T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68R07
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 7357730
zbMATH Keywords: branching program
zbMATH Keywords: read-\(k\)-times
zbMATH Keywords: satisfiability
zbMATH Keywords: moderately exponential time
zbMATH Keywords: polynomial space
MaRDI profile type: Publication
full work available at URL: s00224-020-09996-3
OpenAlex ID: W3044773971
cites work: Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Time-space tradeoffs for branching programs
cites work: Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
cites work: On lower bounds for read-\(k\)-times branching programs
cites work: Mining circuit lower bound proofs for meta-algorithms
cites work: Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
cites work: The Shrinkage Exponent of de Morgan Formulas is 2
cites work: Q5743451
cites work: A note on read-$k$ times branching programs
cites work: A nondeterministic space-time tradeoff for linear codes
cites work: A Moderately Exponential Time Algorithm for k-IBDD Satisfiability
cites work: Q4484662
cites work: Q3281059
cites work: Q4542589
cites work: Improving exhaustive search implies superpolynomial lower bounds
DOI: 10.1007/S00224-020-09996-3
description: scientific article; zbMATH DE number 7357730