automatic presentation
Let $S$ be a relational structure (for example, a graph).
$S$ has an automatic presentation if (for some alphabet $\mathrm{\Sigma}$) there is a language^{} $L\subseteq {\mathrm{\Sigma}}^{*}$ and a surjective map $f$ from $L$ onto the ) of $S$ such that

•
$L$ can be checked by a finite automaton (http://planetmath.org/DeterministicFiniteAutomaton) (Membership)

•
The language of all convolutions of $x,y\in L$ where $f(x)=f(y)$ can be checked by a (Equality)

•
For all $n$ary relations^{} (http://planetmath.org/Relation) ${R}_{i}$ in $S$, the language of all convolutions of ${x}_{1},{x}_{2},\mathrm{\dots},{x}_{n}\in L$ where ${R}_{i}(f({x}_{1}),f({x}_{2}),\mathrm{\dots},f({x}_{n}))$ can be checked by a ()
The class of languages accepted by finite automata, i.e. regular languages, is closed under^{} operations like union, intersection^{}, complementation etc, and it is decidable whether or not a finite accepts the empty language. This allows any first order sentence^{} over the structure^{} to be decided  using union for ’and’, complementation for ’not’ etc., and emptiness for dealing with ’there exists’. As such, the first order theory of any structure with an automatic presentation is decidable.
Note that wrt group this is inspired by, but not to, the definition of automatic groups^{}.
Title  automatic presentation 

Canonical name  AutomaticPresentation 
Date of creation  20130322 14:16:57 
Last modified on  20130322 14:16:57 
Owner  mathcam (2727) 
Last modified by  mathcam (2727) 
Numerical id  8 
Author  mathcam (2727) 
Entry type  Definition 
Classification  msc 03D05 
Classification  msc 03C57 
Synonym  automatic structure 
Synonym  FA presentation 
Related topic  AutomaticGroup 