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

Adaptive solution strategy for solving large systems of p‐type finite element equations

R.B. Morris, Y. Tsuji, et al.

International Journal for Numerical Methods in Engineering

Conference paper

On a partial ordering relation derived from redundancy of Slepian-Wolf coding

Da-Ke He, Ashish Jagmohan, et al.

ISIT 2007

Paper

Output distribution of the burrows-wheeler transform

Karthik Visweswariah, Sanjeev Kulkarni, et al.

IEEE International Symposium on Information Theory - Proceedings

Conference paper

Convergence properties of multi-dimensional stack filters

Peter Wendt

Electronic Imaging: Advanced Devices and Systems 1990

View all publications

Abstract

Related

Adaptive solution strategy for solving large systems of p‐type finite element equations

On a partial ordering relation derived from redundancy of Slepian-Wolf coding

Output distribution of the burrows-wheeler transform

Convergence properties of multi-dimensional stack filters