東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

VTC(0): A second-order theory for T...

Nguyen, Phuong.

Linked to FindBook

Google Book

Amazon

博客來

VTC(0): A second-order theory for TC(0).

Record Type:	Electronic resources : Monograph/item
Title/Author:	VTC(0): A second-order theory for TC(0)./
Author:	Nguyen, Phuong.
Description:	60 p.
Notes:	Source: Masters Abstracts International, Volume: 42-06, page: 2240.
Contained By:	Masters Abstracts International42-06.
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=MQ91317
ISBN:	0612913171

VTC(0): A second-order theory for TC(0).
Nguyen, Phuong.

VTC(0): A second-order theory for TC(0). - 60 p.

Source: Masters Abstracts International, Volume: 42-06, page: 2240.

Thesis (M.Sc.)--University of Toronto (Canada), 2004.

We introduce a finitely axiomatizable second-order theory VTC 0 and show that it characterizes precisely the class uniform TC0. It is simply the theory V0 [12] together with the axiom NUMONES, which states the existence of a "counting array" Y for any string X : the ith row of Y contains only the number of 1 bits upto (excluding) bit i of X. First, we introduce the notion of "strong DB1 -definability" for relations in a theory, and use the recursive properties of TC0 relations (rather than functions) to show that TC0 relations are strongly DB1 -definable, and TC0 functions are SB1 -definable in VTC0. Then, we generalize the Witnessing Theorem for V0 [12], and obtain the witnessing theorem for VTC0 from this general result: ∃SB0+ SB1 theorems of VTC0 can be witnessed by TC0 functions (here, SB0+S B1 formulas are those obtained from SB1 formulas using &and;,&or; and bounded number quantifications). Finally, we show that VTC0 is RSUV isomorphic to the first-order theory Db1 -CR, which has been claimed the "minimal" theory for TC0 [20]. This isomorphism shows that VTC0 admits the SB0+D B1 comprehension rule. Hence, in VTC0, strong DB1 -definability and the usual DB1 -definability coincide. It also follows that Db1 - CR = Db1 - CRi, for some i. This answers affirmatively an open question from [20].

ISBN: 0612913171Subjects--Topical Terms:

626642
Computer Science.

VTC(0): A second-order theory for TC(0).
LDR:02166nmm 2200265 4500 001 1847042
005 20051103093614.5
008 130614s2004 eng d
020 $a 0612913171
035 $a (UnM)AAIMQ91317
035 $a AAIMQ91317
040 $a UnM $c UnM
100 1 $a Nguyen, Phuong. $3 1271784
245 1 0 $a VTC(0): A second-order theory for TC(0).
300 $a 60 p.
500 $a Source: Masters Abstracts International, Volume: 42-06, page: 2240.
500 $a Adviser: Stephen Cook.
502 $a Thesis (M.Sc.)--University of Toronto (Canada), 2004.
520 $a We introduce a finitely axiomatizable second-order theory VTC 0 and show that it characterizes precisely the class uniform TC0. It is simply the theory V0 [12] together with the axiom NUMONES, which states the existence of a "counting array" Y for any string X : the ith row of Y contains only the number of 1 bits upto (excluding) bit i of X. First, we introduce the notion of "strong DB1 -definability" for relations in a theory, and use the recursive properties of TC0 relations (rather than functions) to show that TC0 relations are strongly DB1 -definable, and TC0 functions are SB1 -definable in VTC0. Then, we generalize the Witnessing Theorem for V0 [12], and obtain the witnessing theorem for VTC0 from this general result: ∃SB0+ SB1 theorems of VTC0 can be witnessed by TC0 functions (here, SB0+S B1 formulas are those obtained from SB1 formulas using &and;,&or; and bounded number quantifications). Finally, we show that VTC0 is RSUV isomorphic to the first-order theory Db1 -CR, which has been claimed the "minimal" theory for TC0 [20]. This isomorphism shows that VTC0 admits the SB0+D B1 comprehension rule. Hence, in VTC0, strong DB1 -definability and the usual DB1 -definability coincide. It also follows that Db1 - CR = Db1 - CRi, for some i. This answers affirmatively an open question from [20].
590 $a School code: 0779.
650 4 $a Computer Science. $3 626642
690 $a 0984
710 2 0 $a University of Toronto (Canada). $3 1017674
773 0 $t Masters Abstracts International $g 42-06.
790 1 0 $a Cook, Stephen, $e advisor
790 $a 0779
791 $a M.Sc.
792 $a 2004
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=MQ91317