The Markov algorithm as a language parser—Linear bounds

摘要

The Markov algorithm [1, 2] can be used as a language parser and as means fordefining languages [2–5]. This work is concerned with the amount of computing time which the algorithm requires. Computing time is measured by the number of comparisons between the rules of the grammar and the input string. A modification is introduced into the algorithm which reduces the computation time. It is proved that under certain conditions imposed on the rules of the grammar the computing time required by the modified algorithm is bounded linearly by the length of the input string. One set of such conditions requires that each application of a grammar rule reduces the length of the input string. Another set requires that each application does not increase the length of the input string and that the graph associated with the rules of the grammar satisfies certain restrictions.