Almost deterministic $\omega$-automata with existential output condition
HTML articles powered by AMS MathViewer
- by Marek Karpiński PDF
- Proc. Amer. Math. Soc. 53 (1975), 449-452 Request permission
Abstract:
The theorem on reduction in the nondeterminateness degree of $\omega$-automata has been formulated.References
- 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
- 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
- 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 D. E. Muller, Infinite sequences and finite machines, AIEE Proc. Fourth Annual Sympos. Switching Circuit Theory and Logical Design, 1963, pp. 3-16.
- 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, Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1–35. MR 246760, DOI 10.1090/S0002-9947-1969-0246760-1
Additional Information
- © Copyright 1975 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 53 (1975), 449-452
- MSC: Primary 02F10; Secondary 68A30, 68A25
- DOI: https://doi.org/10.1090/S0002-9939-1975-0437321-8
- MathSciNet review: 0437321