Series Overview
The book series Theory and Applications of Computability is published by Springer
in cooperation with the Association Computability in Europe.
Books published in this series will be of interest to the research community and graduate students, with a
unique focus on issues of computability. The perspective of the series is multidisciplinary, recapturing the
spirit of Turing by linking theoretical and real-world concerns from computer science, mathematics, biology,
physics, and the philosophy of science.
The series includes research monographs, advanced and graduate texts, and books that offer an original
and informative view of computability and computational paradigms.
Volume 12
Gleb Beliakov , Simon James , Jianzhang Wu
Choquet Capacities and Fuzzy Integrals
1st Edition., 2025
Hardcover, ISBN 978-3-031-97069-6
Choquet capacities, which provide the weighting mechanism for the Choquet and other fuzzy integrals,
model synergistic and antagonistic interactions between variables by assigning value to all subsets rather than individual inputs.
While the flexibility of capacities (also referred to as fuzzy measures and cooperative games) comes
at the expense of an exponentially increasing number of parameters, the ability to explain their
behavior using various value and interaction indices makes them appealing for applications requiring
transparency and interpretability. As well as a number of useful indices that in some way capture the
extent to which positive and negative interactions occur, significant progress has been made in
addressing the scalability issues that arise in applications. This book provides a detailed overview
of the background concepts relating to capacities and their role in fuzzy integration and aggregation,
then presents specialised chapters on most recent results in learning, random sampling and optimization
that involve Choquet capacities.
Topics and features:
- Fundamentals of Choquet capacities (fuzzy measures) and their use in modeling importance and interaction between variables
- Definitions, properties and mappings between alternative representations that allow capacities and fuzzy integrals to be interpreted and applied in different settings
- Various simplification assumptions, from k-additive, p-symmetric and l-measures to more recent concepts such as k-interactive and hierarchical frameworks
- Capacity learning formulations that allow the diverse types to be elicited from datasets or according to user-specified requirements
- Recent findings related to random sampling and optimisation with Choquet integral objectives
This book includes illustrative examples and guidance for implementation, including an appendix detailing
functions found in the pyfmtools software library. It aims to be useful for practitioners and researchers
in decision and data-driven fields, or those who wish to apply these emerging tools to new problems.
|
|
Volume 11
Rodney G. Downey,
Alexander G. Melnikov
Computable Structure Theory
A Unified Approach
1st Edition., 2025
Hardcover, ISBN 978-3-031-92432-3
This is the first book which gives a unified theory for countable and uncountable computable structures.
The work treats computable linear orderings, graphs, groups and Boolean algebras unified with computable
metric and Banach spaces, profinite groups, and the like. Further, it provides the first account of these
that exploits effective versions of dualities, such as Stone and Pontryagin dualities. The themes are
effective classification and enumeration.
Topics and features:
- Delivers a self-contained, gentle introduction to priority arguments, directly applying them in algebraic contexts
- Includes extensive exercises that both cement and amplify the materials
- Provides complete introduction to the basics of computable analysis, particularly in the context of computable structures
- Offers the first monograph treatment of computable Polish groups, effective profinite groups via Stone duality, and effective abelian groups via Pontryagin duality
- Presents the first book treatment of Friedberg enumerations of structures
This unique volume is aimed at graduate students and researchers in computability theory, as well as mathematicians seeking to
understand the algorithmic content of structure theory. Being self-contained, it provides ample opportunity for self-study.
|
|
Volume 10
Friedrich Otto
Restarting Automata
Extensions and Generalizations
1st Edition., 2025, XVI, 313 p.
Hardcover, ISBN 978-3-031-78700-3
See below.
|
|
Volume 9
Friedrich Otto
Restarting Automata
The Standard Type of Restarting Automaton and Its Variants
1st Edition., 2024, VIII, 409 p.
Hardcover, ISBN 978-3-031-70093-4
The subject of this monograph are restarting automata. The definition of these automata is motivated by
the linguistic technique of analysis by reduction. This technique, which can be used to analyze sentences
in natural languages with a rather free word-order like Czech (or Latin or German), consists of a sequence
of step-by-step simplifications of a given sentence. Each of these simplifications is realized by a single
reduction operation, which consists of either the deletion of one or several words from that sentence or
the replacement of a (possibly discontinuous) substring of that sentence by a shorter substring.
It is required that each application of such a reduction operation must preserve the syntactical correctness
of the sentence. Accordingly, a restarting automaton consists of a finite-state control, a flexible tape
that initially contains the input, and a read-write window of a fixed finite size that works on that tape.
The first type of restarting automaton was presented at the international conference FCT in 1995.
This type was required to restart as soon as it executes a rewrite operation, that is, the window jumps back
to the left end of the tape and the finite-state control is reset to the initial state. Moreover, each
rewrite operation simply deletes one or more letters from the contents of the read-write window. Subsequently,
many different variants of the restarting automaton have been defined and studied. In particular, proper
length-reducing rewrite operations have replaced the original delete steps, additional non-input letters,
called auxiliary letters, have been added to the alphabet, and the original combined rewrite/restart
operation has been split into a rewrite operation and a separate restart operation. Thus, the restarting
automaton is no longer just a particular type of automaton, but it has evolved into a whole family of
various types of automata that are specified through several parameters. The objective of the current
monograph is to collect the many results that have been obtained on the various types of restarting
automata in one place and to present them in a uniform and systematic way. In particular, the influence
of the various parameters on the expressive capacity of the resulting types of restarting automata is
studied in detail. Other topics include the descriptional complexity and inductive inference of certain
types of restarting automata, cooperating distributed and parallel communicating systems of restarting
automata, restarting automata with output, weighted restarting automata, and restarting automata for
picture languages and tree languages. This monograph may serve as a book of reference for researchers
working in formal language and automata theory, as a guide to the literature on restarting automata,
and as a text book for an advanced undergraduate or graduate course in formal language and automata
theory.
Topics and features:
- Offers a comprehensive survey of restarting automata and results generated from them
- Presents systematically the various types of restarting automata
- Provides extremely complete reference lists, for maximum utility
|
|
Volume 8
Dusko Pavlovic
Programs as Diagrams
From Categorical Computability to Computable Categories
1st Edition., 2023, XVII, 252 p.
Hardcover, ISBN 978-3-031-34826-6
It is not always clear what computer programs mean in the various languages in which they can be written,
yet a picture can be worth 1000 words, a diagram 1000 instructions.
In this unique textbook/reference, programs are drawn as string diagrams in the language of categories,
which display a universal syntax of mathematics (Computer scientists use them to analyze the program semantics;
programmers to display the syntax of computations). Here, the string-diagrammatic depictions of computations
are construed as programs in a single-instruction programming language. Such programs as diagrams show how
functions are packed in boxes and tied by strings. Readers familiar with categories will learn about the
foundations of computability; readers familiar with computability gain access to category theory.
Additionally, readers familiar with both are offered many opportunities to improve the approach.
Topics and features:
- Delivers a ‘crash’ diagram-based course in theory of computation
- Uses single-instruction diagrammatic programming language
- Offers a practical introduction into categories and string diagrams as computational tools
- Reveals how computability is programmability, rather than an ‘ether’ permeating computers
- Provides a categorical model of intensional computation is unique up to isomorphism
- Serves as a stepping stone into research of computable categories
In addition to its early chapters introducing computability for beginners,
this flexible textbook/resource also contains both middle chapters that expand for suitability
to a graduate course as well as final chapters opening up new research.
|
|
|
Editorial Board
Founding Editors: P. Bonizzoni, V. Brattka, S.B. Cooper, E. Mayordomo
Proposals
Formal or informal book proposals can be
sent directly to members of the editorial board
(contact details are on the linked web pages above).
Series Advisory Board
- Samson Abramsky (Oxford, UK)
- Eric Allender (Rutgers, New Jersey, USA)
- Klaus Ambos-Spies (Heidelberg, Germany)
- Giorgio Ausiello (Rome, Italy)
- Jeremy Avigad (Carnegie Mellon, Pittsburgh, USA)
- Samuel R. Buss (California, San Diego, USA)
- Rodney G. Downey (Wellington, New Zealand)
- Sergei S. Goncharov (Novosibirsk, Russia)
- Peter Jeavons (Oxford, UK)
- Nataša Jonoska (South Florida, Tampa, USA)
- Ulrich Kohlenbach (Darmstadt, Germany)
- Ming Li (Waterloo, Canada)
- Wolfgang Maass (Graz, Austria)
- Grzegorz Rozenberg (Leiden, The Netherlands and Colorado, USA)
- Alan Selman (Buffalo, New York, USA)
- Wilfried Sieg (Carnegie Mellon, Pittsburgh, USA)
- Jan van Leeuwen (Utrecht, The Netherlands)
- Klaus Weihrauch (Hagen, Germany)
- Philip Welch (Bristol, UK)
Series
Volume 7
Damir D. Dzhafarov,
Carl Mummert
Reverse Mathematics
Problems, Reductions, and Proofs
1st Edition., 2022, X, 480 p. 20 illus.
Hardcover, ISBN 978-3-031-11366-6
Reverse mathematics studies the complexity of proving mathematical theorems and solving mathematical problems.
Typical questions include: Can we prove this result without first proving that one? Can a computer solve this
problem? A highly active part of mathematical logic and computability theory, the subject offers beautiful
results as well as significant foundational insights.
This text provides a modern treatment of reverse mathematics that combines computability theoretic reductions
and proofs in formal arithmetic to measure the complexity of theorems and problems from all areas of mathematics.
It includes detailed introductions to techniques from computable mathematics, Weihrauch style analysis, and
other parts of computability that have become integral to research in the field.
Topics and features:
- Provides a complete introduction to reverse mathematics, including necessary background from computability theory, second order arithmetic, forcing, induction, and model construction
- Offers a comprehensive treatment of the reverse mathematics of combinatorics, including Ramsey's theorem, Hindman's theorem, and many other results
- Provides central results and methods from the past two decades, appearing in book form for the first time and including preservation techniques and applications of probabilistic arguments
- Includes a large number of exercises of varying levels of difficulty, supplementing each chapter
The text will be accessible to students with a standard first year course in mathematical logic.
It will also be a useful reference for researchers in reverse mathematics, computability theory, proof theory, and related areas.
|
|
Volume 6
Vasco Brattka,
Peter Hertling (Eds.)
Handbook of Computability and Complexity in Analysis
1st Edition., 2021, XXIV, 426 p. 23 illus.
Hardcover, ISBN 978-3-030-59233-2
Computable analysis is the modern theory of computability and complexity in analysis that arose out of Turing's seminal work in the 1930s.
This was motivated by questions such as: which real numbers and real number functions are computable,
and which mathematical tasks in analysis can be solved by algorithmic means?
Nowadays this theory has many different facets that embrace topics from computability theory, algorithmic randomness, computational complexity,
dynamical systems, fractals, and analog computers, up to logic, descriptive set theory, constructivism, and reverse mathematics.
In recent decades computable analysis has invaded many branches of analysis, and researchers have studied computability and complexity questions
arising from real and complex analysis, functional analysis, and the theory of differential equations, up to (geometric) measure theory and topology.
This handbook represents the first coherent cross-section through most active research topics on the more theoretical side of the field.
It contains 11 chapters grouped into parts on computability in analysis; complexity, dynamics, and randomness; and constructivity, logic,
and descriptive complexity. All chapters are written by leading experts working at the cutting edge of the respective topic.
Researchers and graduate students in the areas of theoretical computer science and mathematical logic will find systematic introductions
into many branches of computable analysis, and a wealth of information and references that will help them to navigate the modern research
literature in this field.
|
|
Volume 5
S. Barry Cooper,
Mariya Soskova (Eds.)
The Incomputable
Journeys Beyond the Turing Barrier
1st Edition., 2017, X, 292 p. 10 illus.
Hardcover, ISBN 978-3-319-43667-8
This book questions the relevance of computation to the physical universe. Our theories deliver computational descriptions,
but the gaps and discontinuities in our grasp suggest a need for continued discourse between researchers from different disciplines,
and this book is unique in its focus on the mathematical theory of incomputability and its relevance for the real world.
The core of the book consists of thirteen chapters in five parts on extended models of computation; the search for natural
examples of incomputable objects; mind, matter, and computation; the nature of information, complexity, and randomness;
and the mathematics of emergence and morphogenesis.
This book will be of interest to researchers in the areas of theoretical computer science, mathematical logic, and philosophy.
|
|
Volume 4
Robert I. Soare
Turing Computability
Theory and Applications
1st Edition., 2016, XXXVI, 263 p. 4 illus.
Hardcover, ISBN 978-3-642-31932-7
Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine.
This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute.
This book presents classical computability theory from Turing and Post to current results and methods,
and their use in studying the information content of algebraic structures, models, and their relation to Peano arithmetic.
The author presents the subject as an art to be practiced, and an art in the aesthetic sense of inherent beauty which
all mathematicians recognize in their subject.
|
|
Volume 3
Dag Normann,
John Longley
Higher Order Computability
1st Edition., 2015, X, 575 p. 2 illus.
Hardcover, ISBN 978-3-662-47991-9
This book offers a self-contained exposition of the theory of computability in a higher-order context,
where 'computable operations' may themselves be passed as arguments to other computable operations.
The subject originated in the 1950s with the work of Kleene, Kreisel and others, and has since expanded
in many different directions under the influence of workers from both mathematical logic and computer science.
The ideas of higher-order computability have proved valuable both for elucidating the constructive content
of logical systems, and for investigating the expressive power of various higher-order programming languages.
|
|
Volume 2
Douglas S. Bridges,
Luminiţa Simona Vîţă
Apartness and Uniformity
A Constructive Development
1st Edition., 2011, XIV, 198 p. 3 illus.
Hardcover, ISBN 978-3-642-22414-0
Largely an exposition of the authors' own research, this is the first
book dealing with the apartness approach to constructive topology, and
is a valuable addition to the literature on constructive mathematics and
on topology in computer science. It is aimed at graduate students and
advanced researchers in theoretical computer science, mathematics, and
logic who are interested in constructive/algorithmic aspects of
topology.
|
|
Volume 1
Rodney G. Downey,
Denis R. Hirschfeldt
Algorithmic Randomness and Complexity
1st Edition., 2010, XXVIII, 855 p. 8 illus.
Hardcover, ISBN 978-0-387-95567-4
This is the first comprehensive treatment of this important field, designed to be both a
reference tool for experts and a guide for newcomers. It surveys a broad section of work
in the area, and presents most of its major results and techniques in depth. It will be of
interest to researchers and students in computability theory, algorithmic information theory,
and theoretical computer science.
This book has received the Shoenfield Prize 2016, which is awarded by the Association for Symbolic
Logic for outstanding expository writing in the field of logic.
|
|
|