Algorithm in an alphabet

algorithm over an alphabet

"An exact, generally understandable set of instructions describing a potentially realizable process of successive transformation of abstract words over the alphabet A, in which any word over A may serve as the initial word" [1].

An algorithm over an alphabet is a special case of the general concept of an algorithm. The input and the possible outputs of an algorithm over an alphabet are constructive objects (cf. Constructive object) of sufficiently general type — words (cf. Word). Various formalizations of an algorithm over an alphabet were developed in the 1970s; the best known ones are Markov's normal algorithms (cf. Normal algorithm) and algorithms defined using the Turing machine. When constructing specific algorithms over alphabets, it is often useful to extend the starting alphabets by introducing additional letters and considering the algorithms over the alphabets thus extended. In the case of two algorithms over the same alphabet, the concepts of equivalence and complete equivalence of these algorithms with respect to it can be naturally introduced.

References

[1]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))

Comments

The connection between algorithmic descriptions of languages (on the basis of algorithms over an alphabet) and generative descriptions using formal grammars in the style of N. Chomsky, constitutes the essence of the theory of abstract automata and formal languages. The classic text is J.E. Hopcroft and J.D. Ullman's book [a1].

References

[a1]	J.E. Hopcroft, J.D. Ullman, "Formal languages and their relation to automata" , Addison-Wesley (1969) (Revised version: "Introduction to automata, languages and computation" Addison-Wesley, 1979)