Geodesic
Proof complexities on a class of balanced formulas in some propositional systems
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 56 (2022) no. 2, pp. 58-65

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper four proof complexity characteristics for some class of balanced tautologies are investigated in two proof systems of propositional logic. One of the considered systems is based on determinative disjunctive normal form, the other on the generalization of splitting method. The optimal upper and lower bounds by logarithmic scale for all main proof complexity characteristics of considered tautologies are obtained in both systems.
Keywords: balanced tautologies, elimination system, generalized splitting system, proof complexity characteristics. 
@article{UZERU_2022_56_2_a2,
     author = {A. A. Chubaryan},
     title = {Proof complexities on a class of balanced formulas in some propositional systems},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {58--65},
     publisher = {mathdoc},
     volume = {56},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2022_56_2_a2/}
}
TY  - JOUR
AU  - A. A. Chubaryan
TI  - Proof complexities on a class of balanced formulas in some propositional systems
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2022
SP  - 58
EP  - 65
VL  - 56
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2022_56_2_a2/
LA  - en
ID  - UZERU_2022_56_2_a2
ER  - 
%0 Journal Article
%A A. A. Chubaryan
%T Proof complexities on a class of balanced formulas in some propositional systems
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2022
%P 58-65
%V 56
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2022_56_2_a2/
%G en
%F UZERU_2022_56_2_a2
A. A. Chubaryan. Proof complexities on a class of balanced formulas in some propositional systems. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 56 (2022) no. 2, pp. 58-65. http://geodesic.mathdoc.fr/item/UZERU_2022_56_2_a2/