Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-18T03:02:53.282Z Has data issue: false hasContentIssue false

Automatic structures of bounded degree revisited

Published online by Cambridge University Press:  12 March 2014

Dietrich Kuske
Affiliation:
Technische Universität Ilmenau, Institut für Theoretische Informatik, Ilmenau, Germany, E-mail: dietrich.kuske@tu-ilmenau.de
Markus Lohrey
Affiliation:
Universität Leipzig, Institut für Informatik, Leipzig, Germany, E-mail: lohrey@informatik.uni-leipzig.de

Abstract

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 [28] by improving both the lower and the upper bounds.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable