Nondeterminism fairness and a fundamental analogy

Keywords

Analogy, Computer science, Mathematical economics, Mathematics, Epistemology

References

• Classes of Languages and Linear-Bounded AutomataS.-Y. Kuroda — 1964
• Introduction to Automata Theory, Languages and ComputationJ. Hopcroft, Rajeev Motwani, Rotwani — 1979
• Countable nondeterminism and random assignmentKrzysztof R. Apt, Gordon Plotkin — 1986
• Finite State LanguagesNoam Chomsky, George A. Miller — 1958
• Nondeterministic space is closed under complementationNeil Immerman — 1988
• Finite Automata and Their Decision ProblemsM. O. Rabin, D. Scott — 1959
• Recursively enumerable sets and degreesRobert I. Soare — 1987
• A Discipline of ProgrammingEdsger W. Dijkstra — 1976
• Computable nondeterministic functionsAshok K. Chandra — 1978
• Proof Rules and Transformations Dealing with FairnessKrzysztof R. Apt, Ernst-Rüdiger Olderog — 1983
• On Computable Numbers, with an Application to the Entscheidungsproblem.Albert A. Bennett — 1937
• Theory of Recursive Functions and Effective ComputabilityR. L. Goodstein — 1969
• Characterizing Correctness Properties of Parallel Programs Using FixpointsE. Emerson, E. Clarke — 1980

Cited by

• Exact Algorithms for Exact Satisfiability ProblemsVilhelm Dahllöf — 2006
• Hypercomputation: computing more than the Turing machineToby Ord — 2002
• Computational Power of Infinite Quantum ParallelismMartin Ziegler — 2004
• Real Hypercomputation and ContinuityMartin Ziegler — 2005
• Logical and schematic characterization of complexity classesIain A. Stewart — 2005
• Introduction to the theory of complexityV. J. Rayward‐Smith, Daniel P. Bovet, Pierluigi Crescenzi — 1994
• Revising Type-2 Computation and Degrees of DiscontinuityMartin Ziegler — 2006
• The many forms of hypercomputationToby Ord — 2006
• Exact Algorithms forVilhelm Dahllöf — 2006
• Continuous Models of Genetic Regulatory Networks and the Multistability ProblemKelly John Rose — 2009
• Décidabilité et ComplexitéOlivier Bournez, Gilles Dowek, Rémi Gilleron — 2010
• Real Hypercomputation and Degrees of DiscontinuityMartin Ziegler — 2006
• Is Church’s Thesis Still Relevant?Jerzy Mycka, Adam Olszewski — 2020
• Nondeterminism and Guarded CommandsKrzysztof R. Apt, Ernst-Rüdiger Olderog — 2022
• Turing Machines for Dummies - Why Representations Do MatterP. E. Boas — 2012
• Accountable AlgorithmsJoshua A. Kroll — 2015
• Real computability and hypercomputationM. Ziegler — 2007
• Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 NondeterminismM. Ziegler — 2005
• Theoretical Computer Science: Computability, Decidability and LogicO. Bournez, Gilles Dowek, Rémi Gilleron — 2020

Related papers

• On computable numbers, with an application to the EntscheidungsproblemAlan Turing — 1937
• Classical recursion theoryP. Odifreddi — 1989
• Computable AnalysisKlaus Weihrauch — 2005
• Computers and Intractability: A Guide to the Theory of NP-CompletenessM. R. Garey, David S. Johnson — 1979
• Modeling Partiality by NondeterminismYngve Lamo, Michał Walicki — 2001
• Full Abstraction for Strongly Fair Communicating ProcessesStephen Brookes, Susan Older — 1995
• The Converse of a Stochastic RelationErnst–Erich Doberkat — 2003