Logic in Computer Science (LICS 2000)

Paper: Automatic Structures (at LICS 2000)

Authors: Achim Blumensath Erich Grädel

Abstract

We study definability and complexity issues for automatic and omega-automatic structures. These are, in general, infinite structures but they can be finitely presented by a collection of automata. Moreover, they admit effective (in fact automatic) evaluation of all first-order queries. Therefore, automatic structures provide an interesting framework for extending many algorithmic and logical methods from finite structures to infinite ones.We explain the notion of (omega-) automatic structures, give examples, and discuss the relationship to automatic groups. We determine the complexity of model checking and query evaluation on automatic structures for fragments of first-order logic. Further, we study closure properties and definability issues on automatic structures and present a technique for proving that a structure is not automatic. We give model-theoretic characterizations for automatic structures via interpretations. Finally, we discuss the composition theory of automatic structures and prove that they are closed under finitary Feferman-Vaught-like products.

BibTeX

  @InProceedings{BlumensathGrdel-AutomaticStructures,
    author = 	 {Achim Blumensath and Erich Grädel},
    title = 	 {Automatic Structures},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2000},
    year =	 2000,
    editor =	 {Martin Abadi},
    month =	 {June}, 
    pages =      {51--62},
    location =   {Santa Barbara, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }