Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Quantifiers on automatic structures


Speaker: Sasha Rubin
Author(s): Valentin Goranko and Sasha Rubin
Slot: Array, 17:30-17:50, 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