Publication Details
Jumping Computation: Updating Automata and Grammars for Discontinuous Information Processing
one-head automata, generalized jumping finite automata, one-way jumping finite automata, multi-head atuomata, double-jumping finite automata, multi-parallel jumping finite automata, jumping Watson-Creck finite automata, Jumping 5'->3' Watson-Crick finite automata, sequential jumping grammars, jumping scattered context grammars, pure jumping grammars, other discontinuous computation devices, application perspectives, models of DNA computation, debt lemma.
Jumping Computation: Updating Automata and Grammars for Discontinuous
Information Processing is primarily a theoretically oriented treatment
of jumping automata and grammars, covering all essential theoretical
topics concerning them, including their power, properties, and
transformations. From a practical viewpoint, it describes various
concepts, methods, algorithms, techniques, case studies and applications
based upon these automata and grammars.
In today's computerized world, the scientific development and study of
computation, referred to as the theory of computation, plays a crucial
role. One important branch, language theory, investigates how to define
and study languages and their models, which formalize algorithms
according to which
their computation is executed. These language-defining models are
classified into two basic categories: automata, which define languages
by recognizing their words, and grammars, which generate them.
Introduced many decades ago, these rules reflect classical sequential
computation. However,
today's computational methods frequently process information in a
fundamentally different way, frequently "jumping" over large portions of
the information as a whole. This book adapts classical models to
formalize and study this kind of computation properly. Simply put,
during their language-defining process, these adapted versions, called
jumping automata and grammars, jump across the
words they work on.
The book selects important models and summarizes key results about them
in a compact and uniform way. It relates each model to a particular form
of modern computation, such as sequential, semiparallel and totally
parallel computation. It explains how the model in question properly
reflects and formalizes the corresponding form of computation, thus
allowing us to obtain a systematized body of mathematically precise
knowledge concerning the jumping computation. The book pays special
attention to power, closure properties, and transformations and also
describes many algorithms that modify jumping grammars and automata so they satisfy some prescribed properties without changing the defined
language. The book will be of great interest to anyone researching the
theory of computation across the fields of computer science,
mathematics, engineering, logic and linguistics.
@book{BUT188317,
author="Alexandr {Meduna} and Zbyněk {Křivka}",
title="Jumping Computation: Updating Automata and Grammars for Discontinuous Information Processing",
year="2024",
publisher="CRC Press LLC",
address="Boca Raton",
pages="1--275",
doi="10.1201/9781003107910",
isbn="978-0-367-62093-6"
}