کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
432106 1441296 2006 41 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Regular algebra applied to language problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Regular algebra applied to language problems
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: The Journal of Logic and Algebraic Programming - Volume 66, Issue 2, February–March 2006, Pages 71-111