New applications of the wreath product of forest algebras

Howard Straubing

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 3, page 261-291
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Straubing, Howard. "New applications of the wreath product of forest algebras." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.3 (2013): 261-291. <http://eudml.org/doc/272987>.

@article{Straubing2013,
abstract = {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.},
author = {Straubing, Howard},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {tree automata; temporal logics; forest algebras},
language = {eng},
number = {3},
pages = {261-291},
publisher = {EDP-Sciences},
title = {New applications of the wreath product of forest algebras},
url = {http://eudml.org/doc/272987},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Straubing, Howard
TI - New applications of the wreath product of forest algebras
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 3
SP - 261
EP - 291
AB - 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.
LA - eng
KW - tree automata; temporal logics; forest algebras
UR - http://eudml.org/doc/272987
ER -

References

top
  1. [1] M. Benedikt and L. Segoufin, Regular tree languages definable in fo and in fomod. ACM Trans. Comput. Logic11 (2009) 1–4. Zbl1118.03314MR2664302
  2. [2] M. Bojanczyk, Algebra for trees, in AutoMathA Handbook, edited by J.-E. Pin (2012). Preprint. 
  3. [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). Zbl1217.68123MR2549260
  4. [4] M. Bojańczyk, Decidable Properties of Tree Languages. Ph.D. thesis, University of Warsaw (2004). 
  5. [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. Zbl1139.68036MR2477193
  6. [6] M. Bojanczyk, L. Segoufin and H. Straubing, Piecewise testable tree languages. To appear in Logical Methods Comput. Sci. (2012). Zbl1261.03126MR2987919
  7. [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). Zbl1258.03044MR2932390
  8. [8] S. Eilenberg, Automata, Languages, and Machines, vol. B. Pure and Applied Mathematics. New York, Academic Press (1976). Zbl0359.94067MR530383
  9. [9] E. Allen Emerson, Temporal and modal logic, in Handbook Of Theoretical Computer Science. Elsevier (1995) 995–1072. Zbl0900.03030MR1127201
  10. [10] L. Libkin, Elements Of Finite Model Theory. Texts in Theoretical Computer Science. Springer (2004). Zbl1060.03002MR2102513
  11. [11] M. Maidl, The common fragment of ctl and ltl. In FOCS. IEEE Computer Society (2000) 643–652. MR1931861
  12. [12] F. Moller and A. M. Rabinovich, On the expressive power of ctl. In LICS. IEEE Computer Society (1999) 360–368. Zbl1110.68076MR1943430
  13. [13] J.E. Pin, Varieties of formal languages. North Oxford Academic (1986). Zbl0632.68069MR912694
  14. [14] J.-E. Pin, Syntactic semigroups, vol. 1 in Handbook of Formal Languages. Springer (1997). MR1470002
  15. [15] A. Potthoff, First-order logic on finite trees. Lect. Notes Comput. Sci.915 (1995) 125–139. 
  16. [16] M. Schützenberger, Sur le produit de concatenation non ambigu. Semigroup Forum 13 (1976) 47–75. Doi: 10.1007/BF02194921. Zbl0373.20059MR444824
  17. [17] S. Shamir, O. Kupferman and E. Shamir, Branching-depth hierarchies. Electr. Notes Theor. Comput. Sci.39 (2000) 65–78. Zbl1260.03034

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.