Kooperativer Bibliotheksverbund

UID:

Format: 447 p. , online resource.

ISBN: 9781461225669

Series Statement: Progress in Computer Science and Applied Logic ; 13

Content: Perspicuity is part of proof. If the process by means of which I get a result were not surveyable, I might indeed make a note that this number is what comes out - but what fact is this supposed to confirm for me? I don't know 'what is supposed to come out' . . . . 1 -L. Wittgenstein A feasible computation uses small resources on an abstract computa­ tion device, such as a 'lUring machine or boolean circuit. Feasible math­ ematics concerns the study of feasible computations, using combinatorics and logic, as well as the study of feasibly presented mathematical structures such as groups, algebras, and so on. This volume contains contributions to feasible mathematics in three areas: computational complexity theory, proof theory and algebra, with substantial overlap between different fields. In computational complexity theory, the polynomial time hierarchy is characterized without the introduction of runtime bounds by the closure of certain initial functions under safe composition, predicative recursion on notation, and unbounded minimization (S. Bellantoni); an alternative way of looking at NP problems is introduced which focuses on which pa­ rameters of the problem are the cause of its computational complexity and completeness, density and separation/collapse results are given for a struc­ ture theory for parametrized problems (R. Downey and M. Fellows); new characterizations of PTIME and LINEAR SPACE are given using predicative recurrence over all finite tiers of certain stratified free algebras (D.

Note: Preface -- On the Existence of modulo p Cardinality Functions -- Predicative Recursion and The Polytime Hierarchy -- Are there Hard Examples for Frege Systems? -- On Godel’s Theorems on Lengths of Proofs II: Lower Bounds for Recognizing k Symbol Provability -- Feasibly Categorical Abelian Groups -- First Order Bounded Arithmetic and Small Boolean Circuit Complexity Classes -- Parameterized Computational Feasibility -- On Proving Lower Bounds for Circuit Size -- Effective Properties of Finitely Generated R.E. Algebras -- On Frege and Extended Frege Proof Systems -- Ramified Recurrence and Computational Complexity I: Word Recurrence and Poly-time -- Bounded Arithmetic and Lower Bounds in Boolean Complexity -- Ordinal Bounds for Programs -- Turing Machine Characterizations of Feasible Functionals of All Finite Types -- The Complexity of Feasible Interpretability.

In: Springer eBooks

Additional Edition: Printed edition: ISBN 9781461275824

Language: English

Keywords: Konferenzschrift

DOI: 10.1007/978-1-4612-2566-9

URL: http://dx.doi.org/10.1007/978-1-4612-2566-9

URL: Volltext

UID:

Format: XIV, 816 p. , online resource.

ISBN: 9781461203254

Series Statement: Progress in Computer Science and Applied Logic ; 12

Content: The twenty-six papers in this volume reflect the wide and still expanding range of Anil Nerode's work. A conference on Logical Methods was held in honor of Nerode's sixtieth birthday (4 June 1992) at the Mathematical Sciences Institute, Cornell University, 1-3 June 1992. Some of the conference papers are here, but others are from students, co-workers and other colleagues. The intention of the conference was to look forward, and to see the directions currently being pursued, in the development of work by, or with, Nerode. Here is a brief summary of the contents of this book. We give a retrospective view of Nerode's work. A number of specific areas are readily discerned: recursive equivalence types, recursive algebra and model theory, the theory of Turing degrees and r.e. sets, polynomial-time computability and computer science. Nerode began with automata theory and has also taken a keen interest in the history of mathematics. All these areas are represented. The one area missing is Nerode's applied mathematical work relating to the environment. Kozen's paper builds on Nerode's early work on automata. Recursive equivalence types are covered by Dekker and Barback, the latter using directly a fundamental metatheorem of Nerode. Recursive algebra is treated by Ge & Richards (group representations). Recursive model theory is the subject of papers by Hird, Moses, and Khoussainov & Dadajanov, while a combinatorial problem in recursive model theory is discussed in Cherlin & Martin's paper. Cenzer presents a paper on recursive dynamics.

Note: The Work of Anil Nerode: A Retrospective -- Embedding Distributive Lattices Preserving 1 Below A Nonzero Recursively Enumerable Turing Degree -- Prime Isols and the Theorems of Fermat and Wilson -- Problem Solving Strategies for the Derivation of Programs -- Effective Real Dynamics -- An Integer Lattice Arising in the Model Theory of Wreath Products -- Undecidability and Definability for Parametrized Polynomial Time m-Reducibilities -- Extracting Programs from Proofs by an Extension of the Curry-Howard Process -- A Bird’s-Eye View of Twilight Combinatorics -- Effectively and Noneffectively Nowhere Simple Subspaces -- Index Sets in Recursive Combinatorics -- Computability in Unitary Representations of Compact Groups -- Recursive Properties of Intervals of Recursive Linear Orders -- Algorithmic Stability of Models -- The Combinatorics of the Friedberg-Muchnick Theorem -- Partial Automata and Finitely Generated Congruences: An Extension of Nerode’s Theorem -- Minimal Pair Constructions and Iterated Trees of Strategies -- Intuitionistic L -- n-Recursive Linear Orders Without (n + 1)-Recursive Copies -- Multiple Agent Autonomous Control — A Hybrid Systems Architecture -- Distributed Concurrent Programs as Strategies in Games -- Dempster-Shafer Logic Programs and Stable Semantics -- Who Put the “Back” in Back-and-Forth? -- Polynomial Time Categoricity and Linear Orderings -- The Disjunction and Numerical Existence Properties for Intuitionistic Analysis -- On the Strength of Fraïssé’s Conjecture.

In: Springer eBooks

Additional Edition: Printed edition: ISBN 9781461267089

Language: English

Keywords: Bibliografie ; Konferenzschrift ; Konferenzschrift ; Festschrift

DOI: 10.1007/978-1-4612-0325-4

URL: http://dx.doi.org/10.1007/978-1-4612-0325-4

URL: Volltext

UID:

Format: 1 online resource (239 p.)

Edition: Reprint 2014

ISBN: 9783110807486 , 9783110637199

Series Statement: De Gruyter Series in Logic and Its Applications , 2

Note: Frontmatter -- , Preface -- , Table of contents -- , Priority method in generalized computability -- , Polynomial-time versus computable Boolean algebras -- , The proof-theoretic strength of the Dushnik-Miller Theorem for countable linear orders -- , Effectively nowhere simple relations on computable structures -- , Jump traces with large gaps -- , Weak recursive degrees and a problem of Spector -- , Compositions of permutations and algorithmic reducibilities -- , Some properties of majorant-computability -- , Hyperarithmetical functions and algebraicity -- , Weak presentations of fields not extendible to recursive presentations -- , Jumps of Ʃ02-high e-degrees and properly Ʃ02 e-degrees -- , Enumeration reducibility and the problem of the nontotal property of e-degrees -- , Algebras of recursive functions -- , Σ2 Induction and cuppable degrees -- , Open problems -- , List of talks -- , List of contributors -- , Backmatter , Issued also in print. , Mode of access: Internet via World Wide Web. , In English.

In: DGBA Mathematics - 1990 - 1999, De Gruyter, 9783110637199

Additional Edition: ISBN 9783110165876

Language: English

Subjects: Mathematics

DOI: 10.1515/9783110807486

URL: https://doi.org/10.1515/9783110807486

URL: https://www.degruyter.com/isbn/9783110807486

URL: Cover