We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ become syntactically identical. We first ... more >>>

This paper studies the isomorphism problem for Boolean formulas and places it precisely in the polynomial hierarchy. Two of its results are new. The first sharpens the relationship between Boolean and graph isomorphism. Chang's reduction shows only that the unrestricted Boolean isomorphism problem is GI-hard, in one direction; restricting both ... more >>>

A Boolean-weighted graph is a finite graph whose edges carry DNF formulas over a common variable set. This paper studies two isomorphism problems on such graphs, distinguished by whether the per-edge condition requires the matched edge labels to be syntactically DNF-isomorphic (BWG-ISO) or syntactically DNF non-isomorphic (BWG-NI), each over a ... more >>>