Solving sequential conditions by finite-state strategies
HTML articles powered by AMS MathViewer
- by J. Richard Büchi and Lawrence H. Landweber PDF
- Trans. Amer. Math. Soc. 138 (1969), 295-311 Request permission
References
- J. Richard Büchi, Decision methods in the theory of ordinals, Bull. Amer. Math. Soc. 71 (1965), 767–770. MR 189997, DOI 10.1090/S0002-9904-1965-11384-2 J. R. Buchi, C. E. Elgot and J. B. Wright, The nonextstence of certain algorithms of finite automata theory, Notices Amer. Math. Soc. 5 (1958), 98.
- J. Richard Büchi, Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlagen Math. 6 (1960), 66–92. MR 125010, DOI 10.1002/malq.19600060105
- J. Richard Büchi, On a decision method in restricted second order arithmetic, Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), Stanford Univ. Press, Stanford, Calif., 1962, pp. 1–11. MR 0183636 A. Church, Application of recursive arithmetic to the problem of circuit synthesis, Summaries of Talks Presented at the Summer Institute for Symbolic Logic, Cornell Univ. 1957, 2nd ed; Princeton, N. J., 1960, 3-50. —, Logic arithmetic and automata, Proc. Internat. Congr. Math. 1963, Almqvist and Wiksells, Uppsala, 1963.
- Morton Davis, Infinite games of perfect information, Advances in Game Theory, Princeton Univ. Press, Princeton, N.J., 1964, pp. 85–101. MR 0170727
- Calvin C. Elgot, Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc. 98 (1961), 21–51. MR 139530, DOI 10.1090/S0002-9947-1961-0139530-9
- Joyce Friedman, Some results in Church’s restricted recursive arithmetic, J. Symbolic Logic 22 (1957), 337–342. MR 97309, DOI 10.2307/2963908
- David Gale and F. M. Stewart, Infinite games with perfect information, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, N.J., 1953, pp. 245–266. MR 0054922
- S. C. Kleene, Arithmetical predicates and function quantifiers, Trans. Amer. Math. Soc. 79 (1955), 312–340. MR 70594, DOI 10.1090/S0002-9947-1955-0070594-4
- S. C. Kleene, Representation of events in nerve nets and finite automata, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, N.J., 1956, pp. 3–41. MR 0077478 L. H. Landweber, Finite state games—A solvability algorithm for restricted second-order arithmetic, Notices Amer. Math. Soc. 14 (1967), 129-130.
- Robert McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521–530. MR 213241, DOI 10.1016/S0019-9958(66)80013-X
- Jan Mycielski, S. Świerczkowski, and A. Zięba, On infinite positional games, Bull. Acad. Polon. Sci. Cl. III. 4 (1956), 485–488. MR 0086725
- M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114–125. MR 103795, DOI 10.1147/rd.32.0114
- Michael O. Rabin, Effective computability of winning strategies, Contributions to the theory of games, vol. 3, Annals of Mathematics Studies, no. 39, Princeton University Press, Princeton, N.J., 1957, pp. 147–157. MR 0093740
- B. A. Trahtenbrot, The synthesis of logical nets whose operators are described in terms of one-place predicate calculus, Dokl. Akad. Nauk SSSR (N.S.) 118 (1958), 646–649 (Russian). MR 0098687 —, Finite automata and the logic of single place predicates, Dokl. Akad. Nauk SSSR 140 (1961), 320-323 = Soviet Math. Dokl. 2 (1961), 623-626.
- J. Richard Büchi and Lawrence H. Landweber, Definability in the monadic second-order theory of successor, J. Symbolic Logic 34 (1969), 166–170. MR 269492, DOI 10.2307/2271090
Additional Information
- © Copyright 1969 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 138 (1969), 295-311
- MSC: Primary 90.70; Secondary 68.00
- DOI: https://doi.org/10.1090/S0002-9947-1969-0280205-0
- MathSciNet review: 0280205