Automatic structures of bounded degree revisited

Details Automatic structures of bounded degree revisited Automatic structures of bounded degree revisited

2008-10-28

arxiv.org/abs/0810.4998v1

Computer Science

Logic in Computer Science

26 pages

Scientific paper

The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar results also for tree automatic structures. These findings close the gaps left open in a previous paper of the second author by improving both, the lower and the upper bounds.

Affiliated with

Also associated with

No associations

Rating

Automatic structures of bounded degree revisited 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 Automatic structures of bounded degree revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic structures of bounded degree revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-485407