Page 1

Displaying 1 – 6 of 6

Showing per page

New applications of the wreath product of forest algebras

Howard Straubing (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

New recursive characterizations of the elementary functions and the functions computable in polynomial space.

I. Oitavem (1997)

Revista Matemática de la Universidad Complutense de Madrid

We formulate recursive characterizations of the class of elementary functions and the class of functions computable in polynomial space that do not require any explicit bounded scheme. More specifically, we use functions where the input variables can occur in different kinds of positions ?normal and safe? in the vein of the Bellantoni and Cook's characterization of the polytime functions.

Currently displaying 1 – 6 of 6

Page 1