کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
432106 | 1441296 | 2006 | 41 صفحه PDF | دانلود رایگان |

Many functions on context-free languages can be expressed in the form of the least fixed point of a function whose definition mimics the grammar of the given language. Examples include the function returning the length of the shortest word in a language, and the function returning the smallest number of edit operations required to transform a given word into a word in a language.This paper presents the basic theory that explains when a function on a context-free language can be defined in this way. It is shown how the theory can be applied in a methodology for programming the evaluation of such functions.Specific results include a novel definition of a regular algebra focusing on the existence of so-called “factors”, and several constructions of non-trivial regular algebras. Several challenging problems are given as examples, some of which are old and some of which are new.
Journal: The Journal of Logic and Algebraic Programming - Volume 66, Issue 2, February–March 2006, Pages 71-111