Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-17T17:23:05.219Z Has data issue: false hasContentIssue false
  • English
  • Français

Monadic second order definable relations on the binary tree

Published online by Cambridge University Press:  12 March 2014

Hans Läuchli  and
Christian Savioz
Hans Läuchli
Affiliation:
Department of Mathematics, ETH, CH-8092 Zürich, Switzerland
Christian Savioz
Affiliation:
Department of Mathematics, ETH, CH-8092 Zürich, Switzerland
Get access Rights & Permissions [Opens in a new window]

Abstract

Let S2S [WS2S] respectively be the strong [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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 52 , Issue 1 , March 1987 , pp. 219 - 226
Copyright
Copyright © Association for Symbolic Logic 1987

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Berstel, J., Transductions and context-free languages, Teubner, Stuttgart, 1979.CrossRefGoogle Scholar
[2] Büchi, J. R., On a decision method in restricted second order arithmetic, Proceedings of the international conference on logic, methodology and philosophy of science, 1960, Stanford University Press, Stanford, California, 1962, pp. 1–11.Google Scholar
[3] Buszkowski, W., Logical complexity of some classes of tree languages generated by multiple-tree-automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 26 (1980), pp. 41–49.CrossRefGoogle Scholar
[4] Gurevich, Y. and Harrington, L., Trees, automata and games, Proceedings of the fourteenth ACM symposium on the theory of computing (San Francisco, 1982), ACM, New York, 1982, pp. 60–65.Google Scholar
[5] Kleene, S. C., Representation of events in nerve nets and finite automata, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, New Jersey, 1956, pp. 3–41.Google Scholar
[6] Rabin, M. O., Decidability of second order theories and automata on infinite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[7] Rabin, M. O., Weakly definable relations and special automata, Mathematical logic and foundations of set theory (proceedings of an international colloquium, Jerusalem, 1968), North-Holland, Amsterdam, 1970, pp. 1–23.Google Scholar
[8] Rabin, M. O., Automata on infinite objects and Church's problem, Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, no. 13, American Mathematical Society, Providence, Rhode Island, 1972.CrossRefGoogle Scholar
[9] Robinson, R. M., Restricted set-theoretical definitions in arithmetic, Proceedings of the American Mathematical Society, vol. 9 (1958), pp. 238–242.CrossRefGoogle Scholar
[10] Savioz, CH., Extensions décidantes et indécidables de la théorie monadique du deuxième ordre de deux fonctions de successeur, Dissertation No. 7898, ETH, Zürich, 1985.Google Scholar
[11] Thomas, W., On the bounded monadic theory of well-ordered structures, this Journal, vol. 45 (1980), pp. 334–338.Google Scholar