[Up]
Finite automata and ordinals
Copyright informations
This material has been published in Theoretical Computer Science, vol. 156, pp 119-144, Mars 1996. Copyright and all rights therein are retained by Elsevier. This material may not be copied or reposted without explicit permission.
Read this to learn more about publisher's official green light
to self-archive both their pre-refereeing preprints and their refereed
postprints.
Abstract
Several definitions of automata on words indexed by ordinals have been proposed previously.
The first one was introduced by Buchi to prove the decidability of the monadic second order theory of denumerable ordinals.
Wojciechowski studied the properties of these automata independently of the length of the input.
The second definition, proposed by Choueka, works only on words of length less than ω^n.
In this paper, we restrict the domain of Wojciechowski automata to the domain of Choueka's ones (that is, given n<ω, we keep only sequences of length less than ω^(n+1) in the language defined by a Wojciechowski automaton) in order to prove the equivalence between Choueka automata and Wojciechowski automata.
Then, we obtain the closure under complementation of the class of Wojciechowski's definable sets, and finally we give an algorithm for determinizing Wojciechowski automata.
- J. Richard Büchi, "On a decision method in the restricted second-order
arithmetic", in Logic, Methodology and Philosophy of science: Proc.
Intern. Congr., (Stanford, California), pp. 1-11, Stanford University
Press, 1962.
- J. Richard Büchi, "Decision methods in the theory of ordinals",
Bull. Am. Math. Soc., vol. 71, pp. 767-770, 1965.
- Yacoov Choueka, "Theories of automata on ω-tapes: a simplified
approach", Journal of Computer and System Sciences, vol. 8, pp.
117-141, 1974.
- Yacoov Choueka, "Finite automata, definable sets, and regular expressions
over ω^n-tapes", Journal of Computer and System Sciences, vol.
17, pp. 81-97, 1978.
- J. E. Hopcroft and J. D. Ullman, Introduction to automata theory,
languages, and computation.
Addison-Wesley, Reading, 1979.
- Robert McNaughton, "Testing and generating infinite sequences by a finite
automaton", Information and Control, vol. 9, pp. 521-530,
1966.
- D. Muller, "Infinite sequences and finite machines", in Switching
circuit theory and logical design: Proc. Fourth Annual Symp. IEEE, pp.
3-16, 1963.
- Dominique Perrin and Jean-Eric Pin, Mots infinis.
1997.
To appear (LITP report 97-04).
- J. G. Rosenstein, Linear ordering.
Academic Press, New York, 1982.
- Waclaw Sierpinski, Leçons sur les nombres transfinis.
Paris: Gauthier-Villars, 1950.
- Waclaw Sierpinski, Cardinal and ordinal numbers.
Varsovie: Polish Scientific Publishers, 1965.
- Wolfgang Thomas, Handbook of theoretical computer science, vol. B,
ch. Automata on infinite objects, pp. 135-191.
Elsevier, 1990.
- Jerzy Wojciechowski, "Classes of transfinite sequences accepted by finite
automata", Fundamenta informaticĉ, vol. 7, no. 2, pp. 191-223,
1984.
- Jerzy Wojciechowski, "Finite automata on transfinite sequences and regular
expressions", Fundamenta informatic\ae, vol. 8, no. 3-4, pp.
379-396, 1985.
Download
Gzipped postcript format
 |
24 January 2015 22:05:30 |