Computability in Europe 2008
Logic and Theory of Algorithms

## Regular Talk: Quantifiers on automatic structures

Edit abstract data

 Speaker: Sasha Rubin Author(s): Valentin Goranko and Sasha Rubin Slot: Wed, 17:30-17:50, Amphitheater B (col. 2)

### Abstract

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