Invariants of Automatic Presentations and Semi−Synchronous Transductions
Vince Barany
Abstract
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 presentations, define semi-synchronous transductions, and show how these concepts correspond. Our main result is that a one-to-one function on words preserves regularity as well as non-regularity of all relations iff it is a semi-synchronous transduction. We also characterize automatic presentations of the complete structures of Blumensath and Gr�del.
Details
| Book Title |
Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science‚ STACS 2006 |
| Editor |
B. Durand and W. Thomas |
| Pages |
289−300 |
| Publisher |
Springer |
| Series |
LNCS |
| Volume |
3884 |
| Year |
2006 |
Links
Related pages
|
People |