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.

Conference paper

Modeling polarization for Hyper-NA lithography tools and masks

Kafai Lai, Alan E. Rosenbluth, et al.

SPIE Advanced Lithography 2007

Conference paper

Convergence properties of multi-dimensional stack filters

Peter Wendt

Electronic Imaging: Advanced Devices and Systems 1990

Conference paper

Compression for data archiving and backup revisited

Corneliu Constantinescu

SPIE Optical Engineering + Applications 2009

Paper

Output distribution of the burrows-wheeler transform

Karthik Visweswariah, Sanjeev Kulkarni, et al.

IEEE International Symposium on Information Theory - Proceedings

View all publications

Abstract

Related

Modeling polarization for Hyper-NA lithography tools and masks

Convergence properties of multi-dimensional stack filters

Compression for data archiving and backup revisited

Output distribution of the burrows-wheeler transform