|
|
|
|
automatic presentation
|
(Definition)
|
|
|
Let  be a relational structure (for example, a graph).
 has an automatic presentation if (for some alphabet  ) there is a language
 and a surjective map  from  onto the domain (universe) of  such that
 can be checked by a finite automaton (Membership)- The language of all convolutions of
 where  can be checked by a finite automaton (Equality)
- For all
 -ary relations  in  , the language of all convolutions of
 where
 can be checked by a finite automaton (Relations)
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 automaton 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 theory this is inspired by, but not equivalent to, the definition of automatic groups.
|
"automatic presentation" is owned by mathcam. [ owner history (1) ]
|
|
(view preamble)
See Also: automatic group
| Other names: |
automatic structure, FA presentation |
| Keywords: |
automata, structure, computability, decidable |
|
|
Cross-references: automatic groups, group, first order theory, structure, sentence, first order, empty language, intersection, union, operations, closed under, regular languages, automata, finite, class, equality, convolutions, map, surjective, language, alphabet, graph, relational structure
This is version 5 of automatic presentation, born on 2004-03-30, modified 2005-05-27.
Object id is 5736, canonical name is AutomaticPresentation.
Accessed 2691 times total.
Classification:
| AMS MSC: | 03C57 (Mathematical logic and foundations :: Model theory :: Effective and recursion-theoretic model theory) | | | 03D05 (Mathematical logic and foundations :: Computability and recursion theory :: Automata and formal grammars in connection with logical questions) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
