Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2025-01-03T11:54:54.177Z Has data issue: false hasContentIssue false
  • English
  • Français

The decision problem for branching time logic1,2

Published online by Cambridge University Press:  12 March 2014

Yuri Gurevich  and
Saharon Shelah
Yuri Gurevich
Affiliation:
Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109
Saharon Shelah
Affiliation:
Institute of Mathematics, The Hebrew University, Jerusalem 91904, Israel
Get access Rights & Permissions [Opens in a new window]

Abstract

The theory of trees with additional unary predicates and quantification over nodes and branches embraces a rich branching time logic. This theory was reduced in the companion paper to the first-order theory of binary, bounded, well-founded trees with additional unary predicates. Here we prove the decidability of the latter theory.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 50 , Issue 3 , September 1985 , pp. 668 - 681
Copyright
Copyright © Association for Symbolic Logic 1985

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.)

Footnotes

1

The results were obtained in principle during the Jerusalem Logic Year 1980–81 when both authors were fellows in the Institute for Advanced Studies of Hebrew University.

2

Supported in part by the US-Israel Binational Science Foundation.

References

REFERENCES

[DMT]Doner, J. E., Mostowski, A. and Tarski, A., The elementary theory of well-ordering-a metamathematical study, Logic Colloquium '77, North-Holland, Amsterdam, 1978, pp. 1–54.Google Scholar
[Eh]Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fundamenta Mathematicae, vol. 49(1961), pp. 129–141:CrossRefGoogle Scholar
[Gu]Gurevich, Y., Monadic second-order theories, Model-theoretical logics (Barwise, J. and Feferman, S., editors), Springer-Verlag, Berlin (to appear).Google Scholar
[Gu2]Gurevich, Y., Toward logic tailored for computational complexity, Logic Colloquium '83, Lecture Notes in Mathematics, Springer-Verlag, Berlin (to appear).Google Scholar
[GS]Gurevich, Y. and Shelah, S., To the decision problem for branching time logic, Foundations of logic and linguistics: Problems and their solutions, Plenum Press (to appear).Google Scholar
[Sh]Shelah, S., The monadic theory of order, Annals of Mathematics, ser. 2, vol. 102 (1975), pp. 379–419.CrossRefGoogle Scholar