Families of automata characterizing context-sensitive languages |
| |
| Authors: | Christophe Morvan Chloé Rispal |
| |
| Affiliation: | (1) Institut Gaspard Monge, Université de Marne-la-Vallée, 5, bd Descartes, 77454 Marne-la-Vallée cedex 2, France |
| |
| Abstract: | In the hierarchy of infinite graph families, rational graphs are defined by rational transducers with labelled final states. This paper proves that their traces are precisely context-sensitive languages and that this result remains true for synchronized rational graphs.Received: 17 December 2003, Published online: 27 December 2004 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
