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.

Paper

Differential operators and the theory of binomial enumeration

George Markowsky

J. Math. Anal. Appl.

Paper

Vertex-Ant-Walk - A robust method for efficient exploration of faulty graphs

Vladimir Yanovski, Israel A. Wagner, et al.

Ann. Math. Artif. Intell.

Conference paper

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

Simeon Furrer, Dirk Dahlhaus

ISIT 2005

Paper

Parallel program schemata

Richard M. Karp, Raymond E. Miller

Journal of Computer and System Sciences

View all publications

Abstract

Related

Differential operators and the theory of binomial enumeration

Vertex-Ant-Walk - A robust method for efficient exploration of faulty graphs

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

Parallel program schemata