Automatic structures
- 1 January 2000
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We study definability and complexity issues for automatic and /spl 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 (/spl 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 characterisations 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.Keywords
This publication has 8 references indexed in Scilit:
- More about recursive structures: descriptive complexity and zero-one lawsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Towards Recursive Model TheoryPublished by Springer Nature ,1998
- Metafinite Model TheoryInformation and Computation, 1998
- Finite Model TheoryPublished by Springer Nature ,1995
- Model TheoryPublished by Cambridge University Press (CUP) ,1993
- Simple interpretations among complicated theoriesInformation Processing Letters, 1990
- On the equivalence, containment, and covering problems for the regular and context-free languagesJournal of Computer and System Sciences, 1976
- On Relations Defined by Generalized Finite AutomataIBM Journal of Research and Development, 1965