More Like this

1. Reasoning about rationality

   https://doi.org/10.1016/j.geb.2017.03.006  

   Bjorndahl, A.; Halpern, J.Y.; Pass, R. (July 2017, Games and Economic Behavior)
2. Reasoning about Uncertainties in Discrete-Time Dynamical Systems using Polynomial Forms

   Sankaranarayanan, Sriram; Chou, Yi; Goubault, Eric; and Putot, Sylvie (December 2020, Advances in Neural Information Processing System (NeurIPS))

   null (Ed.)

   In this paper, we propose polynomial forms to represent distributions of state variables over time for discrete-time stochastic dynamical systems. This problem arises in a variety of applications in areas ranging from biology to robotics. Our approach allows us to rigorously represent the probability distribution of state variables over time, and provide guaranteed bounds on the expectations, moments and probabilities of tail events involving the state variables. First we recall ideas from interval arithmetic, and use them to rigorously represent the state variables at time t as a function of the initial state variables and noise symbols that model the random exogenous inputs encountered before time t. Next we show how concentration of measure inequalities can be employed to prove rigorous bounds on the tail probabilities of these state variables. We demonstrate interesting applications that demonstrate how our approach can be useful in some situations to establish mathematically guaranteed bounds that are of a different nature from those obtained through simulations with pseudo-random numbers. 

   more » « less
3. Reasoning about Uncertainties in Discrete-Time Dynamical Systems using Polynomial Forms.

   Sankaranarayanan, Sriram; Chou, Yi; Goubault, Eric; Putot, Sylvie (December 2020, Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020))

   In this paper, we propose polynomial forms to represent distributions of state variables over time for discrete-time stochastic dynamical systems. This problem arises in a variety of applications in areas ranging from biology to robotics. Our approach allows us to rigorously represent the probability distribution of state variables over time, and provide guaranteed bounds on the expectations, moments and probabilities of tail events involving the state variables. First, we recall ideas from interval arithmetic, and use them to rigorously represent the state variables at time t as a function of the initial state variables and noise symbols that model the random exogenous inputs encountered before time t. Next, we show how concentration of measure inequalities can be employed to prove rigorous bounds on the tail probabilities of these state variables. We demonstrate interesting applications that demonstrate how our approach can be useful in some situations to establish mathematically guaranteed bounds that are of a different nature from those obtained through simulations with pseudo-random numbers. 

   more » « less
4. Reasoning about recursive tree traversals

   https://doi.org/10.1145/3437801.3441617  

   Wang, Yanjun; Liu, Jinwei; Zhang, Dalin; Qiu, Xiaokang (February 2021, Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming)

   null (Ed.)

   Traversals are commonly seen in tree data structures, and performance-enhancing transformations between tree traversals are critical for many applications. Existing approaches to reasoning about tree traversals and their transformations are ad hoc, with various limitations on the classes of traversals they can handle, the granularity of dependence analysis, and the types of possible transformations. We propose Retreet, a framework in which one can describe general recursive tree traversals, precisely represent iterations, schedules and dependences, and automatically check data-race-freeness and transformation correctness. The crux of the framework is a stack-based representation for iterations and an encoding to Monadic Second-Order (MSO) logic over trees. Experiments show that Retreet can automatically verify optimizations for complex traversals on real-world data structures, such as CSS and cycletrees, which are not possible before. Our framework is also integrated with other MSO-based analysis techniques to verify even more challenging program transformations. 

   more » « less
5. Exploring student reasoning about circuits using reasoning chain construction tasks

   https://doi.org/10.1119/perc.2024.pr.Doan  

   Doan, Vincent; Speirs, J Caleb (September 2024, American Association of Physics Teachers)