%{search_type} search results

• 1. Boolean Functions
• 2. Circuit Lower Bounds
• Circuit Upper Bounds
• 4. Randomness and Satisfiability
• 5. Propositional Proof Systems
• 6. Machine Models and Function Algebras
• 7. Higher Types
• References.
• (source: Nielsen Book Data)

This textbook presents a survey of research on boolean functions, circuits, parallel computation models, function algebras, and proof systems. Its main aim is to elucidate the structure of "fast" parallel computation. The complexity of parallel computation is emphasized through a variety of techniques ranging from finite combinatorics, probability theory and finite group theory to finite model theory and proof theory. Nonuniform computation models are studied in the form of boolean circuits; uniform ones in a variety of forms. Steps in the investigation of non-deterministic polynomial time are surveyed as is the complexity of various proof systems. The book will benefit advanced undergraduates and graduate students as well as researchers in the field of complexity theory.
(source: Nielsen Book Data)

• Series Preface
• Preface
• Molecular Biology
• Math Primer
• Sequence Alignment
• All About Eve
• Hidden Markov Models
• Structure Prediction
• Appendix A: Mathematical Background
• Appendix B: Resources
• References
• Index.
• (source: Nielsen Book Data)

• Molecular Biology
• Math Primer
• Sequence Alignment
• All About Eve
• Hidden Markov Models
• Structure Prediction
• Appendices
• References
• Index.
• (source: Nielsen Book Data)

Recently molecular biology has undergone unprecedented development generating vast quantities of data needing sophisticated computational methods for analysis, processing and archiving. This requirement has given birth to the truly interdisciplinary field of computational biology, or bioinformatics, a subject reliant on both theoretical and practical contributions from statistics, mathematics, computer science and biology. Provides the background mathematics required to understand why certain algorithms work Guides the reader through probability theory, entropy and combinatorial optimization In--depth coverage of molecular biology and protein structure prediction Includes several less familiar algorithms such as DNA segmentation, quartet puzzling and DNA strand separation prediction Includes class tested exercises useful for self--study Source code of programs available on a Web site Primarily aimed at advanced undergraduate and graduate students from bioinformatics, computer science, statistics, mathematics and the biological sciences, this text will also interest researchers from these fields.
(source: Nielsen Book Data)

• Preface
• 1. Open Problems
• 2. Note on the Existence of Most General Semi-unifiers
• 3. Kreisel's Conjecture for L31 (including a postscript by George Kreisel)
• 4. Number of Symbols in Frege Proofs with and without the Deduction Rule
• 5. Algorithm for Boolean Formula Evolution and for Tree Contraction
• 6. Provably Total Functions in Bounded Arithmetic Theories Ri3, Ui2 and Vi2
• 7. On Polynomial Size Frege Proofs of Certain Combinatorial Principles
• 8. Interpretability and Fragments of arithmetic
• 9. Abbreviating Proofs Using Metamathematical Rules
• 10. Open Induction, Tennenbaum Phenomena, and Complexity Theory
• 11. Using Herbrand-type Theorems to Separate Strong Fragments of Arithmetic
• 12. An Equivalence between Second Order Bounded Domain Bounded Arithmetic and First Order Bounded Arithmetic
• 13. Integer Parts of Real Closed Exponential Fields (extended abstract)
• 14. Making Infinite Structures Finite in Models of Second Order Bounded Arithmetic
• 15. Ordinal Arithmetic in I
• 16. RSUV Isomorphism
• 17. Feasible Interpretability.
• (source: Nielsen Book Data)

This book principally concerns the rapidly growing area of what might be termed "Logical Complexity Theory", the study of bounded arithmetic, propositional proof systems, length of proof, etc and relations to computational complexity theory. Issuing from a two-year NSF and Czech Academy of Sciences grant supporting a month-long workshop and 3-day conference in San Diego (1990) and Prague (1991), the book contains refereed articles concerning the existence of the most general unifier, a special case of Kreisel's conjecture on length-of-proof, propositional logic proof size, a new alternating logtime algorithm for boolean formula evaluation and relation to branching programs, interpretability between fragments of arithmetic, feasible interpretability, provability logic, open induction, Herbrand-type theorems, isomorphism between first and second order bounded arithmetics, forcing techniques in bounded arithmetic, ordinal arithmetic in L D o . Also included is an extended abstract of J P Ressayre's new approach concerning the model completeness of the theory of real closed exponential fields. Additional features of the book include (1) the transcription and translation of a recently discovered 1956 letter from K Godel to J von Neumann, asking about a polynomial time algorithm for the proof in k-symbols of predicate calculus formulas (equivalent to the P-NP question), (2) an OPEN PROBLEM LIST consisting of 7 fundamental and 39 technical questions contributed by many researchers, together with a bibliography of relevant references.
(source: Nielsen Book Data)

• On the existence of modulo p cardinality functions, Miklos Ajtai
• predicative recursion and the polytime hierarchy, Stephen Bellantoni
• are there hard examples for Frege systems?, Maria Luisa Bonet et al
• Goedel's theorems on lengths of proofs II - lower bounds for recognizing k symbol provability, Samuel R. Buss
• feasibilty categorical Abelian groups, Douglas Cenzer and Jeffrey Remmel
• first order bounded arithmetic and small boolean circiut complexity classes, Peter Clote and Gaisi Takeuti
• parametized computational feasibility, Rodney G. Downey and Micheal R. Fellows
• on proving lower bounds for circuit size, Mauricio Karchmer
• effective properties of finitely generated RE algebras, Bakhadyr Khoussainov and Aail Nerode
• on Frege and extended Frege proof systems, Jan Krajicek
• ramified recurrence and computational complexity I - word recurrence and poly-time, Daniel Leivant
• bounded arithmetic and lower bounds in boolean complexity, Alexander A. Razborov
• ordinal bounds for programs, Helmut Schwichtenberg and Stanley S. Wainer
• Turing machine characterizations of feasible functionals of all finite types, Anil Seth
• the complexity of feasible interpretability, Rineke Verbrugge.
• (source: Nielsen Book Data)

In computational applications, an algorithm may solve a given problem, but be "infeasible" in practice because it requires large time and space resources. A "feasible" algorithm requires a "small" amount of time and/or memory and can be implemented on an abstract computational device such as a Turing machine or a boolean circuit. In investigating feasible algorithms, a wide variety of tools from combinatorics, logic, computational complexity theory and algebra can be employed. The purpose of the workshop on which this volume is based was to carry on the work of the first "Feasible Mathematics" workshop, held in 1989. Both workshops were held at Cornell University and sponsored by the University and Mathematics Sciences Institute. This volume contains contributions to feasible mathematics in three areas: computational complexity theory, proof theory and algebra, with substantial overlap between different fields. Among the topics covered are: boolean circuit lower bounds, novel characteristics of various boolean and sequential complexity classes, fixed-parameter tractability, higher order feasible functionals, higher order programs related to Plotkin's PCF, combinatorial proofs of feasible length, bounded arithmetic, feasible interpretations, polynomial time categoricity, and algebraic properties of finitely generated recursively enumerable algebras.
(source: Nielsen Book Data)

This book constitutes the refereed proceedings of the 13th International Workshop on Computer Science Logic, CSL 2000, held in Fischbachau, Germany as the 8th Annual Conference of the EACSL in August 2000. The 28 revised full papers presented together with eight invited papers were carefully reviewed and selected by the program committee. Among the topics covered are automated deduction, theorem proving, categorical logic, term rewriting, finite model theory, higher order logic, lambda and combinatory calculi, computational complexity, logic programing, constraints, linear logic, modal logic, temporal logic, model checking, formal specification, formal verification, program transformation, etc.
(source: Nielsen Book Data)