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"
}