Promise Algebra: A Functional Approach to Non-Deterministic Computations

Explore a 26-minute lecture on Promise Algebra and its functional approach to non-deterministic computations, presented by Eugenia Ternovska from Simon Fraser University at the Simons Institute. Delve into an algebraic method for modeling non-determinism, where logic-based formalisms tackle complex computer science problems related to computational processes and complexity analysis. Discover how this approach confines non-determinism to the atomic level, resulting in a semi-deterministic model. Learn about the algebra's equivalent form as a linear-time Dynamic Logic and the crucial role of history-dependent choice functions. Understand how solving computational problems correlates to generating strategies in a one-player game, offering new insights into the field of Games and Equilibria in System Design and Analysis.