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.
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 |