Decidability of second-order theories and automata on infinite trees

Michael O. Rabin

doi:10.1090/S0002-9904-1968-12122-6

Bulletin of the American Mathematical Society

Paper

01 Jan 1968

Decidability of second-order theories and automata on infinite trees

Download paper

Abstract

In this note we announce the solvability of the decision problem of the (monadic) second-order theory of two suc- cessor functions (S2S). This answers a question raised by Büchi.

Workshop paper

SPRIG: Stackelberg Perception-Reinforcement Learning with Internal Game Dynamics

Fernando Martinez, Juntao Chen, et al.

AAAI 2025

Conference paper

Convergence properties of multi-dimensional stack filters

Peter Wendt

Electronic Imaging: Advanced Devices and Systems 1990

Talk

Nesterov Accelerated Shuffling Gradient Method for Convex Optimization

Trang H. Tran, Lam Nguyen, et al.

INFORMS 2022

Conference paper

Bounds on the ergodic capacity of training-based multiple-antenna systems

Simeon Furrer, Dirk Dahlhaus

ISIT 2005

View all publications

Abstract

Related

SPRIG: Stackelberg Perception-Reinforcement Learning with Internal Game Dynamics

Convergence properties of multi-dimensional stack filters

Nesterov Accelerated Shuffling Gradient Method for Convex Optimization

Bounds on the ergodic capacity of training-based multiple-antenna systems