New applications of the wreath product of forest algebras
Straubing, Howard
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013), p. 261-291 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We give several new applications of the wreath product of forest algebras to the study of logics on trees. These include new simplified proofs of necessary conditions for definability in CTL and first-order logic with the ancestor relation; a sequence of identities satisfied by all forest languages definable in PDL; and new examples of languages outside CTL, along with an application to the question of what properties are definable in both CTL and LTL.

Publié le : 2013-01-01
DOI : https://doi.org/10.1051/ita/2013039
Classification:  03D05,  68Q70 
@article{ITA_2013__47_3_261_0,
     author = {Straubing, Howard},
     title = {New applications of the wreath product of forest algebras},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {47},
     year = {2013},
     pages = {261-291},
     doi = {10.1051/ita/2013039},
     mrnumber = {3103128},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2013__47_3_261_0}
}

Straubing, Howard. New applications of the wreath product of forest algebras. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) pp. 261-291. doi : 10.1051/ita/2013039. http://gdmltest.u-ga.fr/item/ITA_2013__47_3_261_0/

[1] M. Benedikt and L. Segoufin, Regular tree languages definable in fo and in fomod. ACM Trans. Comput. Logic 11 (2009) 1-4. | MR 2664302 | Zbl 1118.03314

[2] M. Bojanczyk, Algebra for trees, in AutoMathA Handbook, edited by J.-E. Pin (2012). Preprint.

[3] M. Bojanczyk and I. Walukiewicz, Forest algebras, in Logic and Automata: History and Perspectives, edited by E. Graedel, J. Flum and T. Wilke. Amsterdam University Press (2008). | MR 2549260 | Zbl 1217.68123

[4] M. Bojańczyk, Decidable Properties of Tree Languages. Ph.D. thesis, University of Warsaw (2004).

[5] M. Bojanczyk, The common fragment of actl and ltl. In FoSSaCS, vol. 4962 of Lect. Notes Comput Sci., edited by R.M. Amadio (2008) 172-185. | MR 2477193 | Zbl 1139.68036

[6] M. Bojanczyk, L. Segoufin and H. Straubing, Piecewise testable tree languages. To appear in Logical Methods Comput. Sci. (2012). | MR 2987919 | Zbl 1261.03126

[7] M. Bojanczyk, H. Straubing and I. Walukiewicz, Wreath products of forest algebras, with applications to tree logics. To appear in Logical Methods Comput. Sci. (2012). | MR 2932390 | Zbl 1258.03044

[8] S. Eilenberg, Automata, Languages, and Machines, vol. B. Pure and Applied Mathematics. New York, Academic Press (1976). | MR 530383 | Zbl 0359.94067

[9] E. Allen Emerson, Temporal and modal logic, in Handbook Of Theoretical Computer Science. Elsevier (1995) 995-1072. | MR 1127201 | Zbl 0900.03030

[10] L. Libkin, Elements Of Finite Model Theory. Texts in Theoretical Computer Science. Springer (2004). | MR 2102513 | Zbl 1060.03002

[11] M. Maidl, The common fragment of ctl and ltl. In FOCS. IEEE Computer Society (2000) 643-652. | MR 1931861

[12] F. Moller and A. M. Rabinovich, On the expressive power of ctl. In LICS. IEEE Computer Society (1999) 360-368. | MR 1943430 | Zbl 1110.68076

[13] J.E. Pin, Varieties of formal languages. North Oxford Academic (1986). | MR 912694 | Zbl 0632.68069

[14] J.-E. Pin, Syntactic semigroups, vol. 1 in Handbook of Formal Languages. Springer (1997). | MR 1470002

[15] A. Potthoff, First-order logic on finite trees. Lect. Notes Comput. Sci. 915 (1995) 125-139.

[16] M. Schützenberger, Sur le produit de concatenation non ambigu. Semigroup Forum 13 (1976) 47-75. Doi: 10.1007/BF02194921. | MR 444824 | Zbl 0373.20059

[17] S. Shamir, O. Kupferman and E. Shamir, Branching-depth hierarchies. Electr. Notes Theor. Comput. Sci. 39 (2000) 65-78. | Zbl 1260.03034