Type Specification by Regular Expressions

Loutfi Soufi (University of Bourgogne, Lirsia, Fac. Sciences, France)

Abstract: Generally, programming problems are formally described as function computation problems. In this paper they are viewed as language recognition problems. More precisely, we sugget to specify types, and programs using the concept of languages of concatenation of level n, i.e, languages built from regular languages on which language transformation operations are applied to them. Regular languages denoted by regular expressions allow an easy connection between those languages of concatenation and programming. This connection is naturally done via recurrence relations. We explain our approach through some examples.