Linearly bounded infinite graphs

Details Linearly bounded infinite graphs Linearly bounded infinite graphs

2007-05-24

arxiv.org/abs/0705.3487v1

Acta Informatica 43, 4 (25/08/2006) p. 265-292

Computer Science

Logic in Computer Science

Scientific paper

10.1007/s00236-006-0022-z

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.

Affiliated with

Also associated with

No associations

Rating

Linearly bounded infinite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linearly bounded infinite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linearly bounded infinite graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-605899