Abstract
We study structures that are automatic with advice. These are structures that admit a presentation by finite automata (over finite or infinite words or trees) with access to an additional input,called an advice. Over finite words, a standard example of a structure that is automatic with advice, but not automatic in the classical sense, is the additive group of rational numbers (Q,+).
By using a set of advices rather than a single advice, this leads to the new concept of a parameterised automatic presentation as a means to uniformly represent a whole class of structures. The decidability of the firstorder theory of such a uniformly automatic class reduces to the decidability of the monadic secondorder theory of the set of advices that are used in the presentation. Such decidability results also hold for extensions of firstorder logic by regularity preserving quantifiers, such as cardinality quantifiers and Ramsey quantifiers.
To investigate the power of this concept, we present examples of structures and classes of structures that are automatic with advice but not without advice, and we prove classification theorems for the structures with an advice automatic presentation for several algebraic domains.
In particular, we prove that the class of all torsionfree Abelian groups of rank one is uniformly omegaautomatic and that there is a uniform omegatreeautomatic presentation of the class of all Abelian groups up to elementary equivalence and of the class of all countable divisible Abelian groups.
On the other hand we show that every uniformly omegaautomatic class of Abelian groups must have bounded rank.
While for certain domains, such as trees and Abelian groups, it turns out that automatic presentations with advice are capable of presenting significantly more complex structures than ordinary automatic presentations, there are other domains, such as Boolean algebras, where this is provably not the case. Further, advice seems to not be of much help for representing some particularly relevant examples of structures with decidable theories, most notably the field of
reals.
Finally we study closure properties for several kinds of uniformly automatic classes, and decision problems concerning the number of nonisomorphic models in uniformly automatic classes with the unique representation property.
BibTeX  Entry
@InProceedings{abuzaid_et_al:LIPIcs:2017:7697,
author = {Faried Abu Zaid and Erich Gr{\"a}del and Frederic Reinhardt},
title = {{Advice Automatic Structures and Uniformly Automatic Classes}},
booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
pages = {35:135:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770453},
ISSN = {18688969},
year = {2017},
volume = {82},
editor = {Valentin Goranko and Mads Dam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7697},
URN = {urn:nbn:de:0030drops76971},
doi = {10.4230/LIPIcs.CSL.2017.35},
annote = {Keywords: automatic structures, algorithmic model theory, decidable theories, torsionfree abelian groups, firstorder logic}
}
Keywords: 

automatic structures, algorithmic model theory, decidable theories, torsionfree abelian groups, firstorder logic 
Seminar: 

26th EACSL Annual Conference on Computer Science Logic (CSL 2017) 
Issue Date: 

2017 
Date of publication: 

14.08.2017 