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