Leftmost derivations of propagating scattered context grammars: a new proof

Abstract : In 1973, V. Virkkunen proved that propagating scattered context grammars which use leftmost derivations are as powerful as context-sensitive grammars. This paper brings a significantly simplified proof of this result.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (2), pp.39--46
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00972321
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:10:40
Dernière modification le : mercredi 29 novembre 2017 - 10:26:21
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:35:26

Fichier

712-3269-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00972321, version 1

Collections

Citation

Tomáš Masopust, Jiří Techet. Leftmost derivations of propagating scattered context grammars: a new proof. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (2), pp.39--46. 〈hal-00972321〉

Partager

Métriques

Consultations de la notice

198

Téléchargements de fichiers

172