The synchronized graphs trace the context-sensitive languagesReportar como inadecuado




The synchronized graphs trace the context-sensitive languages - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIGM - Laboratoire d-Informatique Gaspard-Monge

Abstract : Morvan and Stirling have proved that the context-sensitive languages are exactly the traces of graphs de ned by transducers with labelled nal states. We prove that this result is still true if we restrict to the traces of graphs de ned by synchronized transducers with labelled nal states. From their construction, we deduce that the context-sensitive languages are the languages of path labels leading from and to rational vertex sets of letter-to-letter rational graphs.





Autor: Chloé Rispal -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados