Algorithms for Constructing Computably Enumerable Sets

Kenneth J. Supowit

$125.95 $100.80

Hardback

Not in-store but you can order this
How long will it take?

Availability Information

We source books from suppliers in Australia and overseas. For books we don't currently have in stock, the time it takes to get them from our suppliers can vary widely - from a few days to a few months - so we check each book with each supplier to determine the expected time it will take to be supplied to us.

We then advise you accordingly. If the time taken to get any book is too long for you, you can let us know and we will cancel or adjust your order, and refund as required.

To find out the anticipated arrival time for specific items prior to ordering, please contact us by phone or email:

Phone +61 2 9264 3111, or 1800 4 BOOKS (1800 4 26657) if outside Sydney:
option 1 Abbey's Bookshop (Crime, History, Science, Kids & more) • info@abbeys.com.au
option 2 Language Book Centre (ESL & Foreign Languages) • language@abbeys.com.au
option 3 Galaxy Bookshop (Sci-fi, Fantasy, Romance, Graphic Novels) • sf@galaxybooks.com.au

QTY:

English

Birkhauser Verlag AG
24 May 2023

Mathematical logic; Set theory; Algorithms & data structures; Mathematical theory of computation

Series: Computer Science Foundations and Applied Logic

Logicians have developed beautiful algorithmic techniques for the construction of computably enumerable sets.  This textbook presents these techniques in a unified way that should appeal to computer scientists.

Specifically, the book explains, organizes, and compares various algorithmic techniques used in computability theory (which was formerly called ""classical recursion theory"").  This area of study has produced some of the most beautiful and subtle algorithms ever developed for any problems.  These algorithms are little-known outside of a niche within the mathematical logic community.  By presenting them in a style familiar to computer scientists, the intent is to greatly broaden their influence and appeal.

Topics and features:

·         All other books in this field focus on the mathematical results, rather than on the algorithms.

·         There are many exercises here, most of which relate to details of the algorithms.

·         The proofs involving priority trees are written here in greater detail, and with more intuition, than can be found elsewhere in the literature.

·         The algorithms are presented in a pseudocode very similar to that used in textbooks (such as that by Cormen, Leiserson, Rivest, and Stein) on concrete algorithms.

·         In addition to their aesthetic value, the algorithmic ideas developed for these abstract problems might find applications in more practical areas.

Graduate students in computer science or in mathematical logic constitute the primary audience. Furthermore, when the author taught a one-semester graduate course based on this material, a number of advanced undergraduates, majoring in computer science or mathematics or both, took the course and flourished in it.

Kenneth J. Supowit is an Associate Professor Emeritus, Department of Computer Science & Engineering, Ohio State University, Columbus, Ohio, US.

By: Kenneth J. Supowit
Imprint: Birkhauser Verlag AG
Country of Publication: Switzerland
Edition: 2023 ed.
Dimensions: Height: 235mm, Width: 155mm,
ISBN: 9783031269035
ISBN 10: 3031269039
Series: Computer Science Foundations and Applied Logic
Pages: 183
Publication Date: 24 May 2023
Audience: Professional and scholarly , Undergraduate
Format: Hardback
Publisher's Status: Active

I received an A.B. degree in linguistics from Cornell University in 1978, and a Ph. D. in computer science from the University of Illinois in 1981. Then I worked three years for Hewlett-Packard in Palo Alto, California. Subsequently, I taught for four years at Princeton University, and then 34 years at Ohio State University, where I retired in May, 2022, and now have emeritus status. Along the way, I’ve consulted for IBM, AT&T, Hewlett-Packard, and various small companies. My research has primarily been in the analysis of algorithms, however, I’ve long been fascinated by computability theory, which has been the focus of my research and much of my teaching in recent years. In Autumn, 2021, I taught a graduate level course using an earlier draft of this book as the text.

Reviews for Algorithms for Constructing Computably Enumerable Sets

“This is a concise book on the subject of computably enumerable (c.e.) sets and their constructions. … This book differs from all other textbooks in computability theory in its exercises. Instead of math-oriented problem sets, the exercises here are mostly discussions of technical details of the proofs … . This type of trial-and-error process is an essential step in learning computability as a beginner, and it is interesting to see how to explicitly emphasize it in the form of exercises.” (Mingzhong Cai, Mathematical Reviews, August, 2024) “The book is organized as a mathematics or theoretical computer science (CS) textbook. Theorems and lemmas, as well as pseudocode, demonstrate the solutions, and each chapter concludes with exercises. A very useful chapter summary describes the resultspresented in the chapter through a semiformal explanation.” (Bálint Molnár, Computing Reviews, November 15, 2023)