Ամսագրի կամ հրապարակման վերնագիր:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Հրապարակման ամսաթիւ:

2008

Հատոր:

30

ISSN:

0131-4645

Լրացուցիչ տեղեկութիւն:

կապին հետեւելուն համար սեղմէ հոս

Այլ վերնագիր:

Արտածումների բարդությունների համեմատումը տարբեր տեղադրման կանոններով Ֆրեգեի համակարգում

Ծածկոյթ:

36-39

Ամփոփում:

We compare the proof complexities in Frege systems with multiple substitution rule and with constant bounded substitution rule. We prove that any two constant bounded substitution Frege systems are polynomially equivalent both by size and by steps. Frege system with multiple substitution rule and Frege system with constant bounded substitution rule are also polynomially equivalent by size, but the first system has exponential speed-up over the second system by steps.

Հրատարակիչ:

Изд-во НАН РА

Ստեղծման ամսաթիւը:

2008-09-10

Ձեւաչափ:

pdf

Նոյնացուցիչ:

oai:arar.sci.am:258554

Բնօրինակին գտնուելու վայրը:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան