The synchronized graphs trace the context-sensitive languages.

Chloé Rispal


Abstract

The synchronized graphs trace the context-sensitive languages. Traces of graphs are a link between infinite graph hierarchy and the Chomsky hierarchy of languages. Recently, Morvan and Stirling have proved that the context-sensitive languages are exactly the traces of rational graphs defined by transducers with labelled final states. We prove that this result is still true if we restrict to the traces of graphs defined by synchronized transducers with labelled final 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 graphs defined by letter-to-letter transducers with labelled final states.