Geodesic
Transformations of discrete functions calculation algorithms to boolean equations
The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 1, pp. 83-96
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The article is devoted to the problem of transforming algorithmic descriptions of discrete functions to their equational descriptions in the form of boolean equations. We propose an approach based on propositional encoding procedures for binary random access machine programs. These procedures are used to build transformations of high-level descriptions of discrete functions calculation algorithms to boolean equations.
Keywords: discrete functions; boolean equations; random access machines. 
@article{IIGUM_2011_4_1_a7,
     author = {I. V. Otpuschennikov and A. A. Semenov},
     title = {Transformations of discrete functions calculation algorithms to boolean equations},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {83--96},
     year = {2011},
     volume = {4},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2011_4_1_a7/}
}
TY  - JOUR
AU  - I. V. Otpuschennikov
AU  - A. A. Semenov
TI  - Transformations of discrete functions calculation algorithms to boolean equations
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2011
SP  - 83
EP  - 96
VL  - 4
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2011_4_1_a7/
LA  - ru
ID  - IIGUM_2011_4_1_a7
ER  - 
%0 Journal Article
%A I. V. Otpuschennikov
%A A. A. Semenov
%T Transformations of discrete functions calculation algorithms to boolean equations
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2011
%P 83-96
%V 4
%N 1
%U http://geodesic.mathdoc.fr/item/IIGUM_2011_4_1_a7/
%G ru
%F IIGUM_2011_4_1_a7
I. V. Otpuschennikov; A. A. Semenov. Transformations of discrete functions calculation algorithms to boolean equations. The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 1, pp. 83-96. http://geodesic.mathdoc.fr/item/IIGUM_2011_4_1_a7/

[1] A. Akho, Dzh. Khopkroft, Dzh. Ulman, Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979, 536 pp. | MR

[2] M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[3] M. A. Posypkin, O. S. Zaikin, D. V. Bespalov, A. A. Semenov, “Reshenie zadach kriptoanaliza potochnykh shifrov v raspredelennykh vychislitelnykh sredakh”, Tr. ISA RAN, 46, 2009, 119–137

[4] A. A. Semenov, “Translyatsiya algoritmov vychisleniya diskretnykh funktsii v vyrazheniya propozitsionalnoi logiki”, Prikladnye algoritmy v diskretnom analize, Diskretnyi analiz i informatika, 2, Izd-vo IGU, Irkutsk, 2008, 70–98

[5] A. A. Semenov, “O preobrazovaniyakh Tseitina v logicheskikh uravneniyakh”, Prikladnaya diskretnaya matematika, 2009, no. 4, 28–50

[6] N. A. Kolchanov, S. S. Goncharov, V. A. Likhoshvai, V. A. Ivanisenko (red.), Sistemnaya kompyuternaya biologiya, Izd.-vo SO RAN, Novosibirsk, 2008, 767 pp.

[7] A. A. Semenov, O. S. Zaikin, D. V. Bespalov, A. A. Ushakov, “SAT-podkhod v kriptoanalize nekotorykh sistem potochnogo shifrovaniya”, Vychisl. tekhnologii, 13:6 (2008), 134–150 | Zbl

[8] G. S. Tseitin, “O slozhnosti vyvoda v ischislenii vyskazyvanii”, Zap. nauch. seminarov LOMI AN SSSR, 8, 1968, 234–259

[9] S. A. Cook, “The complexity of theorem-proving procedures”, Proc. 3rd Ann. ACM Symp. on Theory of Computing, STOC 71, ACM, 1971, 151–159

[10] S. A. Cook, G. Mitchel, “Finding hard instances of the satisfiability problem: A survey”, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 35 (1997), 1–17 | MR | Zbl

[11] A. Menezes, P. Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, 657 pp.

[12] F. Massacci, L. Marraro, “Logical Cryptanalysis as a SAT Problem”, Journal of Automated Reasoning, 24:1–2 (2000), 165–203 | DOI | MR | Zbl

[13] S. Prestwich, “CNF encodings”, Handbook of Satisfiability, eds. A. Biere, M. Heule, H. van Maaren, T. Walsh, IOS Press, 2009, 75–97

[14] http://embedded.eecs.berkeley.edu/pubs/downloads/espresso