Products of Tree Automata with an Application to Temporal Logic

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

Abstrakty

EN

We introduce the notion of the Moore product of tree automata as a special case of the cascade product. We give an algebraic characterization of the expressive power of certain CTL-like temporal logics based on the notion of varieties of finite tree automata closed under the Moore product.

Słowa kluczowe

EN

tree automata; temporal logic

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 82, nr 1-2
• Strony: 61-78
• Opis fizyczny: bibliogr. 15 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] Bojańczyk, M., Walukiewicz, I.: Characterising EF and EX tree logics, in: proc. CONCUR 2004, vol. 3170 of LNCS, Springer-Verlag, 2004, 131-145.
• [4] Ésik, Z.: Definite tree automata and their cascade compositions, Publ. Math., 48, 1996, 243-262.
• [5] Ésik, Z.: A variety theorem for trees and theories, Publ. Math., 54, 1999, 711-762.
• [6] É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.
• [7] Ésik, Z.: Characterizing CTL-like logics on finite trees, Theoretical Computer Science, 356, 2006, 136-152.
• [8] Ésik, Z., Iván, S.: Some varieties of finite tree automata related to restricted temporal logic, To appear in Fundamenta Informaticae.
• [9] Gécseg, F., Steinby, M.: Tree Automata, Akadémiai Kiadó, 1984.
• [10] Grätzer, G.: Universal Algebra, Springer, 1979.
• [11] Ricci, G.: Cascades of tree-automata and computations in universal algebras, Math. Systems Theory, 7, 1973, 201-218.
• [12] Salehi, S.: Varieties of Tree Languages, Ph.D. Thesis, TUCS, 2006.
• [13] Schneider, K.: Verification of Reactive Systems, Springer-Verlag, 2004.
• [14] Steinby,M.: A theory of tree language varieties, in: Tree Automata and Languages, North-Holland, Amsterdam, 1992, 57-81.
• [15] Steinby, M.: General varieties of tree languages, Theoret. Comput. Sci., 205, 1998, 1-43