Some Varieties of Finite Tree Automata Related to Restricted Temporal Logics

• Autorzy: Ésik Z. , Iván S.
• Języki publikacji: EN

Abstrakty

EN

We provide structural descriptions of certain varieties of finite tree automata closed under a version of the cascade product, called the Moore product. As a byproduct, we obtain decidable characterizations of the expressive power of certain fragments of CTL on finite trees.

Słowa kluczowe

EN

finite trees

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 82, nr 1-2
• Strony: 79--103
• Opis fizyczny: bibliogr. 37 poz.

Twórcy

autor

Ésik Z.

autor

Iván S.

• Department of Computer Science, University of Szeged, H-6701 Szeged, P.O.B.652, Hungary

Bibliografia

• [1] Almeida, J.: On pseudovarieties, varieties of languages, filters of congruences, pseudoidentities and related topics, Algebra Universalis, 27, 1990, 333-350.
• [2] Ben-Ari, M., Manna, Z., Pnueli, A.: The temporal logic of branching time, Acta Informatica, 20, 1983, 207-226.
• [3] Benedikt, M., Segoufin, L.: Regular tree languages definable in FO, in: STACS 2005, vol. 2404 of LNCS, Springer-Verlag, 2005, 327-339.
• [4] Bojańczyk, M., Walukiewicz, I.: Characterising EF and EX tree logics, in: proc. CONCUR 2004, vol. 3170 of LNCS, Springer-Verlag, 2004, 131-145.
• [5] Cohen, J., Perrin, D., Pin, J.-E.: On the expressive power of temporal logic, J. Comput. System Sci., 46, 1983, 271-294.
• [6] Cormen, T. H., Leiserson, C. E., Rivest, R. L.: Introduction to Algorithms, MIT Press/McGraw-Hill, 1990.
• [7] Eilenberg, S.: Automata, Languages, and Machines, vol. A and B, Academic Press, 1974 and 1976.
• [8] Emerson, E. A., Halpern, J. Y.: "Sometimes" and "not never" revisited: on branching versus linear time temporal logic, J. Assoc. Comput. Mach., 33, 1986, 151-178.
• [9] Ésik, Z.: Definite tree automata and their cascade compositions, Publ. Math., 48, 1996, 243-262.
• [10] Ésik, Z.: A variety theorem for trees and theories, Publ. Math., 54, 1999, 711-762.
• [11] Ésik, Z.: An algebraic characterization of temporal logics on finite trees. Parts I, II, III, in: 1st International Conference on Algebraic Informatics, 2005, Aristotle Univ. Thessaloniki, Thessaloniki, 2005, 53-77, 79-99, 101-110.
• [12] Ésik, Z.: Characterizing CTL-like logics on finite trees, Theoretical Computer Science, 356, 2006, 136-152.
• [13] Ésik, Z., Iv´an, S.: Products of tree automata with an application to temporal logic, To appear in Fundamenta Informaticae.
• [14] Ésik, Z.,Weil, P.: On logically defined recognizable tree languages, in: FST&TCS 03, Mumbai, vol. 2914 of LNCS, Springer-Verlag, 2003, 195-206.
• [15] Ésik, Z., Weil, P.: Algebraic recognizability of regular tree languages, Theoret. Comput. Sci., 340, 2005, 291-321.
• [16] Gécseg, F., Steinby, M.: Tree Automata, Akadémiai Kiadó, 1984.
• [17] Grätzer, G.: Universal Algebra, Springer, 1979.
• [18] Hafer, T., Thomas,W.: Computation tree logic CTL_ and path quantifiers in the monadic theory of the binary tree, in: ICALP 1987, vol. 267 of LNCS, Springer-Verlag, Karlsruhe, 1987, 269-279.
• [19] Heuter, U.: Definite tree languages, Bulletin of the EATCS, 35, 1988, 137-142.
• [20] Heuter, U.: First-order properties of trees, star-free expressions, and aperiodicity, in: STACS 88, vol. 294 of LNCS, Springer-Verlag, 1988, 136-148.
• [21] McNaughton, R., Papert, S.: Counter-Free Automata, MIT Press, 1971.
• [22] Peled, D.,Wilke, T.: Stutter-invariant temporal properties are expressible without the next-time operator, Inf. Proc. Lett., 63, 1997, 243-246.
• [23] Perrin, D., Pin, J.-E.: First-order logic and star-free sets, J. Comput. System Sci., 32, 1986, 393-406.
• [24] Perrin, D., Pin, J.-E.: Infinite Words, Pure and Applied Mathematics, 141, 2004.
• [25] Piirainen, V.: Monotone algebras, R-trivial monoids and a variety of tree languages, Bulletin of the EATCS, 84, 2004, 189-194.
• [26] Pin, J.-E.: Varieties of Formal Languages, Plenum Publishing Corp., New York, 1986.
• [27] Potthoff, A.: First order logic on finite trees, in: TAPSOFT '95, vol. 915 of LNCS, Springer-Verlag, 1995, 125-139.
• [28] Ricci, G.: Cascades of tree-automata and computations in universal algebras, Math. Systems Theory, 7, 1973, 201-218.
• [29] Salehi, S.: Varieties of Tree Languages, Ph.D. Thesis, TUCS, 2006.
• [30] Schneider, K.: Verification of Reactive Systems, Springer-Verlag, 2004.
• [31] Schützenberger, M. P.: On finite monoids having only trivial subgroups, Information and Control, 8, 1965, 190-194.
• [32] Steinby, M.: A theory of tree language varieties, in: Tree Automata and Languages, North-Holland, Amsterdam, 1992, 57-81.
• [33] Steinby, M.: General varieties of tree languages, Theoret. Comput. Sci., 205, 1998, 1-43.
• [34] Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity, Birkhauser, 1994.
• [35] Thomas, W.: Logical aspects in the study of tree languages, in: Ninth Colloquium on Trees in Algebra and Programming, Bordeaux, 1984, Cambridge Univ. Press, Cambridge, 1984, 31-49.
• [36] VanderWerf, J.: Wreath products of algebras: generalizing the Krohn-Rhodes theorem to arbitrary algebras, Semigroup Forum, 52, 1996, 93-100.
• [37] Wilke, T.: Classifying discrete temporal properties, in: STACS 99, Trier, vol. 1563 of LNCS, Springer-Verlag, Berlin, 1999, 32-46.