Generalized Finite Automata over the Real Numbers

Klaus Meer

Brandenburg University of Technology, Cottbus

Gandhi, Khoussainov, and Liu introduced and studied a generalized model of finite automata able to work over arbitrary structures. The model mimics finite automata over finite structures, but has an additional ability to perform in a restricted way operations attached to the structure under consideration. As one relevant area of investigations for this model Gandhi et al. identified studying the new automata over uncountable structures such as the real and complex numbers.

In the talk we pick up this suggestion and consider their automata model as a finite automata variant in the BSS model of real number computation. We study structural properties as well as (un-)decidability results for several questions inspired by the classical finite automata model.

This is joint work with A. Naif.