Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Solving sequential conditions by finite-state strategies


Authors: J. Richard Büchi and Lawrence H. Landweber
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
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [1] J. R. Buchi, Decision methods in the theory of ordinals, Bull. Amer. Math. Soc. 71 (1965), 767-770. MR 0189997 (32:7413)
  • [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.
  • [3] J. R. Buchi, Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlagen Math. 6 (1960), 66-92. MR 0125010 (23:A2317)
  • [4] -, On a decision method in restricted second order arithmetic, Proc. Internat. Congr. Logic, Method, and Philos. Sci. 1960, Stanford Univ. Press, Stanford, Calif., 1962. MR 0183636 (32:1116)
  • [5] 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.
  • [6] -, Logic arithmetic and automata, Proc. Internat. Congr. Math. 1963, Almqvist and Wiksells, Uppsala, 1963.
  • [7] M. Davis, ``Infinite games of perfect information'' in Advances in game theory, Princeton Univ. Press, Princeton, N. J., 1964, 85-101. MR 0170727 (30:965)
  • [8] C. C. Elgot, Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc. 98 (1961), 21-51. MR 0139530 (25:2962)
  • [9] J. Friedman, Some results in Church's restricted recursive arithmetic, J. Symbolic Logic 22 (1957), 337-342. MR 0097309 (20:3779)
  • [10] D. Gale and F. M. Stewart, ``Infinite games with perfect information'' in Contributions to the theory of games, Vol. II, Princeton Univ. Press, Princeton, N. J., 1953, 245-266. MR 0054922 (14:999b)
  • [11] S. C. Kleene, Arithmetical predicates and function quantifiers, Trans. Amer. Math. Soc. 79 (1955), 312-340. MR 0070594 (17:4g)
  • [12] -, ``Representation of events in nerve nets and finite automata'' in Automata studies, Princeton Univ. Press, Princeton, N. J., 1956, 3-41. MR 0077478 (17:1040c)
  • [13] L. H. Landweber, Finite state games--A solvability algorithm for restricted second-order arithmetic, Notices Amer. Math. Soc. 14 (1967), 129-130.
  • [14] R. McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521-530. MR 0213241 (35:4105)
  • [15] J. Mycielski, S. Swierczkowski and A. Zieba, On infinite positional games, Bull. Acad. Polon. Sci. Cl. III 4 (1956), 485-488. MR 0086725 (19:232i)
  • [16] M. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114-125. MR 0103795 (21:2559)
  • [17] M. Rabin, ``Effective computability of winning strategies'' in Contributions to the theory of games, Vol. III, Princeton Univ. Press, Princeton, N. J., 1957, 147-157. MR 0093740 (20:263)
  • [18] B. A. Trachtenbrot, Synthesis of logic networks whose operators are described by means of single place predicate calculus, Dokl. Akad. Nauk SSSR 118 (1958), 646-649. MR 0098687 (20:5142)
  • [19] -, Finite automata and the logic of single place predicates, Dokl. Akad. Nauk SSSR 140 (1961), 320-323 = Soviet Math. Dokl. 2 (1961), 623-626.
  • [20] J. R. Buchi and L. G. Landweber, Definability in the monadic second-order theory of successor, J. Symbolic Logic 34 (1969). MR 0269492 (42:4387)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 90.70, 68.00

Retrieve articles in all journals with MSC: 90.70, 68.00


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1969-0280205-0
Article copyright: © Copyright 1969 American Mathematical Society

American Mathematical Society