{'fraction_non_alphanumeric': 0.017391304347826087, 'fraction_numerical': 0.0, 'mean_word_length': 5.906666666666666, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Scalable formula decomposition for propositional satisfiability

Propositional satisfiability solving, or SAT, is an important reasoning task arising in numerous applications, such as circuit design, formal verification, planning, scheduling or probabilistic reasoning. The depth-first search DPLL procedure is in practice the most efficient complete algorithm to date. Previous studies have shown the theoretical and experimental advantages of decomposing propositional formulas to guide the ordering of variable instantiation in DPLL. However, in practice, the computation of a tree decomposition may require a considerable amount of time and space on large formulas; existing decomposition tools are unable to handle most currently challenging SAT instances because of their size. In this paper, we introduce a simple, fast and scalable method to quickly produce tree decompositions of large SAT problems. We show experimentally the efficiency of orderings derived from these decompositions on the solving of challenging benchmarks.