Invariants of Automatic Presentations and Semi−Synchronous Transductions

Conference item

Automatic structures are countable structures finitely presentable by a collection of automata. We study questions related to properties invariant with respect to the choice of an automatic presentation. We give a negative answer to a question of Rubin concerning definability of intrinsically regular relations by showing that order-invariant first-order logic can be stronger than first-order logic with counting on automatic structures. We introduce a notion of equivalence of automatic present...

Expand abstract

Authors: Barany, V

• Publisher: Springer
• Host title: Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science‚ STACS 2006
• Volume: 3884
• Publication date: 2006-01-01