Abstract
With every finite-state word or tree automaton, we associate a binary relation on words or trees. We then consider the “rectangular decompositions” of this relation, i.e., the various ways to express it as a finite union of Cartesian products of sets of words or trees, respectively. We show that the determinization and the minimization of these automata correspond to simple geometrical reorganizations of the rectangular decompositions of the associated relations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arnold, A., A syntactic congruence for rational ω-languages,Theoret. Comput. Sci.,39 (1985), 333–335.
Brzozowski, J., Canonical regular expressions and minimal state graphs for definite events, inMathematical Theory of Automata, Vol. 12, MRI Symposium Series, Polytechnic Press of the Polytechnic Institute of Brooklyn, 1963, pp. 529–561.
Courcelle, B., On recognizable sets and tree automata, inResolution of Equations in Algebraic Structures, Vol. 1 (H. Aït-Kaci and M. Nivat, eds.), Academic Press, New York, 1989, pp. 93–126.
Courcelle, B., The monadic second-order logic of graphs, I: Recognizable sets of finite graphs,Inform. and Comput.,85 (1990), 12–75.
Eilenberg, S.,Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974.
Gecseg, F., and Steinby, M.,Tree Automata, Akademiai Kiado, Budapest, 1984.
Mezei, J., and Wright, J., Algebraic automata and context-free sets,Informat. and Control,11 (1967), 3–29.
Nerode, A., Linear automata transformations,Proc. Amer. Math. Soc.,9 (1958), 541–544.
Nivat, M., and Podelski, A., Tree monoids and recognizable sets of finite trees, inResolution of Equations in Algebraic Structures, Vol. 1 (H. Aït-Kaci and M. Nivat, eds.), Academic Press, New York, 1989, pp. 351–367.
Podelski, A., Monoïdes d'arbres et automates d'arbres, Thèse, Université Paris-7, 1989.
Rabin, M., and Scott, D., Finite automata and their decision problems,IBM J. Res. Develop.,3 (1959), 114–125. Reprinted inSequential Machines (E. Moore, ed.), Addison-Wesley, Reading, MA, 1964.
Staiger, L., Finite-state ω-languages,J. Comput. System Sci.,27 (1983), 434–448.
Trakhtenbrot, B., Finite automata and the logic of 1-place predicates,Siberian Math. J.,3 (1962), 103–131 (in Russian).
Author information
Authors and Affiliations
Additional information
This work was supported by the “Programme de Recherches Coordonnées: Mathématiques et Informatique.” It was initiated during a stay in Bordeaux by D. Niwinski in 1988.
Rights and permissions
About this article
Cite this article
Courcelle, B., Niwinski, D. & Podelski, A. A geometrical view of the determinization and minimization of finite-state automata. Math. Systems Theory 24, 117–146 (1991). https://doi.org/10.1007/BF02090394
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02090394