Օբյեկտ

Վերնագիր: On Lower Bounds for Proofs Sizes in Frege Systems

Ստեղծողը:

A. A. Chubaryan ; H. A. Tamazyan

Տեսակ:

article

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

ՀՀ ԳԱԱ Զեկույցներ = Доклады НАН РА = Reports NAS RA

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

2019

Հատոր:

vol. 119

Համար:

№ 2

ISSN:

0321-1339

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

"ՀՀ ԳԱԱ Զեկույցներ"-ը հիմնադրվել են 1944թ.: Լույս են տեսնում տարին 4 անգամ

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

Ֆրեգեի համակարգերում արտածումների երկարությունների ստորին գնահատականների վերաբերյալ; О нижних оценках длин выводов в системах Фреге

Ծածկույթ:

116-121

Ամփոփում:

The trivial exponential upper bounds and only Ω(n2 ) lower bound of proof sizes and Ω(n) lower bound of proof steps for tautologies with the length n were known for Frege systems. Recently the super-linear lower bound for proof steps has been obtained by first coauthor (with Armine Chubaryan and Arman Tshitoyan. Ֆրեգեի համակարգերում n երկարությամբ նույնաբանությունների համար հայտնի էին վերին ցուցչային գնահատականը և միայն Ω(n2 ) ստորին գնահատականը արտածման երկարության համար ու Ω(n) ստորին գնահատականը արտածման քայլերի համար: Վերջերս առաջին համահեղինակի (Արմինե Չուբարյանի և Արման Ճիտոյանի համահեղինակությամբ) կողմից ստացվել էր սուպեր-գծային գնահատական արտածման քայլերի համար: Для систем Фреге были известны лишь тривиальные экспоненциальные верхние оценки и только Ω(n) нижняя оценка для количества шагов и только Ω(n ) нижняя оценка для длин выводов тавтологий длины n. Недавно первым соавтором (совместно с Армине Чубарян и Арманом Читояном) была получена суперлинейная оценка для количества шагов выводов.

Հրատարակիչ:

ՀՀ ԳԱԱ

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

2019-06-10

Ձևաչափ:

pdf

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

oai:arar.sci.am:46901

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

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

Օբյեկտի հավաքածուներ:

Վերջին անգամ ձևափոխված:

Feb 7, 2021

Մեր գրադարանում է սկսած:

Mar 5, 2020

Օբյեկտի բովանդակության հարվածների քանակ:

2

Օբյեկտի բոլոր հասանելի տարբերակները:

https://arar.sci.am/publication/52285

Ցույց տուր նկարագրությունը RDF ձևաչափով:

RDF

Ցույց տուր նկարագրությունը OAI-PMH ձևաչափով։

OAI-PMH

Հրատարակության անուն Ամսաթիվ
On Lower Bounds for Proofs Sizes in Frege Systems Feb 7, 2021

Այս էջը օգտագործում է 'cookie-ներ'։ Ավելի տեղեկատվություն