Jumping Computation

Chapter 7Pure Jumping Grammars

This chapter studies jumping computation based upon the notion of a pure grammar G. Section 7.1 gives an introduction into its subject. Section 7.2 recalls all the terminology needed in this chapter and introduces a variety of jumping pure grammars, illustrated by an example. Finally, Section 7.3 presents fundamental results and concludes by summing up ten open problems.

7.1 Introduction

Jumping versions of language-defining rewriting systems, such as grammars and automata, represent a brand new trend in formal language theory. In essence, they act just like classical rewriting systems except that they work on strings discontinuously. That is, they apply a production rule so they erase an occurrence of its left-hand ...