Towards an Algebraic Theory of Context-Free Languages

J. Berstel, L. Boasson

IBP-Litp 1994/51: Rapport de Recherche Litp / Litp research reports
25 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Towards an Algebraic Theory of Context-Free Languages

Résumé : Le but de cet article est de présenter les conséquences d'une nouvelle définition des langages algébriques. L'intérêt principal de cette approche est d'une part de permettre de donner des preuves formelles complètes et, d'autre part,de mettre en évidence le rôle central des fermetures rationnelles. Le formalisme proposé est fondé sur un théorème de Wechler..Il est très proche des "algèbres radicales" de Conway.

Abstract : The purpose of the paper is to present the implications of a new definition of context-free languages. The main interests of this approach are first to allow full formal proofs and second to enlight the crucial role of rational closures. The proposed formalism is based on a theorem of wechler. It is very near to the "radical algebras" of Conway.

Publications internes Litp 1994 / Litp research reports 1994