Subrecursive programming systems : complexity & succinctness
著者
書誌事項
Subrecursive programming systems : complexity & succinctness
（Progress in theoretical computer science）
Birkhäuser, 1994
- :us
- :sz
大学図書館所蔵 件 / 全19件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references and index
内容説明・目次
- 巻冊次
-
:us ISBN 9780817637675
内容説明
1.1. What This Book is About This book is a study of * subrecursive programming systems, * efficiency/program-size trade-offs between such systems, and * how these systems can serve as tools in complexity theory. Section 1.1 states our basic themes, and Sections 1.2 and 1.3 give a general outline of the book. Our first task is to explain what subrecursive programming systems are and why they are of interest. 1.1.1. Subrecursive Programming Systems A subrecursive programming system is, roughly, a programming language for which the result of running any given program on any given input can be completely determined algorithmically. Typical examples are: 1. the Meyer-Ritchie LOOP language [MR67,DW83], a restricted assem- bly language with bounded loops as the only allowed deviation from straight-line programming; 2. multi-tape 'lUring Machines each explicitly clocked to halt within a time bound given by some polynomial in the length ofthe input (see [BH79,HB79]); 3. the set of seemingly unrestricted programs for which one can prove 1 termination on all inputs (see [Kre51,Kre58,Ros84]); and 4. finite state and pushdown automata from formal language theory (see [HU79]). lOr, more precisely, the collection of programs, p, ofsome particular general-purpose programming language (e.
g., Lisp or Modula-2) for which there is a proof in some par- ticular formal system (e.g., Peano Arithmetic) that p halts on all inputs.
目次
1 Introduction.- 1.1 What This Book is About.- 1.1.1 Subrecursive Programming Systems.- 1.1.2 Relative Succinctness Trade-offs.- 1.1.3 The Toolkit.- 1.2 Outline of Part I. A Subrecursion Programming Systems Toolkit.- 1.3 Outline of Part II. Program Succinctness.- 1.4 Brief History of Prior Results.- 1.5 How to Use This Book.- 1.6 Acknowledgments.- I A Subrecursion Programming Systems Toolkit.- 2 Basic Notation and Definitions.- 2.1 Equation Numbering.- 2.2 General Notation and Conventions.- 2.3 The Standard Pairing Function.- 2.4 Representing Numbers.- 2.5 Of Lengths and Logarithms.- 2.6 Classes of Sets and Functions.- 2.7 Programming Systems and Numberings.- 2.8 Complexity Measures.- 2.9 The Arithmetic Hierarchy.- 2.10 Formal Systems.- 3 Deterministic Multi-tape Turing Machines.- 3.1 Details of the Model.- 3.1.1 TM Conventions.- 3.1.2 Coding TMs.- 3.1.3 The Standard Acceptable Programming System and Complexity Measures.- 3.1.4 The Complexity of Basic Functions and Operations..- 3.1.5 Standard Complexity Classes.- 3.1.6 Efficient Universal Simulation.- 3.2 Costs of Combining Turing Machines and Efficiency of the Combinations.- 3.2.1 TM Normalization.- 3.2.2 Clocked TMs.- 3.2.3 Combining TMs.- 3.2.4 Slowed Simulations.- 4 Programming Systems.- 4.1 Closure Properties and Control Structures.- 4.1.1 Formalizing the Notion of a Control Structure.- 4.1.2 Building Control Structures.- 4.2 Clocked Programming Systems.- 4.2.1 Formalizations.- 4.2.2 Constructing Clocked Systems.- 4.2.3 Inherited Properties of Clocked Systems.- 4.2.4 Clocked Systems for Collections of Sets.- 4.3 Provably Bounded Programming Systems.- 4.3.1 Provably Explicitly Bounded Systems.- 4.3.2 Provably Implicitly Bounded Systems.- 4.4 Reducibility Induced Programming Systems.- 4.4.1 Induced Systems and Their Properties.- 4.4.2 The Generality of Induced Systems.- 5 The LOOP Hierarchy.- 6 The Poly-Degree Hierarchy.- 7 Delayed Enumeration and Limiting Recursion.- 7.1 Uniform Enumerations.- 7.2 Limiting Recursion.- 7.3 Uniform Limits.- 8 Inseparability Notions.- 8.1 Productiveness and Related Notions.- 8.2 ?n-Inseparability.- 8.3 ?n-Inseparability.- 9 Toolkit Demonstrations.- 9.1 Uniform Density.- 9.2 A Generalization of Uniform Density.- 9.3 Upper Bounds on Upward Chains.- 9.4 Minimal Pairs.- 9.5 Sufficient Conditions for Effective ?2-Inseparability.- II Program Succinctness.- 10 Notions of Succinctness.- 10.1 Program Size.- 10.2 Relative Succinctness: Definitions.- 10.3 Invariances and Limitations.- 10.3.1 Invariance with Respect to Program Size Measures..- 10.3.2 Limits on Succinctness.- 10.3.3 Invariance Under Choice of Programming Systems ..- 10.3.4 Programming Systems That Represent Classes of Sets.- 11 Limiting-Recursive Succinctness Progressions.- 11.1 A Technical Prelude.- 11.2 The Key Theorem.- 11.3 A Cornucopia of Corollaries.- 11.4 A Tight Incompleteness Theorem about Complexity Bounds.- 11.5 Characterizations of Limiting-Recursive Succinctness.- 12 Succinctness for Finite and Infinite Variants.- 12.1 The =m Case.- 12.2 Considerations for the =* and =? Cases.- 12.3 The =* Case.- 12.4 The =? Case.- 13 Succinctness for Singleton Sets.- 13.1 Progressions for Clocked Systems.- 13.2 Succinctness for Programs with Provable Complexity.- 14 Further Problems.- Appendix A Exercises.- Appendix B Solutions for Selected Exercises.- Notation Index.
- 巻冊次
-
:sz ISBN 9783764337674
内容説明
This text develops the theory of subrecursive programming systems and applies it to the more general theory of structural complexity theory. Its first goal is to establish relative program succinctness between systems, improving and subsuming most prior results in this area and introducing several forms of the phenomena. Its second goal is to illustrate the applicability of these tools in the context of structural complexity theory. This book is suitable for researchers aquainted with the theory of computation and comfortable with mathematical proofs. It can also be used by computer science and mathematics advanced undergraduates and graduates.
目次
- What this book is about - subrecursive programming systems, relative succinctness trade-offs, the toolkit
- outline of Part I - a subrecursion programming systems toolkit
- outline of Part II - program succinctness
- brief history of prior results
- how to use this book
- acknowledgments. Part 1 A subrecursion programming systems toolkit: basic notation and definitions - equation numbering, general notation and conventions, the standard pairing function, representing numbers, of lengths and logarithms, classes of sets and functions, programming systems and numberings, complexity measures, the arithmetic hierarchy, formal systems
- deterministic multi-tape turing machines - details of the model - TM conventions, coding TMs, the standard acceptable programming system and complexity measures, the complexity of basic functions and operations, standard complexity classes
- efficient universal simulation, costs of combining turing machines and efficiency of the combinations, TM normalisation
- clocked TMs, combining TMs
- slowed simulations
- programming systems - closure properties and control structures, formalising the notion of a control structure, building control structures, clocked programming systems, formalizations, constructing clocked systems, inherited properties of clock systems, clocked systems for collections of sets, provably bounded programming systems, provably explicitly bounded systems, provably implicitly bounded systems, reducibility induced programming systems, induced systems and their properties, the generality of induced systems
- the LOOP hierarchy
- the poly-degree hierarchy
- delayed enumeration and limiting recursion - uniform enumerations, limiting recursion, uniform limits
- inseparability notions - productiveness and related notions, an-inseparability, en-inseparability
- toolkit demonstrations: uniform density, a generalisation of uniform density, upper bounds on upward chains, minimal pairs, sufficient conditions for effective E2-inseparability. Part 2 Program succinctness: notions of succinctness - program size, relative succinctness - definitions, invariances and limitations, invariance with respect to program size measures, limits on succinctness, invariance under choice of programming systems, programming systems that represent classes of sets
- limiting-recursive succinctness progressions - a technical prelude, the key theorem, a cornucopia of corollaries, a tight incompleteness theorem about complexity bounds, characterisations of limiting-recursive succinctness
- succinctness for finite and infinite variant - the =m case, considerations for the =* and =x cases, the =* case, the =x case
- succinctness for singleton sets - progressions for clocked systems, succinctness for programs with provable complexity
- further problems. Appendices: exercises
- solutions for selected exercises. Subject Index.
「Nielsen BookData」 より
