“Bulletin Board”

School of Mathematics - November 24, 2004

Mathematical Lectures

Saeed SalehiInstitute of Mathematics Polish Academy of Science, PolandDecember 1-2, 2004 School of Mathematics, IPM

 Saeed Salehi Institute of Mathematics,Polish Academy of Science,Poland Talk 1: Variants of Kleene's Recursive Realizability Wednesday, December 1, 16:00-18:00 Abstract: The notion of Recursive Realizability introduced by Kleene is a useful tool for measuring the strength of intuitionistic arithmetics. Various generalizations of this realizability has been proposed by restricting the class of recursive functions to a proper sub-class. As such examples one could mention Damnjanovic's or Lopez-Escobar's primitive recursive realizability or Plisko's $\Sigma_n$--realizability. In this talk, I present definitions and basic properties of two realizabilities introduced by the speaker, namely that of realizability by primitive recursive functions and realizability by polynomially bounded (primitive) recursive functions. Applying these to Ruitenburg's Basic Arithmetic (a sub-system of Heyting Arithmetic) yields interesting results about its provably total functions. Applicability of these realizabilities to Basic Arithmetic results from the observations that (1) the G\"odel codes of primitive recursive and polynomially bounded recursive functions are arithmetically definable, and (2) the S-m-n functions in Recursion Theory can be chosen from the class of primitive recursive or polynomially bounded recursive functions. Talk 2: Variety Theory of Tree Languages Thursday, December 2, 16:00-18:00 Abstract: String languages can be regarded as subsets of free semigroups over their alphabets. Eilenberg's variety theorem connects amilies of string languages to varieties of semigroups through their syntactic semigroups. For tree languages which are defined to be subsets of (free) term algebras several syntactic structures have been introduced in the literature, two of which are syntactic algebras and syntactic semigroups/monoids. A variety theorem for syntactic algebras of tree languages was proved by M. Steinby, but no variety theorem was known for syntactic semigroups/monids. In this talk, I sketch the variety theorem for tree languages and syntactic semigroups/monoids proved by the speaker recently. Information: Place: School of Mathematics, Niavaran Bldg., Niavaran Square, Tehran, Iran.