The complexity of linear-time temporal logic over the class of ordinals [PDF]
Logical Methods in Computer Science, 2010 We consider the temporal logic with since and until modalities. This temporal logic is expressively equivalent over the class of ordinals to first-order logic by Kamp's theorem.
Stephane Demri, Alexander Rabinovich
doaj +4 more sources
Predicting the satisfiability of Boolean formulas by incorporating gated recurrent unit (GRU) in the Transformer framework [PDF]
PeerJ Computer ScienceThe Boolean satisfiability (SAT) problem exhibits different structural features in various domains. Neural network models can be used as more generalized algorithms that can be learned to solve specific problems based on different domain data than ...
Wenjing Chang, Mengyu Guo, Junwei Luo
doaj +3 more sources
An exactly solvable random satisfiability problem [PDF]
Journal of Physics A: Mathematical and General, 2002 We introduce a new model for the generation of random satisfiability problems. It is an extension of the hyper-SAT model of Ricci-Tersenghi, Weigt and Zecchina, which is a variant of the famous K-SAT model: it is extended to q-state variables and relates
Caracciolo, Sergio, Sportiello, Andrea
core +5 more sources
The Satisfiability Problem for Probabilistic CTL [PDF]
2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008 We study the satisfiability problem for qualitative PCTL (probabilistic computation tree logic), which is obtained from "ordinary" CTL by replacing the EX, AX, EU, and AU operators with their qualitative counterparts X > 0, X = 1, U > 0, and U = 1, respectively.
T. Brázdil +3 more
semanticscholar +3 more sources
Governance as a complex, networked, democratic, satisfiability problem [PDF]
npj ComplexityDemocratic governments comprise a subset of a population whose goal is to produce coherent decisions solving societal challenges while respecting the will of the people.
Laurent Hébert-Dufresne +8 more
doaj +2 more sources
Optimal Testing for Planted Satisfiability Problems [PDF]
Electronic Journal of Statistics, 2015 We study the problem of detecting planted solutions in a random satisfiability formula. Adopting the formalism of hypothesis testing in statistical analysis, we describe the minimax optimal rates of detection.
Berthet, Quentin
core +8 more sources
Machine Learning Methods in Solving the Boolean Satisfiability Problem [PDF]
Machine Intelligence Research, 2022 This paper reviews the recent literature on solving the Boolean satisfiability problem (SAT), an archetypal NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy ...
Wenxuan Guo +5 more
semanticscholar +1 more source
APPLICATION OF INCREMENTAL SATISFIABILITY PROBLEM SOLVERS FOR NON-DETERMINISTIC POLYNOMIAL-TIME HARD PROBLEMS AS ILLUSTRATED BY MINIMAL BOOLEAN FORMULA SYNTHESIS PROBLEM [PDF]
Научно-технический вестник информационных технологий, механики и оптики, 2020 Subject of Research. The paper considers a method for solution of the nondeterministic polynomial hard problem (NP-hard problem) of a minimal Boolean formula synthesis from a given truth table.
Konstantin I. Chukharev
doaj +1 more source
Satisfiability-Aided Language Models Using Declarative Prompting [PDF]
Neural Information Processing Systems, 2023 Prior work has combined chain-of-thought prompting in large language models (LLMs) with programmatic representations to perform effective and transparent reasoning.
Xi Ye +3 more
semanticscholar +1 more source
Register Automata with Extrema Constraints, and an Application to Two-Variable Logic [PDF]
Logical Methods in Computer Science, 2022 We introduce a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can compare those values to the suprema and infima of register values in ...
Szymon Toruńczyk, Thomas Zeume
doaj +1 more source