Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Almost deterministic $ \omega $-automata with existential output condition

Author: Marek Karpiński
Journal: Proc. Amer. Math. Soc. 53 (1975), 449-452
MSC: Primary 02F10; Secondary 68A30, 68A25
MathSciNet review: 0437321
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The theorem on reduction in the nondeterminateness degree of $ \omega $-automata has been formulated.

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

  • [1] J. R. 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 32 #1116. MR 0183636 (32:1116)
  • [2] J. R. Büchi, Decision methods in the theory of ordinals, Bull. Amer. Math. Soc. 71 (1965), 767-770. MR 32 #7413. MR 0189997 (32:7413)
  • [3] R. McNaughton, Testing and generating infinite sequences by a finite autommaton, Information and Control 9 (1966), 521-530. MR 35 #4105. MR 0213241 (35:4105)
  • [4] D. E. Muller, Infinite sequences and finite machines, AIEE Proc. Fourth Annual Sympos. Switching Circuit Theory and Logical Design, 1963, pp. 3-16.
  • [5] M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114-125. MR 21 #2559; reprinted in Sequential machines, selected papers, edited by E. F. Moore, Addison-Wesley, Reading, Mass., 1964. MR 0103795 (21:2559)
  • [6] M. O. Rabin, Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1-35. MR 40 #30. MR 0246760 (40:30)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 02F10, 68A30, 68A25

Retrieve articles in all journals with MSC: 02F10, 68A30, 68A25

Additional Information

Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society