Zobrazeno 1 - 10
of 300
pro vyhledávání: '"Frege system"'
Autor:
Arai, Toshiyasu
In this paper we introduce a system AID (Alogtime Inductive Definitions) of bounded arithmetic. The main feature of AID is to allow a form of inductive definitions, which was extracted from Buss' propositional consistency proof of Frege systems F. We
Externí odkaz:
http://arxiv.org/abs/math/9809205
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Universitat Politècnica de Catalunya (UPC)
We define and investigate Frege systems for quantified Boolean formulas (QBF). For these new proof systems, we develop a lower bound technique that directly lifts circuit lower bounds for a circuit class C to the QBF Frege system operating with lines
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b1a71059526abcfaa4d32b866518de6d
https://doi.org/10.1145/3381881
https://doi.org/10.1145/3381881
Autor:
Raheleh Jalali
In this paper, we investigate the proof complexity of a wide range of substructural systems. For any proof system $\mathbf{P}$ at least as strong as Full Lambek calculus, $\mathbf{FL}$, and polynomially simulated by the extended Frege system for some
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aa0490ac2b040f9e05b6e5275259c407
http://arxiv.org/abs/2006.09705
http://arxiv.org/abs/2006.09705
Autor:
Samuel R. Buss
Publikováno v:
Outstanding Contributions to Logic ISBN: 9783030714291
We discuss substitution rules that allow the substitution of formulas for formula variables. A substitution rule was first introduced by Frege. More recently, substitution is studied in the setting of propositional logic. We state theorems of Urquhar
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1826ee7f4610e8ad7298e88a78a900f3
https://doi.org/10.1007/978-3-030-71430-7_17
https://doi.org/10.1007/978-3-030-71430-7_17
Publikováno v:
Journal of the ACM. Mar2020, Vol. 67 Issue 2, p1-36. 36p.
Autor:
Pavel Pudlák
The canonical pair of a proof system P is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have P-proofs bounded by some polynomial. We give a combinatorial characteri
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::94c6a4f52cc8f21e1500e0366d13ec1d
http://arxiv.org/abs/1912.03013
http://arxiv.org/abs/1912.03013
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Aleksanyan, S. R.1 sonush@rambler.ru, Chubaryan, A. A.2 achubaryan@ysu.am
Publikováno v:
Siberian Mathematical Journal. Mar2009, Vol. 50 Issue 2, p193-198. 6p.
Autor:
Moniri, Morteza1,2 ezmoniri@ipm.ir
Publikováno v:
Mathematical Logic Quarterly. Jan2005, Vol. 51 Issue 1, p73-76. 4p.