Počet záznamů: 1

Simulating non-prenex cuts in quantified propositional calculus

  1. 1.
    0364309 - MU-W 2012 RIV DE eng J - Článek v odborném periodiku
    Jeřábek, Emil - Nguyen, P.
    Simulating non-prenex cuts in quantified propositional calculus.
    Mathematical Logic Quarterly. Roč. 57, č. 5 (2011), s. 524-532 ISSN 0942-5616
    Grant CEP: GA AV ČR IAA100190902; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: proof complexity * prenex cuts * quantified propositional calculus
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.496, rok: 2011
    http://onlinelibrary.wiley.com/doi/10.1002/malq.201020093/abstract

    We show that the quantified propositional proof systems G_i are polynomially equivalent to their restricted versions that require all cut formulas to be prenex Sigma^q_i (or prenex Pi^q_i). Previously this was known only for the treelike systems G^*_i.
    Trvalý link: http://hdl.handle.net/11104/0199828
    Název souboruStaženoVelikostKomentářVerzePřístup
    Jerabek2.pdf1119.4 KBVydavatelský postprintvyžádat