Text-only Preview

From References: 0
From Reviews: 1
MR2372750 (2009b:03107) 03D05 (03B44 68Q45 68Q70)
Esik, Zolt´an (H-SZEG-C); Iv´an, Szabolcs (H-SZEG-C)
Products of tree automata with an application to temporal logic. (English summary)
Fund. Inform. 82 (2008), no. 1-2, 6178.
The present paper and its sequel [Fund. Inform. 82 (2008), no. 1-2, 79–103; MR2372751
(2009b:03108)] constitute a continuation and generalization of the first author’s earlier research
published in a series of three papers [in Proceedings of the 1st International Conference on
Algebraic Informatics
, 53–77, Aristotle Univ. Thessaloniki, Thessaloniki, 2005; MR2186455
(2006j:03018); ibid., 79–99; MR2186456 (2006j:03019); ibid., 101–110; MR2186457
(2006j:03017)]. In the earlier papers varieties of tree automata which were closed under the cas-
cade products (of algebras) were linked, via a type of Eilenberg Variety Theorem, to the families
of tree languages which were definable by some modal (and other natural) operations. The clo-
sure of the tree automata varieties under the cascade products forced the modal operations to
express the next modality, and the families of tree languages to contain the variety D of definite
tree languages.
In these two papers, the authors relax the constraint of being closed under the cascade products
(of the tree automata varieties) to being closed under the so-called Moore products. The closure
of the tree automata varieties under the Moore products does not force anything on the expressive
power of the modal operations, but still the families of tree languages have to contain the variety
D1 of 1-definite tree languages.
In this first paper the above basic result, with a few applications and examples, is presented.
Reviewed by Saeed Salehi
c Copyright American Mathematical Society 2009