Abstract
This chapter presents a brief introduction to the theory of automata, formal languages, decidability, and complexity.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem, 2nd edn. Springer, Berlin (2001)
Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity. Prentice Hall, New York (1994)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1990)
Ginsburg, S.: Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland, Amsterdam (1975)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, 3rd edn. Addison Wesley, Boston (2006)
Jirásková, G., Masopust, T.: Complexity in union-free regular languages. International Journal of Foundations of Computer Science 22(7), 1639–1653 (2011)
Jones, N.D.: Computability and Complexity from a Programming Perspective. MIT Press, Cambridge (1997)
Kozen, D.C.: Automata and Computability. Springer, Berlin (1997)
Papadimitriou, C.: Computational Complexity. Addison Wesley, Boston (1993)
Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, pp. 1–3. Springer, Berlin (1997)
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, New York (2009)
Salomaa, A.: Formal Languages. Academic Press, New York (1973)
Salomaa, A.: Computation and Automata. Cambridge University Press, Cambridge (1985)
Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, New York (2008)
Sipser, M.: Introduction to the Theory of Computation, Course Technology, 2nd edn., Boston, MA (2005)
Sudkamp, T.: Languages and Machines: An Introduction to the Theory of Computer Science, 3rd edn. Addison Wesley, Boston (2005)
Szepietowski, A.: Turing Machines with Sublogarithmic Space. Springer, Berlin (1994)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag London
About this chapter
Cite this chapter
Haar, S., Masopust, T. (2013). Languages, Decidability, and Complexity. In: Seatzu, C., Silva, M., van Schuppen, J. (eds) Control of Discrete-Event Systems. Lecture Notes in Control and Information Sciences, vol 433. Springer, London. https://doi.org/10.1007/978-1-4471-4276-8_2
Download citation
DOI: https://doi.org/10.1007/978-1-4471-4276-8_2
Publisher Name: Springer, London
Print ISBN: 978-1-4471-4275-1
Online ISBN: 978-1-4471-4276-8
eBook Packages: EngineeringEngineering (R0)