|
Zapiski Nauchnykh Seminarov POMI, 1997, Volume 241, Pages 72–96
(Mi znsl482)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
Number representations of satisfiability
G. V. Davydova, I. M. Davydovab a Institute of Transport Problems, Russian Academy of Sciences
b Saint-Petersburg State University
Abstract:
Propositional formulas are represented by real-valued matrices in such way that unsatisfiability is proved to be equivalent to stable non-negative solvability of linear algebraic systems. Complete calculus for the generation of all non-negatively solvable linear homogeneous systems is presented as consequence.
Solvability of systems of linear inequalities with real coefficients and Boolean variables is reduced to satisfiability of some formula. Alternative's theorem is proved for solvability of such systems. The technique of implicit enumeration for the search of solutions both in considering systems and in a wide range of discrete optimization problems is described.
Received: 19.02.1996
Citation:
G. V. Davydov, I. M. Davydova, “Number representations of satisfiability”, Studies in constructive mathematics and mathematical logic. Part X, Zap. Nauchn. Sem. POMI, 241, POMI, St. Petersburg, 1997, 72–96; J. Math. Sci. (New York), 98:4 (2000), 464–478
Linking options:
https://www.mathnet.ru/eng/znsl482 https://www.mathnet.ru/eng/znsl/v241/p72
|
Statistics & downloads: |
Abstract page: | 463 | Full-text PDF : | 136 |
|