He received his Ph.D. in mathematics from the University of Jena in 1976; Staiger wrote his doctoral thesis, Zur Topologie der regulären Mengen, under the direction of Gerd Wechsung[de] and Rolf Lindner.[1]
He co-invented with Klaus Wagner the Staiger–Wagner automaton. Staiger is an expert in ω-languages, an area in which he wrote more than 19 papers [3] including the paper on this topic in the monograph.[4] He found surprising applications of ω-languages in the study of Liouville numbers.
C. S. Calude, L. Staiger. Liouville numbers, Borel normality and algorithmic randomness, Theory of Computing Systems, First online 27 April 2017, doi:10.1007/s00224-017-9767-8.
In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin.
Gregory John Chaitin is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem. He is considered to be one of the founders of what is today known as algorithmic complexity together with Andrei Kolmogorov and Ray Solomonoff. Along with the works of e.g. Solomonoff, Kolmogorov, Martin-Löf, and Leonid Levin, algorithmic information theory became a foundational part of theoretical computer science, information theory, and mathematical logic. It is a common subject in several computer science curricula. Besides computer scientists, Chaitin's work draws attention of many philosophers and mathematicians to fundamental problems in mathematical creativity and digital philosophy.
Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor at the University of Toronto, Department of Computer Science and Department of Mathematics.
Richard Edwin Stearns is a prominent computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory". In 1994 he was inducted as a Fellow of the Association for Computing Machinery.
In mathematics and computer science, Zeno machines are a hypothetical computational model related to Turing machines that are capable of carrying out computations involving a countably infinite number of algorithmic steps. These machines are ruled out in most models of computation.
Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" (except for a constant that only depends on the chosen universal programming language) the relations or inequalities found in information theory. According to Gregory Chaitin, it is "the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously."
Christos Charilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.
Michael J. Dinneen is an American-New Zealand mathematician and computer scientist working as a senior lecturer at the University of Auckland, New Zealand. He is co-director of the Center for Discrete Mathematics and Theoretical Computer Science. He does research in combinatorial algorithms, distributive programming, experimental graph theory, and experimental algorithmic information theory.
Avi Wigderson is an Israeli mathematician and computer scientist. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural networks. Wigderson received the Abel Prize in 2021 for his work in theoretical computer science.
Faron George Moller is a Canadian-born British computer scientist and expert on theoretical computer science, particularly infinite-state automata theory and temporal logic. His work has focussed on structural decomposition techniques for analysing abstract models of computing systems. He is founding Director of the Swansea Railway Verification Group; Director of Technocamps; and Head of the Institute of Coding in Wales.
John Vivian Tucker is a British computer scientist and expert on computability theory, also known as recursion theory. Computability theory is about what can and cannot be computed by people and machines. His work has focused on generalising the classical theory to deal with all forms of discrete/digital and continuous/analogue data; and on using the generalisations as formal methods for system design; based on abstract data types and on the interface between algorithms and physical equipment.
In mathematics, effective dimension is a modification of Hausdorff dimension and other fractal dimensions that places it in a computability theory setting. There are several variations of which the most common is effective Hausdorff dimension. Dimension, in mathematics, is a particular way of describing the size of an object. Hausdorff dimension generalizes the well-known integer dimensions assigned to points, lines, planes, etc. by allowing one to distinguish between objects of intermediate size between these integer-dimensional objects. For example, fractal subsets of the plane may have intermediate dimension between 1 and 2, as they are "larger" than lines or curves, and yet "smaller" than filled circles or rectangles. Effective dimension modifies Hausdorff dimension by requiring that objects with small effective dimension be not only small but also locatable in a computable sense. As such, objects with large Hausdorff dimension also have large effective dimension, and objects with small effective dimension have small Hausdorff dimension, but an object can have small Hausdorff but large effective dimension. An example is an algorithmically random point on a line, which has Hausdorff dimension 0 but effective dimension 1.
Cristian Sorin Calude is a Romanian-New Zealander mathematician and computer scientist.
Michael Ezra Saks is an American mathematician. He is currently the Department Chair of the Mathematics Department at Rutgers University (2017–) and from 2006 until 2010 was director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D. from the Massachusetts Institute of Technology in 1980 after completing his dissertation titled Duality Properties of Finite Set Systems under his advisor Daniel J. Kleitman.
Constantinos Daskalakis is a Greek theoretical computer scientist. He is a professor at MIT's Electrical Engineering and Computer Science department and a member of the MIT Computer Science and Artificial Intelligence Laboratory. He was awarded the Rolf Nevanlinna Prize and the Grace Murray Hopper Award in 2018.
Parallel Processing Letters is a journal published by World Scientific since 1991. It covers the field of parallel processing, including topics such as design and analysis of parallel and distributed algorithms, parallel programming languages and parallel architectures and VLSI circuits.
Richard Ryan Williams, known as Ryan Williams, is an American theoretical computer scientist working in computational complexity theory and algorithms.
Jan van Leeuwen is a Dutch computer scientist and Emeritus professor of computer science at the Department of Information and Computing Sciences at Utrecht University.
Stathis K. Zachos is a mathematician, logician and theoretical computer scientist.
Leslie Ann Goldberg is a professor of computer science at the University of Oxford and a Fellow of St Edmund Hall, Oxford. Her research concerns the design and analysis of algorithms for random sampling and approximate combinatorial enumeration.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
