@inproceedings{10.5555_788022.789015,
    author = {Blumensath, Achim and Gr\"{a}del, Erich},
    title = {Automatic Structures},
    year = {2000},
    isbn = {0769507255},
    publisher = {IEEE Computer Society},
    address = {USA},
    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.},
    booktitle = {Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science},
    pages = {51},
    keywords = {logic, interpretability, definability vs. complexity, Automata},
    series = {LICS '00},
    date-added = {2025-10-31 17:27:13 +0100}
}

@inproceedings{10.5555_788022.789015, author = {Blumensath, Achim and Gr\"{a}del, Erich}, title = {Automatic Structures}, year = {2000}, isbn = {0769507255}, publisher = {IEEE Computer Society}, address = {USA}, 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.}, booktitle = {Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science}, pages = {51}, keywords = {logic, interpretability, definability vs. complexity, Automata}, series = {LICS '00}, date-added = {2025-10-31 17:27:13 +0100} }