Modern Language Models and Computation | springerprofessional.de

Springer Professional

nach oben

2017 | Buch

Kapitel lesen Erstes Kapitel lesen

Modern Language Models and Computation

Theory with Applications

verfasst von: Dr. Alexander Meduna, Ondřej Soukup

Verlag: Springer International Publishing

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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.

Anzeige

Inhaltsverzeichnis

Frontmatter

Part I

Frontmatter

Chapter 1. Mathematical Background

Abstract

This three-section chapter reviews rudimentary mathematical concepts, including key notions concerning sets (Sect. 1.1), relations (Sect. 1.2), and graphs (Sect. 1.3). For readers having background in these areas, this chapter can be skipped and treated as a reference for terminology used later in this book.

Alexander Meduna, Ondřej Soukup

Chapter 2. Formal Language Theory: Basics

Abstract

This chapter covers the basics of formal language theory. It covers all the notions that are necessary to follow the rest of this book. Apart from the classical rudiments, however, the chapter covers several lesser-known areas of this theory, such as parallel grammars, because these areas are also needed to fully grasp some upcoming topics discussed in this book. The chapter consists of four sections.

Alexander Meduna, Ondřej Soukup

Part II

Frontmatter

Chapter 3. Regulated Grammars and Computation

Abstract

In practice, computation is almost always regulated by some additional conditions and restrictions placed upon the way it is performed under given circumstances. To investigate computation regulated in this way as precisely as possible, language theory has formalized it by a variety of regulated grammars. In essence, all these grammars are based upon some restrictions placed upon their derivations and, thereby, properly express computational regulation. This chapter covers major types of these grammars.

Alexander Meduna, Ondřej Soukup

Chapter 4. Parallel Grammars and Computation

Abstract

Originally, computer programs were always executed strictly sequentially. Indeed, to perform a computational task, an algorithm was written and implemented as an instruction sequence executed on a central processing unit on a single computer. Only one instruction was executed at a time, so after this instruction was completed, the next instruction was executed until all the sequence of instructions was performed in this one-by-one way. In the mid-1980s or so, however, computer programmers introduced the first pioneer programs that performed several parts of a single computational task simultaneously. At that time, parallel computation emerged in computer science.

Alexander Meduna, Ondřej Soukup

Chapter 5. Jumping Grammars and Discontinuous Computation

Abstract

Indisputably, processing information in a largely discontinuous way has become a quite common computational phenomenon [BYRN11, BCC10, MRS08]. Indeed, consider a process p that deals with information i. During a single computational step, p can read a piece of information x in i, erase it, generate a new piece of information y, and insert y into i possibly far away from the original occurrence of x, which was erased. Therefore, intuitively speaking, during its computation, p keeps jumping across i as a whole. To explore computation like this systematically and rigorously, the language theory should provide computer science with language-generating models to explore various information processors mathematically, so it should do so for the purpose sketched above, too.

Alexander Meduna, Ondřej Soukup

Chapter 6. Algebra, Grammars, and Computation

Abstract

In terms of algebra, the context-free and E0L grammatical derivations are traditionally defined over the free monoids generated by total alphabets of these grammars under the operation of concatenation. The present chapter, however, introduces and investigates these derivations over different algebraic structures in order to increase the generative power of these grammars.

Alexander Meduna, Ondřej Soukup

Part III

Frontmatter

Chapter 7. Regulated Automata and Computation

Abstract

Just like there exist regulated grammars, which formalize regulated computation (see Chap. 3), there also exist their automata-based counterparts for this purpose. Basically, in a very natural and simple way, these automata regulate the selection of rules according to which their sequences of moves are made. These regulated automata represent the principle subject of the present chapter, which covers their most essential types.

Alexander Meduna, Ondřej Soukup

Chapter 8. Jumping Automata and Discontinuous Computation

Abstract

Recall that jumping grammars (see Chap. 5) represent language-generating models for discontinuous computation. The present chapter explores their automata-based counterparts, called jumping automata. As their name suggests, they jump across their input words discontinuously, and in this way, they also formalize computation performed in a discontinuous way.

Alexander Meduna, Ondřej Soukup

Chapter 9. Deep Pushdown Automata and New Stack Structures

Abstract

Deep pushdown automata, explored in this chapter, represent language-accepting models based upon new stack structures, which can be modified deeper than on their top. As a result, these automata can make expansions deeper in their pushdown lists while ordinary pushdown automata (see Sect. 2.4) can expand only the very pushdown top.

Alexander Meduna, Ondřej Soukup

Chapter 10. Algebra, Automata, and Computation

Abstract

Traditionally, from an algebraic viewpoint, automata work over free monoids. The present chapter, however, modifies this standard approach so they work over other algebraic structures. More specifically, this chapter discusses a modification of pushdown automata that is based on two-sided pushdowns into which symbols are pushed from both ends.

Alexander Meduna, Ondřej Soukup

Part IV

Frontmatter

Chapter 11. Language-Generating Automata and State-Controlled Computation

Abstract

Traditionally, computation controlled by finitely many states is formalized by finite state automata, which accept their languages (see Sect. 2.4). Untraditionally, however, the present chapter explains how to adapt these automata in a very natural way so they act as language generators just like grammars. Consequently, the formalization of state-controlled computation can be based on the language-generating automata resulting from this adaptation.

Alexander Meduna, Ondřej Soukup

Chapter 12. Multigenerative Grammar Systems and Parallel Computation

Abstract

Today’s environment of cooperating multiprocessor computers allows us to base modern information technologies on a large combination of simultaneously running processes, which make use of this powerful environment as much as possible. Consequently, parallel computation plays a crucially important role in computer science at present as already pointed out in the beginning of Chap. 4

Alexander Meduna, Ondřej Soukup

Part V

Frontmatter

Chapter 13. Applications and Their Perspectives in General

Abstract

This chapter makes several general remarks about computational applications of modern language models covered earlier in this book. It also discusses their application perspectives in computer science in the near future.

Alexander Meduna, Ondřej Soukup

Chapter 14. Applications in Computational Linguistics

Abstract

This chapter gives several specific case studies concerning linguistics. Specifically, it demonstrates applications of scattered context grammars in this scientific field. It concentrates its attention to many complicated English syntactical structures and demonstrates how scattered context grammars allow us to explore them clearly, elegantly, and precisely.

Alexander Meduna, Ondřej Soukup

Chapter 15. Applications in Computational Biology

Abstract

This chapter presents some case studies concerning biology. It consists of Sects. 15.1, 15.2, and 15.3. Sect. 15.1 introduces simple case study using jumping scattered context derivation in DNA processing. Sect. 15.2 presents two case studies of biological organisms whose development is affected by some abnormal conditions, such as a virus infection. From a more practical point of view, Sect. 15.3 discusses parametric 0L grammars (see [PL90b]), which represent a powerful and elegant implementation tool in the area of biological simulation and modeling today. More specifically, we extend parametric 0L grammars by context conditions and demonstrate their use in models of growing plants.

Alexander Meduna, Ondřej Soukup

Part VI

Frontmatter

Chapter 16. Concluding Remarks

Abstract

This three-section chapter closes the book by adding several remarks concerning its coverage. Sect. 16.1 briefly summarizes all the material covered in the text. Furthermore, Sect. 16.2 sketches many brand new investigation trends as well as points out long-time open problems. Finally, it makes several bibliographical and historical remarks.

Alexander Meduna, Ondřej Soukup

Backmatter

Titel: Modern Language Models and Computation
verfasst von: Dr. Alexander Meduna
Ondřej Soukup
Copyright-Jahr: 2017
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-63100-4
Print ISBN: 978-3-319-63099-1
DOI: https://doi.org/10.1007/978-3-319-63100-4

Premium Partner