Automatic Structures

Proceedings - Symposium on Logic in Computer Science, pp. 21–34

Abstract

Automatic structures made their appearance at LICS twenty years ago, at LICS 2000. However, their roots are much older. The idea of automata based decision procedures for logical theories can be traced back to the early days of automata theory and to the work of Büchi, Elgot, Trakhtenbrot and Rabin in the 1960s. The explicit notion of automatic structures has first been proposed in 1976 in the (unfortunately largely unnoticed) PhD thesis of Hodgson, and later been reinvented by Khoussainov and Nerode in 1995.

Authors 1

1. Erich Grädel corresponding Aachen Mathematical Foundations of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Mathematical Foundations of Computer Science, RWTH Aachen University, Germany