Monadic second order definable relations on the binary tree
Journal of Symbolic Logic 52 (1):219-226 (1987)
| Abstract | Let S2S [WS2S] espectively be the storn [weak] monadic second order theory of the binary tree T in the language of two successor functions. An S2S-formula whose free variables are just individual variables defines a relation on T (rather than on the power set of T). We show that S2S and WS2S define the same relations on T, and we give a simple characterization of these relations | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesShmuel Lifsches & Saharon Shelah (1997). Peano Arithmetic May Not Be Interpretable in the Monadic Theory of Linear Orders. Journal of Symbolic Logic 62 (3):848-872.
Amir Leshem (2000). On the Consistency of the Definable Tree Property on ℵ. Journal of Symbolic Logic 65 (3):1204 - 1214.
Nader Vakil (1987). Monadic Binary Relations and the Monad Systems at Near-Standard Points. Journal of Symbolic Logic 52 (3):689-697.
A. P. Hazen (1997). Relations in Monadic Third-Order Logic. Journal of Philosophical Logic 26 (6):619-628.
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
Shmuel Lifsches & Saharon Shelah (1996). Uniformization, Choice Functions and Well Orders in the Class of Trees. Journal of Symbolic Logic 61 (4):1206-1227.
E. Fischer & J. A. Makowsky (2004). On Spectra of Sentences of Monadic Second Order Logic with Counting. Journal of Symbolic Logic 69 (3):617-640.
Shmuel Lifsches & Saharon Shelah (1998). Uniformization and Skolem Functions in the Class of Trees. Journal of Symbolic Logic 63 (1):103-127.
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Yuri Gurevich & Saharon Shelah (1983). Rabin's Uniformization Problem. Journal of Symbolic Logic 48 (4):1105-1119.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads7 ( #133,421 of 549,065 )Recent downloads (6 months)1 ( #63,185 of 549,065 )How can I increase my downloads? |
My notes
Discussion
