Jumping models

Jumping models

For access to this article, please select a purchase option:

Buy chapter PDF
(plus tax if applicable)
Buy Knowledge Pack
10 chapters for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
Handbook of Mathematical Models for Languages and Computation — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Take a typical program p that processes information i within the framework of today's information technologies. During a computational step, p usually reads a piece of information x in i, erases it, generates a new piece of information y, and inserts y into somewhere into i, whereas the position of this insertion may occur far away from the original position of x, which was erased. Therefore, to put it simply, during its computation, p keeps jumping across i as a whole. To investigate this kind of modern computation mathematically, the language theory should provide computer science with appropriate mathematical models. The classical versions of automata and grammars work on words strictly continuously, however. Consequently, they can hardly serve as appropriate models for this purpose. A proper formalization of processors that work in the way sketched above necessitates an adaptation of classical grammars, so they work on words discontinuously. At the same time, any adaptation of this kind should conceptually maintain the original structure of these models as much as possible, so computer science can quite naturally base its investigation upon these newly adapted grammatical models by analogy with the standard approach based upon their classical versions. That is, these new models should work on words in a discontinuous way while keeping their structural conceptualization unchanged. This chapter discusses models that work in this discontinuous way. Indeed, automata and grammars discussed in this section are conceptualized just like their classical versions except that during the applications of their rules, they can jump over symbols in either direction within the rewritten strings, and in this jumping way, they define their languages

Chapter Contents:

  • 14.1 Sequential jumping grammars
  • 14.2 Parallel jumping grammars
  • 14.2.1 Definitions
  • 14.2.2 Results
  • Jumping derivation mode 1
  • Jumping derivation mode 2
  • Jumping derivation mode 3
  • Jumping derivation mode 4
  • Jumping derivation mode 5
  • Jumping derivation mode 6
  • Jumping derivation mode 7
  • Jumping derivation mode 8
  • Jumping derivation mode 9
  • Open problem areas
  • 14.3 Jumping automata
  • 14.3.1 Definitions and examples
  • Denotation of language families
  • 14.3.2 Properties
  • Relations with well-known language families
  • Closure properties
  • Decidability
  • An infinite hierarchy of language families
  • Left and right jumps
  • A variety of start configurations
  • Relations between jumping automata and jumping grammars
  • A summary of open problems

Inspec keywords: grammars; rewriting systems; automata theory

Other keywords: jumping models; grammars; language theory; rewritten strings; automata

Subjects: Automata theory; Formal languages and computational linguistics

Preview this chapter:
Zoom in

Jumping models, Page 1 of 2

| /docserver/preview/fulltext/books/pc/pbpc026e/PBPC026E_ch14-1.gif /docserver/preview/fulltext/books/pc/pbpc026e/PBPC026E_ch14-2.gif

Related content

This is a required field
Please enter a valid email address