Advice Automatic Structures and Uniformly Automatic Classes

We study structures that are automatic with advice. Building on advice automata we introduce the concept of a parameterised automatic presentation as a means to uniformly represent a class of finite or infinite structures with a regular set of advices. We give a characterisation of the advice automatic countable Boolean algebras and give upper bounds on the complexity of presentable structures for several algebraic classes like semigroups, groups, and integral domains generalising results for ordinary automatic structures. On the positive side we give, among others, parameterised automatic presentations for the class of torsion-free abelian groups of rank 1, the class of all finite abelian groups and the class of all groups having a product decomposition with non-abelian factors of bounded size. Furthermore we apply our results to show that model-checking for first-order logic becomes fixed-parameter tractable on the class of finite abelian groups and the class of all finite groups. This is joint work with Faried Abu Zaid and Erich Grädel (RWTH Aachen)

Authors

• Frederic Reinhardt

Keywords

No keywords are indexed for this paper.