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	2013-03-22 14:16:57
Last modified on	2013-03-22 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