Počet záznamů: 1
Algebraic proofs over noncommutative formulas
- 1.
SYSNO ASEP 0374819 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Algebraic proofs over noncommutative formulas Tvůrce(i) Tzameret, Iddo (MU-W) SAI Zdroj.dok. Information and Computation. - : Elsevier - ISSN 0890-5401
Roč. 209, č. 10 (2011), s. 1269-1292Poč.str. 24 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova proof complexity ; algebraic proof systems ; frege proofs Vědní obor RIV BA - Obecná matematika CEP LC505 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000295019700001 EID SCOPUS 80052231047 DOI 10.1016/j.ic.2011.07.004 Anotace We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege, yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analog of Frege proofs, different from that given in Buss et al. (1997) and Grigoriev and Hirsch (2003). We then turn to an apparently weaker system, namely, polynomial calculus (PC) where polynomials are written as ordered formulas (PC over ordered formulas, for short). Given some fixed linear order on variables, an arithmetic formula is ordered if for each of its product gates the left subformula contains only variables that are less-than or equal, according to the linear order, than the variables in the right subformula of the gate. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2012
Počet záznamů: 1