@incollection{Rabin:Weak:1970,
    Abstract = {Publisher Summary This chapter presents the weakly definable relations and special automata. The monadic second-order theories and study problems of definability are considered. The chapter characterizes the definable relations by means of finite automata operating on infinite trees. The notion of a special automaton on infinite trees is obtained and is used to characterize the weakly definable sets. As a by-product of the characterization of weakly definable relations, the solution of certain decision problems is obtained. It is shown that the weak second-order theory of a unary function and the weak second-order theory of linearly ordered sets are decidable. These results were corollaries of stronger theorems concerning the corresponding full monadic second-order theories. The same decidability results are deduced using the information concerning weakly definable relations and special automata. The chapter characterizes the weakly-defined relations and develops a theory of special automata.},
    Author = {Rabin, Michael O.},
    BookTitle = {Mathematical Logic and Foundations of Set Theory},
    Editor = {Bar-Hillel, Yehoshua},
    File = {Weakly Definable Relations and Special Automata - rabin1970 - a - a - a - a.pdf},
    ISSN = {0049-237X},
    Pages = {1 - 23},
    Publisher = {Elsevier},
    Series = {Studies in Logic and the Foundations of Mathematics},
    Title = {Weakly Definable Relations and Special Automata},
    URL = {http://www.sciencedirect.com/science/article/pii/S0049237X08719293},
    Volume = {59},
    Year = {1970},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0049237X08719293},
    bdsk-url-2 = {https://doi.org/10.1016/S0049-237X(08)71929-3},
    date-added = {2020-02-06 16:06:15 +0100},
    date-modified = {2020-02-06 16:23:41 +0100},
    doi = {10.1016/S0049-237X(08)71929-3}
}

@incollection{Rabin:Weak:1970, Abstract = {Publisher Summary This chapter presents the weakly definable relations and special automata. The monadic second-order theories and study problems of definability are considered. The chapter characterizes the definable relations by means of finite automata operating on infinite trees. The notion of a special automaton on infinite trees is obtained and is used to characterize the weakly definable sets. As a by-product of the characterization of weakly definable relations, the solution of certain decision problems is obtained. It is shown that the weak second-order theory of a unary function and the weak second-order theory of linearly ordered sets are decidable. These results were corollaries of stronger theorems concerning the corresponding full monadic second-order theories. The same decidability results are deduced using the information concerning weakly definable relations and special automata. The chapter characterizes the weakly-defined relations and develops a theory of special automata.}, Author = {Rabin, Michael O.}, BookTitle = {Mathematical Logic and Foundations of Set Theory}, Editor = {Bar-Hillel, Yehoshua}, File = {Weakly Definable Relations and Special Automata - rabin1970 - a - a - a - a.pdf}, ISSN = {0049-237X}, Pages = {1 - 23}, Publisher = {Elsevier}, Series = {Studies in Logic and the Foundations of Mathematics}, Title = {Weakly Definable Relations and Special Automata}, URL = {http://www.sciencedirect.com/science/article/pii/S0049237X08719293}, Volume = {59}, Year = {1970}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0049237X08719293}, bdsk-url-2 = {https://doi.org/10.1016/S0049-237X(08)71929-3}, date-added = {2020-02-06 16:06:15 +0100}, date-modified = {2020-02-06 16:23:41 +0100}, doi = {10.1016/S0049-237X(08)71929-3} }