Linearly bounded infinite graphs |
| |
Authors: | Arnaud Carayol Antoine Meyer |
| |
Affiliation: | (1) Irisa, Campus de Beaulieu, 35042 Rennes Cedex, France;(2) Liafa, Université Denis Diderot, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France |
| |
Abstract: | Linearly bounded Turing machines have been mainly studied as acceptors for context-sensitive languages. We define a natural class of infinite automata representing their observable computational behavior, called linearly bounded graphs. These automata naturally accept the same languages as the linearly bounded machines defining them. We present some of their structural properties as well as alternative characterizations in terms of rewriting systems and context-sensitive transductions. Finally, we compare these graphs to rational graphs, which are another class of automata accepting the context-sensitive languages, and prove that in the bounded-degree case, rational graphs are a strict sub-class of linearly bounded graphs.A preliminary version of this article appeared in MFCS 2005. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|