東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Recursion versus Tail Recursion over...

Bhaskar, Siddharth Kasi.

Linked to FindBook

Google Book

Amazon

博客來

Recursion versus Tail Recursion over Abstract Structures.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Recursion versus Tail Recursion over Abstract Structures./
Author:	Bhaskar, Siddharth Kasi.
Description:	117 p.
Notes:	Source: Dissertation Abstracts International, Volume: 76-10(E), Section: A.
Contained By:	Dissertation Abstracts International76-10A(E).
Subject:	Logic. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3706179
ISBN:	9781321797343

Recursion versus Tail Recursion over Abstract Structures.
Bhaskar, Siddharth Kasi.

Recursion versus Tail Recursion over Abstract Structures. - 117 p.

Source: Dissertation Abstracts International, Volume: 76-10(E), Section: A.

Thesis (Ph.D.)--University of California, Los Angeles, 2015.

There are several ways to understand computability over first-order structures. We may admit functions given by arbitrary recursive definitions, or we may restrict ourselves to "iterative" functions computable by nothing more complicated than while loops.

ISBN: 9781321797343Subjects--Topical Terms:

529544
Logic.

Recursion versus Tail Recursion over Abstract Structures.
LDR:02047nmm a2200313 4500 001 2069230
005 20160510115008.5
008 170521s2015 ||||||||||||||||| ||eng d
020 $a 9781321797343
035 $a (MiAaPQ)AAI3706179
035 $a AAI3706179
040 $a MiAaPQ $c MiAaPQ
100 1 $a Bhaskar, Siddharth Kasi. $3 3184233
245 1 0 $a Recursion versus Tail Recursion over Abstract Structures.
300 $a 117 p.
500 $a Source: Dissertation Abstracts International, Volume: 76-10(E), Section: A.
500 $a Adviser: Yiannis N. Moschovakis.
502 $a Thesis (Ph.D.)--University of California, Los Angeles, 2015.
520 $a There are several ways to understand computability over first-order structures. We may admit functions given by arbitrary recursive definitions, or we may restrict ourselves to "iterative" functions computable by nothing more complicated than while loops.
520 $a In the classical case of recursion over the natural numbers, these two notions of computability coincide. However, this is not true in general. We ask whether there is a model-theoretic classification of structures over which iteration is as powerful as recursion. We give such a classification for non-locally finite structures, and examine the problem of iteration versus recursion for the locally finite structures of finite fields and finite abelian groups. Over these structures, we prove that the question of iteration versus recursion reduces to a hard open problem in computational complexity theory.
520 $a We also ask whether there are structures in which certain function may be more efficiently computable by recursion than iteration, according to some measure of complexity. We identify a family of such structures with arbitrarily large gaps in efficiency.
590 $a School code: 0031.
650 4 $a Logic. $3 529544
650 4 $a Computer science. $3 523869
650 4 $a Mathematics. $3 515831
690 $a 0395
690 $a 0984
690 $a 0405
710 2 $a University of California, Los Angeles. $b Mathematics. $3 2101079
773 0 $t Dissertation Abstracts International $g 76-10A(E).
790 $a 0031
791 $a Ph.D.
792 $a 2015
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3706179