Abstract
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 partciular 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 analyse 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ben-Or, M.: Lower bounds for algebraic decision trees. In: Proc. 15th ACM STOC, pp. 80–86 (1983)
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer (1998)
Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. 21, 1–46 (1989)
Bournez, O., Campagnolo, M.L.: A Survey on Continuous Time Computations. In: Cooper, B., Löwe, B., Sorbi, A. (eds.) New Computational Paradigms, Changing Conceptions of What is Computable, pp. 383–423. Springer, New York (2008)
Bürgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren, vol. 315. Springer (1997)
Cucker, F., Shub, M.: Generalized Knapsack problems and fixed degree separation. Theoretical Computer Science 161, 301–306 (1996)
Gandhi, A., Khoussainov, B., Liu, J.: Finite Automata over Structures. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol. 7287, pp. 373–384. Springer, Heidelberg (2012)
Haykin, S.: Neural Networks - A Comprehensive Foundation, 2nd edn. Prentice Hall (1999)
Meer, K.: On the complexity of Quadratic Programming in real number models of computation. Theoretical Computer Science 133(1), 85–94 (1994)
Meer, K., Ziegler, M.: Real Computational Universality: The word problem for a class of groups with infinite presentation. Foundations of Computational Mathematics 9(5), 599–609 (2009)
Meer, K., Ziegler, M.: An explicit solution to Post’s problem over the reals. Journal of Complexity 24(1), 3–15 (2008)
Meyer auf der Heide, F.: Lower bounds for solving linear diophantine equations on random access machines. Journal ACM 32(4), 929–937 (1985)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2000)
Paun, G.: Membrane Computing: An Introduction. Springer (2002)
Weihrauch, K.: Computable Analysis: An Introduction. Springer (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Meer, K., Naif, A. (2014). Generalized Finite Automata over Real and Complex Numbers. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds) Theory and Applications of Models of Computation. TAMC 2014. Lecture Notes in Computer Science, vol 8402. Springer, Cham. https://doi.org/10.1007/978-3-319-06089-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-06089-7_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06088-0
Online ISBN: 978-3-319-06089-7
eBook Packages: Computer ScienceComputer Science (R0)