Generalized finite automata theory with an application to a decision problem of second-order logic

Abstract

Many of the important concepts and results of conventional finite automata theory are developed for a generalization in which finite algebras take the place of finite automata. The standard closure theorems are proved for the class of sets "recognizable" by finite algebras, and a generalization of Kleene's regularity theory is presented. The theorems of the generalized theory are then applied to obtain a positive solution to a decision problem of second-order logic. © 1968 Springer-Verlag New York Inc.