Several Applications of Analytic Functors to Theoretical: Computer Science

✍ Scribed by Ryu Hasegawa

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 30 KB
• Volume: 29
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(05)80310-x

✦ Synopsis

Analytic functors, or combinatorial species, were introduced by Joyal in 80's to provide a categorical foundation to enumerative combinatorics. Incidentally we found that analytic functors can be used as foundations of several subjects in theoretical computer science.

A famous theorem by Kruskal of well-quasi-ordering finite trees was employed by Dershowitz in term rewriting systems to develop the theory of termination orderings. We show that a class of wellquasi-orderings including Kruskal's and other well-known examples is generated by considering analytic functors. So we have a simple uniform method to form classes of well-quasi-orderings and well-orderings.

Second we consider the theory of lambda calculi. Girard gave semantics of several systems of lambda calculi by introducing normal functors, which are, as seen by a minute of thinking, special cases of analytic functors. So the machinery of enumerative combinatorics behind analytic functors are useful to show some properties of the normal functor model.

Furthermore we focus on the fixpoint operators, which are often used to interpret recursion in computer science. The Lagrange-Good inversion formula, known in analysis and enumerative combinatorics, gives an expression for computing fixpoints of certain recursive definitions on formal power series. We give a new computer theoretical proof of the formula, considering the interpretation of the fixpoint operator in the normal functor model. In the proof, we employ the recent finding by Hasegawa relating fixpoint operators with categorical traces of Joyal, Street and Verity.