Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

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 Valid HTML 4.01! Valid CSS!