Abstract | ||
---|---|---|
In [10] it was shown that it is possible to describe the set of normal inhabitants of a given type Τ, in the standard simple type system, using an infinitary extension of the concept of context-free grammar, which allows for an infinite number of non-terminal symbols as well as production rules. The set of normal inhabitants of Τ corresponds then to the set of terms generated by this, possibly infinitary, grammar plus all terms obtained from those by η-reduction. In this paper we show that the set of normal inhabitants of a type Τ can in fact be described using a standard (finite) context-free grammar, and more interestingly that normal inhabitants of types with the same structure are described by identical context-free grammars, up to renaming of symbols. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1007/3-540-45329-6_32 | EPIA '89 |
Keywords | Field | DocType |
non-terminal symbol,identical context-free grammar,context-free grammar,standard simple type system,context-free grammar representation,normal inhabitant,production rule,normal inhabitants,infinitary extension,infinite number,type system,context free grammar | Rule-based machine translation,Discrete mathematics,Lambda calculus,Context-free grammar,Computer science,Type theory,Grammar | Conference |
ISBN | Citations | PageRank |
3-540-43030-X | 3 | 0.60 |
References | Authors | |
5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sabine Broda | 1 | 64 | 13.83 |
Luís Damas | 2 | 128 | 22.34 |