• search hit 11 of 141
Back to Result List

Generalized finite automata over real and complex numbers

  • In a recent work, Gandhi, Khoussainov, and Liu [7] introduced and studied a generalized model of finite automata able to work over arbitrary structures. As one relevant area of research for this model the authors identify studying such automata over particular structures such as real and algebraically closed fields. In this paper we start investigations into this direction. We prove several structural results about sets accepted by such automata, and analyze decidability as well as complexity of several classical questions about automata in the new framework. Our results show quite a diverse picture when compared to the well known results for finite automata over finite alphabets.

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author: Klaus MeerGND, Ameen Naif
URL:http://www.sciencedirect.com/science/article/pii/S0304397515003928
DOI:https://doi.org/10.1016/j.tcs.2015.05.001
ISSN:0304-3975
Title of the source (English):Theoretical Computer Science
Document Type:Scientific journal article peer-reviewed
Language:English
Year of publication:2015
Tag:Decision problems for automata over uncountable structures; Generalized finite automata; Real and complex number computations
Volume/Year:Vol. 591
First Page:85
Last Page:98
Faculty/Chair:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Theoretische Informatik
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.