Modern Language Models and Computation: Theory with Applications

Alexander Meduna, Full Professor of Computer Science at the Brno University of Technology, received his PhD from this university in 1988. He has taught mathematics and computer science at various European, Asian, and American universities, including the University of Missouri, where he spent a decade teaching advanced topics of the formal language theory and its applications in computer science. He is the author of the books entitled Automata and Languages (Springer, 2000), Elements of Compiler Design (Taylor and Francis, 2008), and Formal Languages and Computation: Models and Their Applications (CRC Press, 2014) . Along with his former PhD students, he is also the co-author of Grammars with Context Conditions and Their Applications (co-authored by M. Švec, Wiley, 2005), Scattered Context Grammars and their Applications (co-authored by J. Techet, WIT Press, 2010), and Regulated Grammars and Automata (co-authored by P. Zemek, Springer, 2014). He has published over ninety papers closely related to the subject of this book.

• Vita
• Scientific Work
• University Website

Ondřej Soukup received his PhD from the Brno University of Technology in 2017 under the supervision of Alexander Meduna. He has published several studies on modern language models in such distinguished computer science journals as Fundamenta Informatica, /International Journal of Foundations of Computer Science, and Theoretical Computer Science.

• Vita
• Scientific Work
• University Website

This textbook gives a systematized and compact summary, providing the most essential types of modern models for languages and computation together with their properties and applications. Most of these models properly reflect and formalize current computational methods, based on parallelism, distribution and cooperation covered in this book. As a result, it allows the user to develop, study, and improve these methods very effectively.

This textbook also represents the first systematic treatment of modern language models for computation. It covers all essential theoretical topics concerning them. From a practical viewpoint, it describes various concepts, methods, algorithms, techniques, and software units based upon these models. Based upon them, it describes several applications in biology, linguistics, and computer science.

Advanced-level students studying computer science, mathematics, linguistics and biology will find this textbook a valuable resource. Theoreticians, practitioners and researchers working in today’s theory of computation and its applications will also find this book essential as a reference.

• Ordered by appearance in the text.
• Last updated on 2018-01-31.
• Please, send additional errors and comments to: meduna@fit.vutbr.cz

• Page 173, Chapter 4, Section 4.1.4 (Reduction)
• In Definition 4.1.12, instead of “lhs(p) ≥ 2”, there should be “len(p) ≥ 2” in the definition of dcs(G).
• Reported 2018-01-31 by Zbyněk Křivka of Brno University of Technology.

• Page 321, Chapter 7, Section 7.1.1 (Self-Regulating Finite Automata)
• In Definition 7.1.2, instead of “j = 0, 1, …, n”, there should be “j = 0, 1, …, n-1”.
• Reported 2018-11-06 by Roman Andriushchenko of Brno University of Technology.

• Page 322, Chapter 7, Section 7.1.1 (Self-Regulating Finite Automata)
• In Example 7.1.3, 1-first-SFA M does not accept ab, so L(M) should be {a^n b^n | n > 1}. Note that we get original L(M) by adding (2,3) into R.
• Reported 2018-11-06 by Roman Andriushchenko of Brno University of Technology.

—-

The authors' thanks go to the readers who pointed out the errors.

To buy the book, visit this website or Amazon website