Logical Approaches to Computational Barriers

Quantifiers on automatic structures

Speaker:
| Sasha Rubin |

Author(s): |
Valentin Goranko and Sasha Rubin |

Slot: |
Array, 17:30-17:50, col. 2 |

An {\em automatic presentation} of a structure is one in which the domain and atomic operations are computable by finite automata operating synchronously on their inputs (finite/infinite words/trees). The fundamental fact about such structures is that they are effectively closed under first-order interpretations. This result has already been strengthened by extending first-order logic with some natural generalised quantifiers, for instance, `there exist infinitely many' and `there exist $k$ modulo $m$ many'. Say that a generalised quantifier $Q$ has property E if the automatic structures are closed under FO + $Q$ interpretations. This talks presents the first steps towards a full understanding of those generalised quantifiers with property E. Restricted to the class of finite-word automatic presentations, I will introduce a natural collection of quantifiers each with property E that includes all known quantifiers satisfying E and can be shown to include {\em all} unary generalised quantifiers satisfying E.

websites: Arnold Beckmann | 2008-05-19 |