Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Periodic Generalized Automata over the Reals
verfasst von : Klaus Meer, Ameen Naif
Erschienen in: Language and Automata Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In [4] Gandhi, Khoussainov, and Liu introduced and studied a generalized model of finite automata able to work over arbitrary structures. The model mimics the 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 the authors of [4] identified studying the new automata over uncountable structures such as the real numbers. This research was started in [7]. However, there it turned out that many elementary properties known from classical finite automata are lost. This refers both to structural properties of accepted languages and to decidability and computability questions. The intrinsic reason for this is that the computational abilities of the new model turn out to be too strong.
We therefore propose a restricted version of the model which we call periodic GKL automata. The new model still has certain computational abilities which, however, are restricted in that computed information is deleted again after a fixed period in time. We show that this limitation regains a lot of classical properties including the pumping lemma and many decidability results. Thus the new model seems to reflect more adequately what might be considered as a finite automata over the reals and similar structures. Though our results resemble classical properties, for proving them other techniques are necessary. One fundamental proof ingredient will be quantifier elimination over real closed fields.