A context-free grammar representation for normal inhabitants of types in TA¿

• Type: Article in International Conference Proceedings Book
• Date: 2001

Authors

Broda, S (Author) FCUP; Damas, L (Author) FCUP

Conference proceedings International

Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Pages: 321-334

10th Portuguese Conference on Artificial Intelligence, EPIA 2001

Porto, 17 December 2001 through 20 December 2001

Indexing

ISI Web of Knowledge

Scopus - 3 Citations

Other information

Authenticus ID: P-007-DFP

DOI: 10.1007/3-540-45329-6_32

Abstract (EN): 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. © Springer-Verlag Berlin Heidelberg 2001.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14